We survey the main paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural cryptographic problems. We 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, we turn to the treatment of basic applications such as encryption and signature schemes as well as the design of general secure cryptographic protocols.
Our presentation assumes basic knowledge of algorithms, probability theory and complexity theory, but nothing beyond this.
Material available on-line:
Related Material available on-line: A webpage on Foundations of Cryptography, including access to the following manuscripts (and more).
Back to the Foundations of Cryptography page or to Oded Goldreich's homepage.