unsolicited statement for 2009-18
|
My research interests lie in the theory of computing,
specifically in the interplay between randomness and computation.
Two areas of interest are complexity theory,
which is the general study of the nature and limitations
of efficient computations, and property testing,
which is the study of super-fast approximate decision procedures.
Within complexity theory, I am most interested
in pseudorandomnessand and probabilistic proof systems.
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 recently completed
a textbook entitled
Introduction to Property Testing.
Selected publications
- [with D. Ron]
On Proximity Oblivious Testing.
SICOMP, Vol. 40, No. 2, pages 534-566, 2011.
- [with B. Juba, and M. Sudan]
A Theory of Goal-Oriented Communication.
JACM Vol. 59, No. 2, Art. 8, 2012.
- [with A. Wigderson]
On Derandomizing Algorithms that Err Extremely Rarely.
In 46th STOC, pages 109-118, 2014.
- [with A. Tal]
Matrix Rigidity of Random Toeplitz Matrices.
In 48th STOC pages 91-104, 2016.
- [with D. Ron]
On Learning and Testing Dynamic Environments.
JACM, Vol. 64, No. 3, pages 21:1-21:90, 2017.
- [with G. Rothblum]
Counting t-cliques: Worst-case to average-case reductions
and direct interactive proof systems.
ECCC TR18-046, 2018.
|
|
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, Vol. 53, No. 4, pages 558-655, 2006.
- [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),
Vol. 36, No. 4, pages 889-974, 2006.
- [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
|
|
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).
|
|
|