Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

This website provides access to the old fragments that are currently superseeded by a book in preparation (by O.G.).

Oded Goldreich:

Foundations of Cryptography (Fragments of a Book)

Revolutionary developments which took place in the previous decade have transformed cryptography from a semi-scientific discipline to a respectable field in theoretical Computer Science. In particular, concepts such as computational indistinguishability, pseudorandomness and zero-knowledge interactive proofs were introduced, and classical notions as secure encryption and unforgeable signatures were placed on sound grounds.

Our intention was to write a book that presents the basic concepts, definitions and results in cryptography. In a first burst of energy, most of the material appearing in these fragments was written, but since then very little progress has been done. Thus, I see it preferable to place these fragments in public domain rather than wait till the original plan is completed.

These fragments contain a first draft for three major chapters and an introduction chapter. The three chapters are the chapters on computational difficulty (or one-way functions), pseudorandom generators and zero-knowledge. These chapters are quite complete with the exception that the zero-knowledge chapter misses the planned section on non-interactive zero-knowledge. However, none of these chapters has been carefully proofread and I expect them to be full of various mistakes ranging from spelling and grammatical mistakes to minor technical inaccuracies. I hope and believe that they are no fatal mistakes, but I cannot guarantee this either.

In addition, the fragments contain an old annotated list of references (compiled mostly in February 1989). Again, I feel that something incomplete is better than nothing.

Download PDF-file of the entire book.

Errors in the fragments
Additional (older) notes which cover material not in the fragments can be found in Lecture Notes on Encryption, Signatures and Cryptographic Protocols (1989)
See news concerning the fragments.
Oded Goldreich
Tel-Aviv, February 1995.

ISSN 1433-8092 | Imprint