Oded Goldreich: periodical statement

Periodical statements of Oded Goldreich

These statements were prepared for the department's booklet. They are supposed to refer to research done in the last five years and contain at most three publications.

Statement for the Faculty Web-page (2008)

My research interests lie in the theory of computing, specifically in complexity theory, which is the general study of the nature and limitations of efficient computations. Within this theory, I am most interested in the interplay between randomness and computation (e.g., pseudorandomness, probabilistic proof systems, and property testing) and in the foundations of cryptography. For more details see my (extended) profile and my list of publications.
In addition to plain research, I'm involved in various educational and expositional efforts. In particular, I wrote a two-volume book entitled Foundations of Cryptography (published in 2001 and 2004, resp.) as well as a number of surveys on Foundations of Cryptography, Pseudorandomness and Zero-Knowledge. Recently, I completed a book entitled Computational Complexity: A Conceptual Perspective.
Recent Publications

[with M. Sudan] Locally testable codes and PCPs of almost-linear length. JACM 53: 4 (2006) 558-655.

[with E. Ben-Sasson, P. Harsha, M. Sudan, and S. Vadhan] Robust PCPs of proximity, shorter PCPs and applications to coding. SICOMP (special issue on Randomness and Complexity) 36: 4 (2006) 889-974.

[with D. Ron] Algorithmic aspects of property testing in the dense graphs model. ECCC Report TR08-039, April 2008.

Statement for the 2004 Booklet

My research interests lie in the theory of computing, specifically in complexity theory, which is the general study of the nature and limitations of efficient computations. Within this theory, I am most interested in the interplay between randomness and computation and in the foundations of cryptography.
My recent and current research projects include the investigation of Locally Testable Codes (i.e., codes that admit very efficient codeword tests), the development of techniques for constructing good Probabilistically Checkable Proofs (with focus on the proof length), the initiation of a theory regarding the complexity of implementing random objects, the developement of a session-key protocol using human passwords only, the initiation of the study of the security of cryptographic systems (say of Zero-Knowledge proofs) under resetting attacks, a demonstration of the impossibility of obfuscating program, and various studies concerning pseudorandomness as well as probabilistic proof systems.
In addition to the above, I'm involved in various educational and expositional efforts. In particular, I've written a two-volume book entitled "Foundations of Cryptography" (Volume 1 was published in 2001, and Volume 2 will be published in 2004) as well as a number of surveys on the Foundations of Cryptography, Pseudorandomness and Zero-Knowledge. In addition, I have advised three PhD students: Boaz Barak, Yehuda Lindell and Alon Rosen.

Recent Publications

[with M. Sudan] Locally Testable Codes and PCPs of Almost-Linear Length. In the proceedings of the 43rd IEEE Symp. on Foundation of Computer Science, pages 13-22, 2002.
[with S. Goldwasser and A. Nussboim] On the Implementation of Huge Random Objects. In the proceedings of the 44th IEEE Symp. on Foundation of Computer Science, pages 68-79, 2003.

[with B. Barak] Universal Arguments and their Applications. In the proceedings of the 17th IEEE Conference on Computational Complexity, pages 194-203, 2002.

Statement for the 1999 Booklet

My research interests lie in the theory of computing. Within this theory, I am most interested in the interplay between randomness and computation and in the foundations of cryptography. In general, I am interested in complexity theory, which is the study of the nature and limitations of efficient computations.

My recent and current research projects include the development of techniques for constructing good (if not optimal) probabilistically checkable proofs and for determining the level of approximation attainable by efficient algorithms for natural optimization problems, the initiation and investigation of Combinatorial Property Testing (the study of the complexity of determining whether a given object has a predetermined property or is ``far'' from any object having the property), the development of techniques for the design of zero-knowledge proofs (for example, a transformation of proofs which yield no knowledge to the prescribed verifier into ones which yield no knowledge to any verifier), and the re-examination of the Random Oracle Model/Methodology (which is extensively used recently in the design of practical cryptographic protocols).

In addition to the above, I'm involved in various educational and expositional efforts. In particular, I've published numerous surveys on topics related to the above, and wrote an introductory 200-pages text, entitled Modern Cryptography, Probabilistic Proofs and Pseudorandomness.

Recent Publications

[with M. Bellare and M. Sudan] Free Bits, PCPs and Non-Approximability - Towards Tight Results. SICOMP, Vol. 27, No. 3, pages 804-915, June 1998.
[with S. Goldwasser and D. Ron] Property Testing and its connection to Learning and Approximation. Journal of the ACM, pages 653--750, July 1998.
[with R. Canetti and S. Halevi] The Random Oracle Methodology, Revisited. In the proceedings of the 30th ACM Symp. on Theory of Computing, pages 209--218, 1998.

Statement for the 1994 Booklet

In recent years, the investigation of the relations between randomness and computation and the application of randomness to computations, has become a central aspect of the theory of computation. In particular, the notions of pseudorandom generators, probabilistic proofs, weak random sources and constructions of small probability spaces have played an important role in the development of cryptography, complexity theory, and algorithmic design. Much of my research in the past, present and future is concerned with these notions. Following are a few words of clarification concerning two of the notions mentioned above.

Loosely speaking, a pseudorandom generator is an efficient (deterministic) program that stretches a randomly chosen seed into a much longer sequence, which nevertheless looks random to any efficient observer. Pseudorandom generators allow to shrink the amount of randomness used by any efficient randomized application program; namely, any application using a source of randomness can be modified so that it only uses much fewer, say 1000, coin tosses.

Various forms of probabilistic proof systems have been the focus of much attention in recent years. These non-traditional proof systems offer many advantages over the classical notion of a proof. For example, probabilistic proofs may be zero-knowledge in the sense that they leak nothing except the validity of the assertion being proven. Namely, whatever can be efficiently computed after getting a zero-knowledge proof, can be efficiently computed from the assertion itself. This paradoxical-looking notion has a tremendous effect on the design of cryptographic protocols, as has been demonstrated in some of my past works.

Recent Publications (not included originally)

O. Goldreich, H. Krawczyk, and M. Luby, On the Existence of Pseudorandom Generators, SIAM Journal on Computing, Vol. 22-6, pages 1163-1175, Dec. 1993.
O. Goldreich and H. Krawczyk, On the Composition of Zero-Knowledge Proof Systems, in the Proc. of the 17th International Colloquium on Automata Languages and Programming (ICALP), Lecture Notes in Computer Science, Vol. 443, Springer Verlag, pages 268-282, 1990.
N. Alon, O. Goldreich J. Hastad and R. Peralta, Simple Constructions of Almost k-wise Independent Random Variables, Journal of Random structures and Algorithms, Vol. 3, No. 3, pages 289-304, 1992.

Statement for the 1980's

Since I moved to Weizmann Institute in 1994, statements referring to previous periods were not made. In my e-records, I could only find a report referring to the academic year 1985-86 (and written for LCS's progress report to MIT). The first two paragraphs are reproduced below.

During the past year, Goldreich has been mainly interested in two topics: zero-knowledge proofs and software protection. In addition he improved the Goldwasser-Micali-Rivest signature sheme, and has been working with Chor on developing better schemes for extracting unbiased bits from weak sources of randomness.
Together with Prof. S. Micali (MIT) and A. Wigderson (UC-Berkeley), he has demonstrated the generality and wide applicability of zero-knowledge proofs, a fundamental notion intruduced by Goldwasser, Micali and Rackoff. Zero-knowledge proofs are probabilistic and interactive proofs that efficiently demonstrate membership in a language without conveying any additional knowledge. So far, zero-knowledge proofs has been known for some number theoretic languages in the intersection of NP and Co-NP. Under the assumption that encryption functions exist, it is shown that all languages in NP possess zero-knowledge proofs. This result is used to prove two fundamental theorems in the field of cryptographic protocols. These theorems consists of standard and efficient transformations that, given a protocol that is correct with respect to a very weak adversary, output a protocol correct in the most adversarial scenario. Using no assumptions, zero-knowledge proofs for both graph isomorphism and graph non-isomorphism, are presented.

A selected list of publications for the 1980's would have read as follows:

O. Goldreich and L.A. Levin, Hard-core Predicates for any One-way Function, in the proceeding of the 21st STOC, 1989.
O. Goldreich, S. Micali, and A. Wigderson, How to Solve any Protocol Problem, in the proceeding of the 19th STOC, 1987.
O. Goldreich, S. Micali, and A. Wigderson, Proofs that Yield Nothing but their Validity and a Methodology of Cryptographic Protocol Design, in the proceeding of the 27th FOCS, 1986.
(Later published under the title Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs, in JACM, Vol. 38, No. 3, 1991.)
B. Chor and O. Goldreich, Unbiased Bits From Sources of Weak Randomness and Probabilistic Communication Complexity, in the proceeding of the 26th FOCS, 1985.
(Later published in SIAM J. on Computing, Vol. 17, No. 2, 1988.)
W. Alexi, B. Chor, O. Goldreich, and C. P. Schnorr, RSA/Rabin Bits Are ((1/2)+(1/poly(log N)))-Secure, in the proceeding of the 25th FOCS, 1984.
(Later published under the title RSA/Rabin Functions: Certain Parts are As Hard As the Whole, in SIAM J. on Computing, Vol. 17, No. 2, 1988.)
O. Goldreich, S. Goldwasser and S. Micali, How to Construct Random Functions, in the proceeding of the 25th FOCS, 1984.
(Later published in JACM, Vol. 33, No. 4, 1986.)
S. Even and O. Goldreich, On the Security of Multi-Party Ping-Pong Protocols, in the proceeding of the 24th FOCS, 1983.

I allowed myself a seventh paper (so to include one work from my graduate studies period) and ordered the papers by reverse chronological order (referring to the actual time they were first made public).

Back to Oded Goldreich's homepage.