The Foundations of Cryptography - a two-volume book

Oded Goldreich


The book was planned to consist of three volumes:

Preliminary drafts are available here. See also related material in the author's webpage on Foundations of Cryptography (including surveys and teaching notes).

Lecture/Teaching Notes: See outline for a course based on this book, and guidelines for independent reading. The latter guidelines assume 20 (or so) two-hour meetings.

This page includes the book's preface, Organization, and answers to Frequently Asked Questions.


It is possible to build a cabin with no foundations,
but not a lasting building.
Eng. Isidor Goldreich (1906-95).

Preface

Cryptography is concerned with the construction of schemes that withstand any abuse: Such schemes are constructed so to maintain a desired functionality, even under malicious attempts aimed at making them deviate from their prescribed functionality.

The design of cryptography schemes is a very difficult task. One cannot rely on intuitions regarding the typical state of the environment in which the system operates. For sure, the adversary attacking the system will try to manipulate the environment into untypical states. Nor can one be content with counter-measures designed to withstand specific attacks, since the adversary (which acts after the design of the system is completed) will try to attack the schemes in ways that are typically different from the ones the designer had envisioned. The validity of the above assertions seems self-evident, still some people hope that in practice ignoring these tautologies will not result in actual damage. Experience shows that these hopes rarely come true; cryptographic schemes based on make-believe are broken, typically sooner than later.

In view of the above, we believe that it makes little sense to make assumptions regarding the specific strategy that the adversary may use. The only assumptions that can be justified refer to the computational abilities of the adversary. Furthermore, it is our opinion that the design of cryptographic systems has to be based on firm foundations; whereas ad-hoc approaches and heuristics are a very dangerous way to go. A heuristic may make sense when the designer has a very good idea about the environment in which a scheme is to operate, yet a cryptographic scheme has to operate in a maliciously selected environment which typically transcends the designer's view.

This book is aimed at presenting firm foundations for cryptography. The foundations of cryptography are the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural ``security concerns''. We will present some of these paradigms, approaches and techniques as well as some of the fundamental results obtained using them. Our emphasis is on the clarification of fundamental concepts and on demonstrating the feasibility of solving several central cryptographic problems.

Solving a cryptographic problem (or addressing a security concern) is a two-stage process consisting of a definitional stage and a constructive stage. First, in the definitional stage, the functionality underlying the natural concern is to be identified, and an adequate cryptographic problem has to be defined. Trying to list all undesired situations is infeasible and prone to error. Instead, one should define the functionality in terms of operation in an imaginary ideal model, and require a candidate solution to emulate this operation in the real, clearly defined, model (which specifies the adversary's abilities). Once the definitional stage is completed, one proceeds to construct a system that satisfies the definition. Such a construction may use some simpler tools, and its security is proven relying on the features of these tools. In practice, of course, such a scheme may need to satisfy also some specific efficiency requirements.

This book focuses on several archetypical cryptographic problems (e.g., encryption and signature schemes) and on several central tools (e.g., computational difficulty, pseudorandomness, and zero-knowledge proofs). For each of these problems (resp., tools), we start by presenting the natural concern underlying it (resp., its intuitive objective), then define the problem (resp., tool), and finally demonstrate that the problem may be solved (resp., the tool can be constructed). In the latter step, our focus is on demonstrating the feasibility of solving the problem, not on providing a practical solution. As a secondary concern, we typically discuss the level of practicality (or impracticality) of the given (or known) solution.

Computational Difficulty

The specific constructs mentioned above (as well as most constructs in this area) can exist only if some sort of computational hardness exists. Specifically, all these problems and tools require (either explicitly or implicitly) the ability to generate instances of hard problems. Such ability is captured in the definition of one-way function (see further discussion in Section 2.1). Thus, one-way functions is the very minimum needed for doing most sorts of cryptography. As we shall see, they actually suffices for doing much of cryptography (and the rest can be done by augmentations and extensions of the assumption that one-way functions exist).

Our current state of understanding of efficient computation does not allow us to prove that one-way functions exist. In particular, the existence of one-way functions implies that NP is not contained in BPP (not even ``on the average''), which would resolve the most famous open problem of computer science. Thus, we have no choice (at this stage of history) but to assume that one-way functions exist. As justification to this assumption we may only offer the combined believes of hundreds (or thousands) of researchers. Furthermore, these believes concern a simply stated assumption, and their validity follows from several widely believed conjectures which are central to some fields (e.g., the conjecture that factoring integers is hard is central to computational number theory).

As we need assumptions anyhow, why not just assume what we want (i.e., the existence of a solution to some natural cryptographic problem)? Well, first we need to know what we want: as stated above, we must first clarify what exactly we want; that is, go through the typically complex definitional stage. But once this stage is completed, can we just assume that the definition derived can be met? Not really: once a definition is derived how can we know that it can at all be met? The way to demonstrate that a definition is viable (and so the intuitive security concern can be satisfied at all) is to construct a solution based on a {\em better understood}\/ assumption (i.e., one that is more common and widely believed). For example, looking at the definition of zero-knowledge proofs, it is not a-priori clear that such proofs exist at all (in a non-trivial sense). The non-triviality of the notion was first demonstrated by presenting a zero-knowledge proof system for statements, regarding Quadratic Residuosity, which are believed to be hard to verify (without extra information). Furthermore, in contrary to prior beliefs, it was later shown in that the existence of one-way functions implies that any NP-statement can be proven in zero-knowledge. Thus, facts which were not known at all to hold (and even believed to be false), where shown to hold by reduction to widely believed assumptions (without which most of modern cryptography collapses anyhow). To summarize, not all assumptions are equal, and so reducing a complex, new and doubtful assumption to a widely-believed simple (or even merely simpler) assumption is of great value. Furthermore, reducing the solution of a new task to the assumed security of a well-known primitive typically means providing a construction that, using the known primitive, solves the new task. This means that we do not only know (or assume) that the new task is solvable but rather have a solution based on a primitive that, being well-known, typically has several candidate implementations.

Our Approach and Prerequisites

Our aim is to present the basic concepts, techniques and results in cryptography. As stated above, our emphasis is on the clarification of fundamental concepts and the relationship among them. This is done in a way independent of the particularities of some popular number theoretic examples. These particular examples played a central role in the development of the field and still offer the most practical implementations of all cryptographic primitives, but this does not mean that the presentation has to be linked to them. On the contrary, we believe that concepts are best clarified when presented at an abstract level, decoupled from specific implementations. Thus, the most relevant background for this book is provided by basic knowledge of algorithms (including randomized ones), computability and elementary probability theory. Background on (computational) number theory, which is required for specific implementations of certain constructs, is not really required here (yet, a short appendix presenting the most relevant facts is included in Volume 1 so to support the few examples of implementations presented here).

Using this book

The book is aimed to serve both as a textbook and a reference text. That is, it is aimed at serving both the beginner and the expert. In order to achieve this aim, the presentation of the basic material is very detailed so to allow a typical CS-undergraduate to follow it. An advanced student (and certainly an expert) will find the pace (in these parts) way too slow. However, an attempt was made to allow the latter reader to easily skip details obvious to him/her. In particular, proofs are typically presented in a modular way. We start with a high-level sketch of the main ideas, and only later pass to the technical details. Passage from high-level descriptions to lower level details is typically marked by phrases such as details follow. More advanced material is typically presented at a faster pace and with less details. Thus, we hope that the attempt to satisfy a wide range of readers will not harm any of them.

Organization

The book is organized in three parts (volumes): Basic Tools, Basic Applications, and Beyond the Basics. The partition is a logical one. Furthermore, it offers the advantage of publishing the first volume without waiting for the completion of the other volumes. Similarly, we hope to complete the second volume within a few years, and publish it without waiting for the third volume. The planned volumes are:

Teaching

The material presented in this book is, on one hand, way beyond what one may want to cover in a course, and on the other hand falls very short of what one may want to know about Cryptography in general. To assist these conflicting needs we make a distinction between basic and advanced material, and provide suggestions for further reading (in the last section of each chapter). In particular, sections, subsections, and subsubsections marked by an asterisk (*) are intended for advanced reading.

Volumes 1 and 2 of this book are supposed to provide all material for a course on Foundations of Cryptography. For a one-semester course, the teacher will definitely need to skip all advanced material (marked by an asterisk) and maybe even some basic material: see suggestion below. This should allow, depending on the class, to cover the basic material at a reasonable level (i.e., cover all material marked as ``main'' and some of the ``optional''). Volumes 1 and 2 can also serve as textbook for a two-semester course. Either way, Volume 1 only covers the first half of the material mentioned above. The second half will be covered in Volume 2. In the meanwhile, we suggest to use other sources for the second half. A brief summary of Volume 2 and recommendations for alternative sources are given in Appendix B of Volume 1. (In addition, fragments and/or preliminary drafts for the three missing chapters are available on-line.)

Following is our suggestion for a one-semester course on Foundations of Cryptography. Each lecture consists of one hour. Lectures 1-15 are covered by Volume 1. Lectures 16-28 will be covered by Volume 2.

Giving a course solely based on the material that appears in Volume 1 is indeed possible, but such a course cannot be considered a stand-alone course in Cryptography (for the reason that the current volume does not consider at all the basic tasks of encryption and signatures).

Practice

The aim of this book is to provide sound theoretical foundations for cryptography. As argued above, such foundations are necessary for sound practice of cryptography. Indeed, practice requires more than theoretical foundations, whereas the current book makes no attempt to provide anything beyond the latter. However, given sound foundations, one can learn and evaluate various practical suggestions that appear elsewhere. On the other hand, lack of sound foundations results in inability to critically evaluate practical suggestions, which in turn leads to unsound decisions. Nothing could be more harmful to the design of schemes that need to withstand adversarial attacks than misconceptions about such attacks.


Frequently Asked Questions

Is there a solution manual of this book? Unfortunately, the answer is negative, but we believe that the guidelines for the exercises provide sufficient clues.

When will Volume 2 appear? It has appeared already (in May 2004).

Can Volume 1 (alone) be used for teaching? Yes, see teaching tips (above).

How does this book relate to the book Modern Cryptography, Probabilistic Proofs and Pseudorandomness? The current book is only remotely related to the former book, published in 1999 as part (i.e., Vol. 17) of the Algorithms and Combinatorics series of Springer: Chapter 1 of the Springer book provides a 30-page overview (or summary) to the current 800-page work. Chapters 2 and 3 of the Springer book provide a wider perspective on Probabilistic Proof systems and Pseudorandomness, respectively. An extensive treatment of the Cryptographically-related aspects of these areas is provided in the first volume of the current book (i.e., Volume 1), but the interested reader may benefit from the wider perspective offered in the Springer book.

How does this book relate to the book Computational Complexity: A Conceptual Perspective? Chapters 2-4 (of Volume 1) of the current book have a significant intersection with Chapters 7-9 of the complexity book, but the perspective taken in the two texts is different, and so is the selection of topics even within these chapters (e.g., pseudorandom functions, auxiliary-input zero-knowledge, and commitment schemes are not covered in the complexity book; on the other hand, other forms of hardness amplification, other types of pseudoranddom generators, and PCPs are not covered here).

See also answers to other frequently asked questions.


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