Oded Goldreich

Modern Cryptography, Probabilistic Proofs and Pseudorandomness

ISBN 3-540-64766-x
Springer-Verlag, Algorithms and Combinatorics, Vol 17, 1998.
For orders, see publisher's webpage.

This page includes the book's preface, Table of Contents, List of References, answers to Frequently Asked Questions, and List of Corrections.

Revised versions of the three main chapters have appeared as independent primers on Foundations of Cryptography (2005), Probabilistic Proof Systems (2008), and Pseudorandom Generators (2008).

See also draft of a revised version (2000) and related material available on-line.


The interplay between randomness and computation is one of the most fascinating scientific phenomena uncovered in the last couple of decades. This interplay is at the heart of modern cryptography and plays a fundamental role in complexity theory at large. Specifically, the interplay of randomness and computation is pivotal to several intriguing notions of probabilistic proof systems and is the focal of the computational approach to randomness. This book provides an introduction to these three, somewhat interwoven domains (i.e., cryptography, proofs and randomness).

Modern Cryptography. Whereas classical cryptography was confined to the art of designing and breaking encryption schemes (or ``secrecy codes''), Modern Cryptography is concerned with the rigorous analysis of any system which should withstand malicious attempts to abuse it. We emphasize two aspects of the transition from classical to modern cryptography: (1) the widening of scope from one specific task to an utmost wide general class of tasks; and (2) the move from an engineering-art which strives on ad-hoc tricks to a scientific discipline based on rigorous approaches and techniques. In this book we provide an introduction to the foundations of Modern Cryptography. We focus on the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural cryptographic problems. We also survey some of the fundamental results obtained using these paradigms, approaches and techniques. The emphasis of the exposition is on the need for and impact of a rigorous approach.

Probablistic Proof Systems. Various types of probabilistic proof systems have played a central role in the development of computer science in the last decade. These proof systems share a common (untraditional) feature -- they carry a probability of error; yet, this probability is explicitly bounded and can be reduced by successive application of the proof system. The gain in allowing this untraditional relaxation is substantial, as demonstrated by three well known results regarding interactive proofs, zero-knowledge proofs, and probabilistic checkable proofs: In each of these cases, allowing a bounded probability of error makes the system much more powerful and useful than the traditional (errorless) counterparts. Focusing on the three types of proof systems mentioned above, but going also beyond them, we survey the basic definitions and results regarding probabilistic proofs. Our exposition stresses both the similarities and differences between the various types of probabilistic proofs.

Pseudorandomness. A fresh view at the question of randomness was taken in the theory of computing: It has been postulated that a distribution is pseudorandom if it cannot be told apart from the uniform distribution by any efficient procedure. This paradigm, originally associating efficient procedures with polynomial-time algorithms, has been applied also with respect to a variety of limited classes of such distinguishing procedures. Starting with the general paradigm, we survey the archetypical case of pseudorandom generators (withstanding any polynomial-time distinguisher), as well as generators withstanding space-bounded distinguishers, the derandomization of complexity classes such as BPP, and some special-purpose generators.

An underlying assumption. Much of the contents of this book depends on the widely believed conjecture by which P neq NP. This dependency is explicitly stated in some of the results which make even stronger assumptions (such as the existence of one-way functions), and is implicit in some results (such as the PCP Characterization of NP) which would become uninteresting if P=NP.

On the nature of this book. This book offers an introduction and extensive survey to each of the three areas mentioned above. It present both the basic notions and the most important (and sometimes advanced) results. The presentation is focused on the essentials and does not ellaborate on details. In some cases it offers a novel and illuminating perspective. The goal is to provide the reader with

It is hoped that the book may be useful both to a beginner (who has only some background in the theory of computing), and to an expert in any of these areas.

Organization. In Chapter 1 we survey the basic concepts, definitions and results in cryptography. In particular, we survey the basic tools of cryptography -- computational difficulty, pseudorandomness and zero-knowledge proofs -- and the basic utilities -- encryption, signatures, and general cryptographic protocols. Chapters 2 and 3 provides a wider perspective on two concepts mentioned in Chapter 1. Specifically, Chapter 2 surveys various types of probabilistic proof systems including interactive proofs, zero-knowledge proofs and probabilistically checkable proofs (PCP). (The overlap with Chapter 1 is small, and the presentation is quite different.) Likewise, Chapter 3 surveys various notions of pseudorandom generators, viewing the one discussed in Chapter 1 as an archetypical instantiation of a general paradigm.

The three chapters may be read independently of each other. In particular, each starts with an individual brief introduction to the respective subject matter. As hinted above, although the chapters do overlap, the perspectives taken in them are different. Specifically, Chapter 1 treats the theoretical foundations of a practical discipline, and so the presentation departs from practice and emphasizes the importance of rigorous treatment for sound practice (and not merely per se). In contrast, Chapters 2 and 3 depart from the theory of computing and emphasize the intellectual contents of the material (rather than its practical applicability). The fact that different perspectives co-exist in the same book, let alone in the same author, is indicative of the nature of the theory of computing.

The three chapters are augmented by four appendices and an extensive bibliography. Most importantly, Appendix A provides some basic background on computation and randomness. We mention that important relations between randomness and computation were discovered also in other domains of the theory of computation. Some examples are given in Appendix B. Appendix C provides proofs of two basic results; one being a folklore for which no proof has ever appeared, and the other for which the published proof is both too terse and more complex than the alternative presented here.

Table of Contents


Chapter 1: The Foundations of Modern Cryptography

Chapter 2: Probabilistic Proof Systems

Chapter 3: Pseudorandom Generators

Appendix A: Background on Randomness and Computation

Appendix B: Randomized Computations

Appendix C: Notes on two proofs

Appendix D: Related Surveys by the Author

Bibliography (over 300 entries)


List of References

The original bibliography. [in PDF].

Frequently Asked Questions

How does this book relate to the fragments of the book on the Foundations of Cryptography? This book is almost unrelated to the fragments. The only relation is that Chapter 1 provides a 30-page overview (or summary) to what may become a 600-pages textbook on the Foundations of Cryptography. In fact, the structure of Chapter 1 (specifically, sections 1.2--1.7) mimics the planned structure of the big book. (Btw, very preliminary versions of 5 out of the 6 planned chapters are available on-line at the above URL.)

What is the realtion among the main chapters of the current book? See preface: Indeed, there is some small intersection between the three main chapters, but the perspectives are different.

Can this book be used for teaching? This book is not a textbook; yet, I believe that it provides good overviews for three potential courses, corresponding to the three chapters. Such overviews may be useful especially in conjunction with additional (more detailed) material (which sometimes lacks an overview).

List of Corrections

Related material available on-line

Revised versions of the three main chapters have appeared as independent primers on Foundations of Cryptography (2005), Probabilistic Proof Systems (2008), and Pseudorandom Generators (2008).

Back to the top or to Oded Goldreich's homepage.