Foundations of Cryptography

The Foundations of Cryptography - Volume 1

Oded Goldreich

ISBN 0-521-79172-3
Published in US in June 2001.
See purchase information.
Publisher: Cambridge University Press
(see the publisher's page for this volume).

This volume is part of the two-volume work Foundations of Cryptography (see Volume 2).
For a brief introduction to the Foundations of Cryptography, see surveys.
For further suggestions regarding teaching, see notes. A preliminary draft is available here.

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

Preface

See preface to the entire work Foundations of Cryptography. We highlight the following points:

Cryptography is concerned with the construction of schemes that should maintain a desired functionality, even under malicious attempts aimed at making them deviate from it.
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.
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.
This work 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. This is done in a way independent of the particularities of some popular number theoretic examples.
- The most relevant background for this work 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.
Most of modern cryptography relies on the ability to generate instances of hard problems. Such ability is captured in the definition of one-way function.

Preface to the current volume

The current (first) volume consists of an introductory chapter (Chapter 1), followed by chapters on computational difficulty (one-way functions), pseudorandomness and zero-knowledge proofs (Chapters 2-4, respectively). Also included are two appendices: one of them providing a brief summary of Volume 2. The high-level structure of the current volume is as follows:

Chapter 1: Introduction
Chapter 2: Computational Difficulty (One-Way Functions)
Chapter 3: Pseudorandom Generators
Chapter 4: Zero-Knowledge Proofs
Appendix A: Brief Background on Computational Number Theory
Appendix B: Brief Outline of Volume 2
Bibliography and Index

Historical notes, suggestions for further reading, some open problems and some exercises are provided at the end of each chapter. The exercises are mostly designed to help and test the basic understanding of the main text, not to test or inspire creativity. The open problems are fairly well-known, still we recommend to check their current status (e.g., in this website).

Using this work

The work 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.

Teaching

(See also Teaching Notes.)

The material presented in this work 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 work 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, the current volume only covers the first half of the aforementioned material. The second half is covered in Volume 2.

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 the current volume. Lectures 16-28 will be covered by the second volume.

Lecture 1: Introduction, Background, etc (depending on class)
Lecture 2-5: Computational Difficulty (One-Way Functions)
Lecture 6-10: Pseudorandom Generators
Lecture 11-15: Zero-Knowledge Proofs
Lecture 16-20: Encryption Schemes
Lecture 21-24: Signature Schemes
Lecture 25-28: General Cryptographic Protocols

Giving a course solely based on the material that appears in the current volume 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).

Preface

Chapter 1: Introduction

1.1 Cryptography - Main Topics
1.2 Some Background from Probability Theory
1.3 The Computational Model
1.4 Motivation to the Rigorous Treatment
1.5 Miscellaneous

Chapter 2: Computational Difficulty

2.1 One-Way Functions: Motivation
2.2 One-Way Functions: Definitions
2.3 Weak One-Way Functions Imply Strong Ones
2.4 One-Way Functions: Variations
2.5 Hard-Core Predicates
2.6* Efficient Amplification of One-way Functions
2.7 Miscellaneous

Chapter 3: Pseudorandom Generators

3.1 Motivating Discussion
3.2 Computational Indistinguishability
3.3 Definitions of Pseudorandom Generators
3.4 Constructions based on One-Way Permutations
3.5* Constructions based on One-Way Functions
3.6 Pseudorandom Functions
3.7* Pseudorandom Permutations
3.8 Miscellaneous

Chapter 4: Zero-Knowledge Proof Systems

4.1 Zero-Knowledge Proofs: Motivation
4.2 Interactive Proof Systems
4.3 Zero-Knowledge Proofs: Definitions
4.4 Zero-Knowledge Proofs for NP

4.5* Negative Results
4.6* Witness Indistinguishability and Hiding
4.7* Proofs of Knowledge
4.8* Computationally-Sound Proofs (Arguments)
4.9* Constant-Round Zero-Knowledge Proofs
4.10* Non-Interactive Zero-Knowledge Proofs
4.11* Multi-Prover Zero-Knowledge Proofs
4.12 Miscellaneous

Appendix A: Background in Computational Number Theory

A.1 Prime Numbers
A.2 Composite Numbers

Appendix B: Brief Outline of Volume 2

B.1 Encryption - Brief Summary
B.2 Signatures - Brief Summary
B.3 Cryptographic Protocols - Brief Summary

Bibliography (approximately 200 entries)

Index (approximately 500 entries)

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, in Spring 2004.

Can Volume 1 (alone) be used for teaching? Yes, see teaching tips above. But this question seems less relevant today, since Volume 2 is available.

How does this volume relate to the book Modern Cryptography, Probabilistic Proofs and Pseudorandomness? The current volume 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 entire work, which holds 350 pages in its current (first) volume only. 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 current volume, but the interested reader may benefit from the wider perspective offered in the Springer book.

List of Corrections

For further details see Appendix C in Volume 2 (as well as a draft of the said appendix, Feb. 2003).

Unfortunately, we have to withdraw two claims regarding strong witness indistinguishable proofs as defined in Definition 4.6.2. Specifically, in general, strong witness indistinguishability is not closed under parallel composition (and so Lemma 4.6.7 is wrong). Consequently, in contrary to what is stated in Theorem 4.6.8, we do not know whether there exist constant-round public-coin proofs with negligible error that are strong witness indistinguishable for languages out of BPP. We stress that the flaws pointed out here only refer to strong witness indistinguishability and not to (regular) witness indistinguishability. That is, as stated in Lemma 4.6.6, (regular) witness indistinguishability is closed under parallel composition and thus the part of Theorem 4.6.8 that refers to regular witness indistinguishability is valid (i.e., providing constant-round public-coin proofs with negligible error that are witness indistinguishable for NP).
Remark 4.10.6 as well as Theorems 4.10.10, 4.10.14 and 4.10.16, seem to require trapdoor permutations in which the permutation's domain coincides with the set of all strings of certain length. This special case of Definition 2.4.5 can be implemented by modifying the RSA or the Factoring Trapdoors (cf. Canetti et al (in STOC'96) and [5]). For further detail on Remark 4.10.6, the reader is referred to [23]. Added comment (Nov. 2008): see note.
A recent result by Boaz Barak (see FOCS'01), calls for re-evaluation of the significance of all negative results regarding black-box zero-knowledge (cf. Definition 4.5.10). In particular, relying on standard intractability assumptions, Barak presents round-efficient public-coin zero-knowledge arguments for NP (using non-black-box simulators), whereas only BPP can have such black-box zero-knowledge arguments (cf. comment following Theorem 4.5.11). Interestingly, Barak's simulator works in strict (rather than expected) probabilistic polynomial-time, addressing an open problem mentioned in Section 4.12.3.
In Definition 4.10.15 (adaptive NIZK), the adaptive zero-knowledge condition (page 310) should relate only to input-selecting functions $\Xi$ that are implementable by a family of polynomial-size circuits.
Const. 4.10.7 and Prop. 4.10.9 (pp. 303-304): The current description in terms of two mappings $\pi_1,\pi_2$ is confusing and even inaccurate. Instead one should identify the row and columns of $H$ with $[n]$ and use one permuation/isomorphism $\pi$ of $G$ to $H$. Alternatively, one may compose this $\pi$ with the $\psi_i$'s (which results in $\pi_i$'s as in the text). [Luis von Ahn]
Definition 4.9.3 is carelessly written. One should partition the commit phase into two sub-phases, with the second sub-phase being a proof-of-knowledge referring to the view of the first sub-phase, which in turn should constitute a commitment scheme by itself. Alternatively, a Non-Oblivious Commitment may be defined as the sequential composition of an ordinary commitment scheme with a corresponding proof-of-knowledge such that the composed protocol is also a commitment scheme. [Yehuda Lindell]
Addition to Section 4.12.2: In continuation to Sections 4.7 and 4.9.2, we mention that the round-efficient argument system of [77] is actually an ``argument of knowledge'' (with negligible error).
Adding self-credits to Section 4.12.1: the notions of strong witness indistinguishability (Section 4.6) and strong proofs of knowledge (Section 4.7.6), and the Hidden Bit Model (Section 4.10.2) are due to (early versions of) this work.

The foregoing errors were corrected in Volume 2. More recent corrections and additions follow

There is a typo in the guideline given for Exercise 9 of Chapter 2: The suggestion should be $f(y,z)=(g(y),y\xor z)$.
There is a typo in the guideline given for Exercise 17 of Chapter 2: The statistical distance is stated at the end should by $O(2^{-\ell} + 2^{2\ell+2\log n}\cdot\epsilon)$.
There is a typo on page 46 (just before equation 2.7): N0 should be N'.
There is a typo in Exercise 28 of Chapter 3: The threshold value should be $2^ell \cdot ell$ (rather than $\ell^\ell$ as written).
At the end of Section 2.7.3, the question should refer to returning a constant fraction of the bits of $x$ (rather than the first half of $x$).
In continuation to Sec 2.4.2 and 2.4.4, see clarifications regarding one-way permutations, 2005.
In continuation to the definition of Proofs Of Knowledge (Sec 4.7.1), see discussion of Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge, 2006.
Section 2.5.3 does not provide a good analysis of the security of hard-core functions. A better analysis is provided HERE.
A recent work of Nguyen, Ong, and Vadhan (see 47th FOCS, 2006) provides statistical zero-knowledge arguments for NP from any one-way function. This resolves a central open problem in the area (also mentioned in Sec. 4.12.3).
The specific expression given for Chernoff Bound (in Sec 1.2.2, page 11) may be wrong. The exponent should be either $-(\epsilon^2/(4p(1-p)))\cdot n$ (i.e., a factor of two smaller than stated) or $-2\epsilon^2\cdot n$. (Both alternatives are correct, but one usually sees the latter.) [Kivanc Mihcak]
Typo in page 99 line 3 (Exer 28 in Chap 2): the reference should be to [204] not [203].

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