The Foundations of Cryptography  Volume 1
Oded Goldreich


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.
The design of cryptographic systems has to be based on firm foundations;
whereas adhoc 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''.
The emphasis of the work is on the clarification of fundamental concepts
and on demonstrating the feasibility of solving several central
cryptographic problems.
The current book is the first volume of this work, and it focuses
on the main tools of Modern Cryptography: computational difficulty
(oneway functions), pseudorandomness and zeroknowledge proofs.
The next volume will focus on the main applications of Cryptography:
encryption schemes, signature schemes and secure protocols.
ISBN 0521791723
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 twovolume 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 adhoc 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 oneway function.
Preface to the current volume
The current (first) volume consists of an introductory chapter
(Chapter 1), followed by
chapters on computational difficulty (oneway functions),
pseudorandomness and zeroknowledge proofs
(Chapters 24, respectively).
Also included are two appendices:
one of them providing a brief summary
of Volume 2.
The highlevel structure of the current volume is as follows:
 Chapter 1: Introduction
Main Topics covered by the work (Sec. 1.1)
Background on Probability and Computation (Sec. 1.2 and 1.3)
Motivation to the Rigorous Treatment (Sec. 1.4)
 Chapter 2: Computational Difficulty (OneWay Functions)
Motivation and Definitions (Sec. 2.1 and 2.2)
OneWay functions: Weak implies Strong (Sec. 2.3)
Variants (Sec. 2.4) and advanced material (Sec. 2.6)
HardCore Predicates (Sec. 2.5)
 Chapter 3: Pseudorandom Generators
Motivation and Definitions (Sec. 3.13.3)
Constructions based on OneWay Permutations (Sec. 3.4)
Pseudorandom Functions (Sec. 3.6)
Advanced material (Sec. 3.5 and 3.7)
 Chapter 4: ZeroKnowledge Proofs
Motivation and Definitions (Sec. 4.14.3)
ZeroKnowledge Proofs for NP (Sec. 4.4)
Advanced material (Sec. 4.54.11)
 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 wellknown,
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 CSundergraduate 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 highlevel sketch of the main ideas,
and only later pass to the technical details.
Passage from highlevel 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 onesemester 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 twosemester 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 onesemester course on Foundations of Cryptography.
Each lecture consists of one hour.
Lectures 115 are covered by the current volume.
Lectures 1628 will be covered by
the second volume.
 Lecture 1: Introduction, Background, etc (depending on class)
 Lecture 25: Computational Difficulty (OneWay Functions)
Main: Definition (Sec. 2.2), HardCore Predicates (Sec. 2.5)
Optional: Weak implies Strong (Sec. 2.3), and Sec. 2.4.22.4.4
 Lecture 610: Pseudorandom Generators
Main: Definitional issues and a construction (Sec. 3.23.4)
Optional: Pseudorandom Functions (Sec. 3.6)
 Lecture 1115: ZeroKnowledge Proofs
Main: Some definitions and a construction
(Sec. 4.2.1, 4.3.1, 4.4.14.4.3)
Optional: Sec. 4.2.2, 4.3.2, 4.3.34.3.4, 4.4.4
 Lecture 1620: Encryption Schemes
 Lecture 2124: Signature Schemes
 Lecture 2528: General Cryptographic Protocols
The definitional approach and a general construction (sketches).
(Consult Apdx. B.3, see also our exposition.)
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 standalone course in Cryptography
(for the reason that the current volume does not consider at all
the basic tasks of encryption and signatures).
Table of Contents
Preface
Chapter 1: Introduction

1.1 Cryptography  Main Topics
1.1.1 Encryption Schemes
1.1.2 Pseudorandom Generators
1.1.3 Digital Signatures
1.1.4 FaultTolerant Protocols and ZeroKnowledge Proofs

1.2 Some Background from Probability Theory
1.2.1 Notational Conventions
1.2.2 Three Inequalities

1.3 The Computational Model
1.3.1 P, NP, and NPcompleteness
1.3.2 Probabilistic PolynomialTime
1.3.3 NonUniform PolynomialTime
1.3.4 Intractability Assumptions
1.3.5 Oracle Machines

1.4 Motivation to the Rigorous Treatment
1.4.1 The Need for a Rigorous Treatment
1.4.2 Practical Consequences of the Rigorous Treatment
1.4.3 The Tendency to be Conservative

1.5 Miscellaneous
1.5.1 Historical Notes
1.5.2 Suggestion for Further Reading
1.5.3 Open Problem
1.5.4 Exercises
Chapter 2: Computational Difficulty

2.1 OneWay Functions: Motivation

2.2 OneWay Functions: Definitions
2.2.1 Strong OneWay Functions
2.2.2 Weak OneWay Functions
2.2.3 Two Useful Length Conventions
2.2.4 Candidates for OneWay Functions
2.2.5 NonUniformly OneWay Functions

2.3 Weak OneWay Functions Imply Strong Ones
2.3.1 The Construction and its Analysis
2.3.2 Illustration by a toy example
2.3.3 Discussion

2.4 OneWay Functions: Variations
2.4.1* Universal OneWay Function
2.4.2 OneWay Functions as Collections
2.4.3 Examples of Oneway Collections (RSA, Factoring, DLP)
2.4.4 Trapdoor oneway permutations
2.4.5* Clawfree Functions
2.4.6* On Proposing Candidates

2.5 HardCore Predicates
2.5.1 Definition
2.5.2 HardCore Predicates for any OneWay Function
2.5.3* HardCore Functions

2.6* Efficient Amplification of Oneway Functions

2.7 Miscellaneous
2.7.1 Historical Notes
2.7.2 Suggestion for Further Reading
2.7.3 Open Problems
2.7.4 Exercises
Chapter 3: Pseudorandom Generators

3.1 Motivating Discussion
3.1.1 Computational Approaches to Randomness
3.1.2 A Rigorous Approach to Pseudorandom Generators

3.2 Computational Indistinguishability
3.2.1 Definition
3.2.2 Relation to Statistical Closeness
3.2.3 Indistinguishability by Repeated Experiments
3.2.4* Indistinguishability by Circuits
3.2.5 Pseudorandom Ensembles

3.3 Definitions of Pseudorandom Generators
3.3.1 Standard Definition of Pseudorandom Generators
3.3.2 Increasing the Expansion Factor
3.3.3* Variableoutput pseudorandom generators
3.3.4 The Applicability of Pseudorandom Generators
3.3.5 Pseudorandomness and unpredictability
3.3.6 Pseudorandom Generators imply OneWay Functions

3.4 Constructions based on OneWay Permutations
3.4.1 Construction based on a Single Permutation
3.4.2 Construction based on Collections of Permutations
3.4.3* Using HardCore Functions rather than Predicates

3.5* Constructions based on OneWay Functions
3.5.1 Using 11 OneWay Functions
3.5.2 Using Regular OneWay Functions
3.5.3 Going beyond Regular OneWay Functions

3.6 Pseudorandom Functions
3.6.1 Definitions
3.6.2 Construction
3.6.3 Applications  A general methodology
3.6.4 Generalization

3.7* Pseudorandom Permutations
3.7.1 Definitions
3.7.2 Construction

3.8 Miscellaneous
3.8.1 Historical Notes
3.8.2 Suggestion for Further Reading
3.8.3 Open Problems
3.8.4 Exercises
Chapter 4: ZeroKnowledge Proof Systems

4.1 ZeroKnowledge Proofs: Motivation
4.1.1 The Notion of a Proof
4.1.2 Gaining Knowledge

4.2 Interactive Proof Systems
4.2.1 Definition
4.2.2 An Example (Graph NonIsomorphism in IP)
4.2.3* The Structure of the Class IP
4.2.4 Augmentation to the Model

4.3 ZeroKnowledge Proofs: Definitions
4.3.1 Perfect and Computational ZeroKnowledge
4.3.2 An Example (Graph Isomorphism in PZK)
4.3.3 ZeroKnowledge w.r.t. Auxiliary Inputs
4.3.4 Sequential Composition of ZeroKnowledge Proofs

4.4 ZeroKnowledge Proofs for NP
4.4.1 Commitment Schemes
4.4.2 ZeroKnowledge Proof of Graph Coloring
4.4.3 The General Result and Some Applications
4.4.4 Second Level Considerations

4.5* Negative Results
4.5.1 On the importance of interaction and randomness
4.5.2 Limitations of unconditional results
4.5.3 Limitations of Statistical ZK proofs
4.5.4 ZeroKnowledge and Parallel Composition

4.6* Witness Indistinguishability and Hiding
4.6.1 Definitions
4.6.2 Parallel Composition
4.6.3 Constructions
4.6.4 Applications

4.7* Proofs of Knowledge
4.7.1 Definition
4.7.2 Reducing the knowledge error
4.7.3 ZeroKnowledge Proofs of Knowledge for NP
4.7.4 Applications
4.7.5 Proofs of Identity (Identification schemes)
4.7.6 Strong Proofs of Knowledge

4.8* ComputationallySound Proofs (Arguments)
4.8.1 Definition
4.8.2 PerfectlyHiding Commitment Schemes
4.8.3 Perfect ZeroKnowledge Arguments for NP
4.8.4 Arguments of Polylogarithmic Efficiency

4.9* ConstantRound ZeroKnowledge Proofs
4.9.1 Using commitment schemes with perfect secrecy
4.9.2 Bounding the power of cheating provers

4.10* NonInteractive ZeroKnowledge Proofs
4.10.1 Basic Definitions
4.10.2 Constructions
4.10.3 Extensions

4.11* MultiProver ZeroKnowledge Proofs
4.11.1 Definitions
4.11.2 TwoSenders Commitment Schemes
4.11.3 Perfect ZeroKnowledge for NP
4.11.4 Applications

4.12 Miscellaneous
4.12.1 Historical Notes
4.12.2 Suggestion for Further Reading
4.12.3 Open Problems
4.12.4 Exercises
Appendix A: Background in Computational Number Theory

A.1 Prime Numbers
A.1.1 Quadratic residues modulo a prime
A.1.2 Extracting square roots modulo a prime
A.1.3 Primality testers
A.1.4 On uniform selection of primes

A.2 Composite Numbers
A.2.1 Quadratic residues modulo a composite
A.2.2 Extracting square roots modulo a composite
A.2.3 The Legendre and Jacobi Symbols
A.2.4 Blum Integers and their quadratic residue structure
Appendix B: Brief Outline of Volume 2

B.1 Encryption  Brief Summary
B.1.1 Definitions
B.1.2 Constructions
B.1.3 Beyond eavesdropping security
B.1.4 Some Suggestions

B.2 Signatures  Brief Summary
B.2.1 Definitions
B.2.2 Constructions
B.2.3 Some Suggestions

B.3 Cryptographic Protocols  Brief Summary
B.3.1 Definitions
B.3.2 Constructions
B.3.3 Some Suggestions
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 30page 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 Cryptographicallyrelated 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.
See also
answers to other frequently asked questions.
List of Corrections
The following errors were corrected in Volume 2;
for further details see Appendix C (of 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 constantround
publiccoin 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 constantround
publiccoin 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):
Unfortunately, the correction that appeared in
Appendix C of Volume 2 is also incorrect.
For details see
note
(or better its
revision).
For a discussion of enhanced trapdoor permutations
see my paper with Ron Rothblum
titled Enhancements of Trapdoor Permutations.
 Not exactly an error, yet a recent result by Boaz Barak (see FOCS'01)
calls for reevaluation of the significance of all negative
results regarding blackbox zeroknowledge (cf. Definition 4.5.10).
In particular, relying on standard intractability assumptions,
Barak presents roundefficient publiccoin
zeroknowledge arguments for NP (using nonblackbox simulators),
whereas only BPP can have such blackbox zeroknowledge arguments
(cf. comment following Theorem 4.5.11).
Interestingly, Barak's simulator works in strict (rather than expected)
probabilistic polynomialtime, addressing an open problem
mentioned in Section 4.12.3.
 In Definition 4.10.15 (adaptive NIZK),
the adaptive zeroknowledge condition (page 310) should relate
only to inputselecting functions $\Xi$
that are implementable by a family of polynomialsize circuits.
 Const. 4.10.7 and Prop. 4.10.9 (pp. 303304):
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 subphases, with the second subphase being a proofofknowledge
referring to the view of the first subphase, which in turn should
constitute a commitment scheme by itself.
Alternatively, a NonOblivious Commitment may be defined as
the sequential composition of an ordinary commitment scheme with
a corresponding proofofknowledge
such that the composed protocol is also a commitment scheme.
[Yehuda Lindell]
 The proof of Theorem 4.9.4 is wrong, since it relies
on the existence of constantround strong witness indistinguishability
proofs of knowledge for NP (i.e., Theorem 4.6.8).
Fortunately, an alternative proof exists
(see Apdx C.3.3 in Volume 2).
 Addition to Section 4.12.2: In continuation to Sections 4.7 and 4.9.2,
we mention that the roundefficient argument system of [77] is
actually an ``argument of knowledge'' (with negligible error).
 Adding selfcredits 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

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(1p)))\cdot n$
(i.e., a factor of two smaller than stated)
or just $2\epsilon^2\cdot n$.
(Both alternatives are correct, but one usually sees the latter.)
[Kivanc Mihcak]
 Typo on page 35, 2nd paragraph:
It should be $\nu(n) > 1/p(n)$.
[Eldad Zinger]
 There is a typo on page 46 (just before equation 2.7):
N0 should be N'.
 Formally speaking, Prop. 2.4.1 (as stated) is trivial.
The statement asserts that there exists a polytime computable $f$
such that $f$ is a OWF iff OWF exist.
But, as pointed out by Claus Diem, if OWF exist then one may use $f$
as any of them, and otherwiose one may use any polytime computable $f$.
Of course, what I meant was that one can specify a polytime computable $f$
without knowing if OWF exist or not, but this is not captured by the
formal statement. Of course, one way out is to describe $f$ first,
and then make the claim about this $f$; but, for obvious reasons,
I did not want to do that.
 In continuation to Sec 2.4.2 and 2.4.4,
see clarifications
regarding oneway permutations, 2005.
 The lower bound (on the size of $S_n$) in Claim 2.5.2.1
can be improved to $\epsilon(n)\cdot 2^n$.
See details
HERE.
[Noam Livne]
 Section 2.5.3 does not provide the best analysis of the
security of hardcore functions. A better analysis is provided
HERE.
 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$).
 The presentation in Section 2.6.2 contains a (fixable) error.
The graph $G_{f,n}$ defined on page 82 is a directed graph,
and the construction of the function $F$ (Construction 2.6.3)
refers to directed walks on it. But Lemma 2.6.5 refers to
undirected graphs and hence cannot be applied to it. [Qifu Hu]
Nevertheless, the weaker bound provided in the proof of
Lemma 2.6.5 holds also in this case. Specifically,
consider the stochastic process captured by the matrix $M_f$
such that $M_f =MR$, where $M$ is the normalized adjacency
matrix of the graph $G_n$ and $R$ is the permutation matrix
that corresponds to the mapping $x\mapsto f(x)$.
Now we want to bound $\(PMR)^t z\$
and we do it by bounding $\PMR z\$,
which reduces to bounding $\PMz'\$ for $z'=Rz$
(while noting that $Rz$ and $z$ have the same norm).
Hence, we obtain a bound of $1(10.5\mu)^{t/2}$,
rather than $1(10.5\mu)^{t}$,
and this is the bound we should use for $\beta(n)$
(with $t=k(n)/\ell$) when we invoke Lemma 2.6.6.
This means that we establish the corresponding
bound of with $\beta(n)=1(10.5\alpha(n))^{k(n)/2\ell}$
also in Prop. 2.6.4 (i.e., we lose a factor of two in the exponent).
Note, however, that the above analysis presumes that
$\mu \geq 2\rho^2$, where $\rho$ is an upper bound
on the eigenvalue ratio. This is fine when applying
Lemma 2.6.6 with a constant value of $\alpha$,
but for smaller values we have to use an expander
of degree $d=\poly(1/\alpha)$ and a polynomially
related expansion bound (where such an expander
can be obtained by talking a walk of length $\log d$
on a constantdegree expander).
This in turn means that $\ell=O(\log(1/\alpha))$
and that we can only use $k(n)=O(n/\ell)$ in Prop 2.6.4
(in order to maintain $n+k(n)\log d = O(n)$).
This only means that in the first applications
of Prop 2.6.4 (within the proof of Thm 2.6.2),
we only increase the hardness parameter by
a factor of $n/\log n$ (rather than by $n$).
That is, starting with an $n^{\delta}$OWP,
for $i\in[\delta]$, after $i$ iterations
we derive an $(n^{(\deltai)}/(\log n)^i)$OWP,
and in the last (i.e., $\delta+1$st) iteration
we obtain a string oneway function
(since $1(1(1/\poly\log n))^{n/\log n}$ is negligible).
I'm currently unsure if the original claim
(i.e., with Lemma 2.6.5 applied to the directed graph $G_{f,n}$)
is true, but it does not matter much.
 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)$.
 Typo in page 99 line 3 (Exer 28 in Chap 2):
the reference should be to [204] not [203].
 Prop. 3.3.8 (on page 124) can be extended to all pseudorandom
generators $G$ of arbitrary stretch $ell(n)$, yielding a strong OWF
if $\ell(n)n=\omega(\log n))$ and a weak OWF otherwise.
This follows by observing that for any subset $S$ of the image of $G$
(or rather the image of $n$bit long seeds under $G$),
it holds that $prob[G(U_n)\in S] \geq \frac{S}{2^n}$
whereas
$prob[U_{ell(n)}\in S] = \frac{S}(2^{ell(n)}} \leq \frac{S}(2^{n+1}}$.
[Guang Yang]
 The sampling procedure referred to at the end of Sec 3.4.2
is not as obvious; the $O(n^3)$ bound relies on the fact
that the expected number of candidates to be tried is $O(n)$.
[Qifu Hu]
 Sec. 3.5.1.2 (on page 138), right after Prop 3.5.3,
contains a typo: $k$ should be set to $O(p(n))$, not to $n$. [Qifu Hu]
 Typo on page 142 (last sentence of 2nd paragraph):
It should be $m$ not $i$. [Qifu Hu]
 Typo on page 143 (1st paragraph of the proof of Prop 3.5.9):
The 3rd sentence should have been
``Thus, for every $y$ and $\alpha$, it holds that
$\pr[F^{1}(y,\alpha,H_{n}^{m(n)l(n)}) >2^{l(n)+1}] < 2^{l(n)}$.''
and the rest of this paragraph should have referred to
$B_y=\{(\alpha,h):F^{1}(y,\alpha,h) \!>\!2^{l(n)+1}\}$.
[Qifu Hu]
 Sec. 3.5.3 (on page 147) contains an error.
The number of copies should be $n^3$, not $n^2$.
In all expressions in Sec. 3.5.3, $n^2$ should be replaced by $n^3$,
and $n^3$ by $n^4$. [Yu Yu]
 Unfortunately, Theorem 3.5.12 (i.e., OWF implies PRGs)
still does not have an easy proof (i.e., one suitable for a textbook).
But proofs are getting easier and better.
Currently, the most readerfriendly proof can be found in
Efficiency Improvements in
Constructing Pseudorandom Generators from Oneway Functions
(by Iftach Haitner, Omer Reingold, and Salil Vadhan).
 Typo on page 155 at the beginning of the proof of Claim 3.6.6.1.
The queries in the simple case should be the reverses of the
first $t$ strings in lexorder; that is, for $t=2^{k+1}$, we
use strings of the form $x'0^{nk1}$, where $x\in\{0,1\}^{k+1}$.
[Qifu Hu]
 Typo on page 156 line 12: The text should read
"In fact, g(p_i)=g(p_j)=v_i=v_j also in case p_i \neq p_j"
(i.e., inequality rather than equality). [Qifu Hu]
 Typo on Page 163, in the displaced definition of $f$:
In the otherwisecase, one should replace $G_{\sigma_{k+1}}$
by $P_{\sigma_{k+1}}$, where $P_0(s)$ (resp., $P_1(s)$) is defined
as the first $n$ bits of $s$ (resp., the next $n$ bits of $s$),
just as in the proof of Thm 3.6.6.
[Qifu Hu]
 The definitions in Sec 3.6.1 fail to require that
the function $\ell$ is upper bounded by a polynomial.
Furthermore, they also fair to require that $\ell$
is efficiently computible (i.e., $\ell(n)$ can be
compurted in $\poly(n)$time when given $n$).
[Dima Kogan and Inbal Livni]
Both conditions are not used in the text,
but I agree that it is a good idea to impose them both.
I tend to insert these conditions into Def 3.6.1
and the preamble of Def 3.6.4.
Alternatively, it may be inserted into Def 3.6.3
and the first item of Def 3.6.4.
 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).
 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.
 Thm 4.4.11 fails to clarify that this result holds
for any NPwitness relation,
and not merely for any NPset [Roei Tell].
Likewise, in Def 4.3.10,
it would have been better to define (efficient) zeroknowledge
interactive proofs for any relation $R$ rather than refer
to the set of strings $P_L(x)$ that satisfy completenss.
In such case, the completeness and zeroknowledge conditions
should hold for any $(x,y)\in R$
(rather than for every $x\in L$ and $y\in P_L(x)$),
for any $R$ such that $L$ contains all $x$'s
for which there exists a $y$ such that $(x,y)\in $R$.
 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]).
As stated above, the correction that appeared in
Appendix C of Volume 2 is also incorrect.
For details see
note.
 In Construction 4.10.12, it seems better to use the symbol $u'$
(in the definition of $L_2$) instead of $w'$.
The point is to streamline better with the proof of Proposition 4.10.13.
 A recent work of Nguyen, Ong, and Vadhan (see 47th FOCS, 2006) provides
statistical zeroknowledge arguments for NP from any oneway function.
This resolves a central open problem in the area
(also mentioned in Sec. 4.12.3).
See also a followup work by Haitner and Reingold (see 39th STOC, 2007)
providing statistical hiding commitment schemes.
Back to
the top or to
Oded Goldreich's homepage.