Oded Goldreich coauthored the pseudorandom function family construction with Shafi Goldwasser and Silvio Micali. The construction uses a pseudorandom generator to expand a seed into two child seeds; successive input bits choose left or right children. Only the selected path is evaluated, so a short input can be processed without generating the whole tree.[ref]
The result connects compact computation with a much larger implicit table of values. Security requires that efficient adaptive observers cannot distinguish this keyed table from a randomly chosen function, under the paper's computational assumptions.
- How to Construct Random Functions by Oded Goldreich, Shafi Goldwasser and Silvio Micali
- In a World of P=BPP by Oded Goldreich
- On Defining Proofs of Knowledge by Mihir Bellare and Oded Goldreich
- Probabilistic Proof Systems: A Primer by Oded Goldreich
- Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems by Oded Goldreich and others
- Zero-Knowledge: a tutorial by Oded Goldreich
- Zero-Knowledge chapter draft of Foundations of Cryptography by Oded Goldreich
Articles by others on the same topic
Oded Goldreich is a prominent Israeli computer scientist known for his contributions to the fields of cryptography, complexity theory, and algorithm design. He has made significant advancements in theoretical computer science, particularly in the areas of secure multi-party computation, zero-knowledge proofs, and randomness in computation. Goldreich has authored or co-authored numerous influential papers and is recognized for his work in making complex theoretical concepts accessible and applicable in real-world scenarios.