The Foundations of Cryptography

Oded Goldreich

The Foundations of Cryptography are the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural Cryptographic problems.

Material available on-line

• Surveys: The surveys start by presenting some of the central tools; that is, computational difficulty (in the form of one-way functions), pseudorandomness, and zero-knowledge proofs. Based on these tools, they turn to the treatment of basic applications such as encryption and signature schemes as well as the design of general secure cryptographic protocols. The presentation assumes basic knowledge of algorithms, probability theory and complexity theory, but nothing beyond this.
  • Foundations of Cryptography - A Primer (2004).
    This survey is more extensive than the previous ones available below and superseeds them as an introductory text.
  • Cryptography and Cryptographic Protocols (2001).
    Assumes no prior familiarity with cryptography. Aims to introduce the reader (who may know nothing about cryptography) to the basic paradigms, approaches, techniques and results that provide the foundations of the discipline. (Originally intended for researchers in distributed computing.)
  • The Foundations of Cryptography - An Essay (1997).
    Intended for readers who have some familiarity with the basic problems of Cryptography. Aims to introduce such readers (who may even be very knowledgeable about the applied aspects of cryptography) to the rigorous foundations of the discipline, while attempting to dissolve common misconceptions regarding these foundations.
  
  
• Webpage for a two-volume work: The work is organized in two logical parts (volumes): Basic Tools, and Basic Applications. Each part (volume) will appear seperately, once ready. Their respective contents and status is as follows:
  • Foundations of Cryptography - Volume 1 (Basic Tools):
    An introductory chapter as well as chapters on One-Way Functions, Pseudorandom Generators and Zero-Knowledge Proofs.
    Published in 2001.
  • Foundations of Cryptography - Volume 2 (Basic Applications):
    Chapters on on Encryption, Signatures and Cryptographic Protocols.
    Published in 2004.
  Preliminary drafts are available here. Also available are related teaching notes, 2002.
  
  

• Specific topics:

  • Zero-Knowledge: A Tutorial, 2002.
  • General Cryptographic Protocols: The Very Basics, 2010.
  
  See also selection of (O.G.'s) works in cryptography and webpages on specific topics.
  

Archive:

• Foundations of Cryptography - Fragments of a Book (1995 and 1998).
  These are old (unpolished) fragments of the work mentioned above. These include a preliminary draft of Volume 1 (ie., an introductory chapter, and the chapters on one-way functions, pseudorandomness and zero-knowledge). Also included is an even rougher draft of a chapter on encryption schemes.
  
  
• Lecture Notes on Encryption, Signatures and Cryptographic Protocols (1989).
  These notes are subsumed by the drafts of Volume 2 mentioned above.
  
  
• Secure Multi-Party Computation (working draft) (1998).
  This text subsumes the above lecture notes on Cryptographic Protocols, and is subsumed by Volume 2 mentioned above.