Oded Goldreich

Foundations of Cryptography (Fragments of a Book)

1 Introduction [11]

1.1 Cryptography - Main Topics [11]

1.1.1 Encryption Schemes [11]

1.1.2 Pseudorandom Generators [13]

1.1.3 Digital Signatures [14]

1.1.4 Fault-Tolerant Protocols and Zero-Knowledge Proofs [16]

1.2 Some Background from Probability Theory [18]

1.2.1 Notational Conventions [18]

1.2.2 Three Inequalities [19]

1.3 The Computational Model [23]

1.3.1 P, NP, and NP-completeness [23]

1.3.2 Probabilistic Polynomial-Time [24]

1.3.3 Non-Uniform Polynomial-Time [27]

1.3.4 Intractability Assumptions [29]

1.3.5 Oracle Machines [30]

1.4 Motivation to the Formal Treatment [31]

1.4.1 The Need to Formalize Intuition [31]

1.4.2 The Practical Consequences of the Formal Treatment [32]

1.4.3 The Tendency to be Conservative [33]

2 Computational Difficulty [35]

2.1 One-Way Functions: Motivation [35]

2.2 One-Way Functions: Definitions [36]

2.2.1 Strong One-Way Functions [36]

2.2.2 Weak One-Way Functions [38]

2.2.3 Two Useful Length Conventions [39]

2.2.4 Candidates for One-Way Functions [42]

2.2.5 Non-Uniformly One-Way Functions [44]

2.3 Weak One-Way Functions Imply Strong Ones [45]

2.4 One-Way Functions: Variations [51]

2.4.1 * Universal One-Way Function [51]

2.4.2 One-Way Functions as Collections [52]

2.4.3 Examples of One-way Collections (RSA, Factoring, DLP) [54]

2.4.4 Trapdoor one-way permutations [57]

2.4.5 * Clawfree Functions [58]

2.4.6 On Proposing Candidates [61]

2.5 Hard-Core Predicates [61]

2.5.1 Definition [62]

2.5.2 Hard-Core Predicates for any One-Way Function [63]

2.5.3 * Hard-Core Functions [67]

2.6* Efficient Amplification of One-way Functions [70]

2.7 Miscellaneous [76]

2.7.1 Historical Notes [76]

2.7.2 Suggestion for Further Reading [77]

2.7.3 Open Problems [78]

2.7.4 Exercises [78]

3 Pseudorandom Generators [85]

3.1 Motivating Discussion [85]

3.1.1 Computational Approaches to Randomness [85]

3.1.2 A Rigorous Approach to Pseudorandom Generators [86]

3.2 Computational Indistinguishability [87]

3.2.1 Definition [87]

3.2.2 Relation to Statistical Closeness [89]

3.2.3 Indistinguishability by Repeated Experiments [90]

3.2.4 Pseudorandom Ensembles [94]

3.3 Definitions of Pseudorandom Generators [94]

3.3.1 * A General Definition of Pseudorandom Generators [95]

3.3.2 Standard Definition of Pseudorandom Generators [96]

3.3.3 Increasing the Expansion Factor of Pseudorandom Generators [96]

3.3.4 The Significance of Pseudorandom Generators [100]

3.3.5 A Necessary Condition for the Existence of Pseudorandom Generators [101]

3.4 Constructions based on One-Way Permutations [102]

3.4.1 Construction based on a Single Permutation [102]

3.4.2 Construction based on Collections of Permutations [104]

3.4.3 Practical Constructions [106]

3.5 * Construction based on One-Way Functions [106]

3.5.1 Using 1-1 One-Way Functions [106]

3.5.2 Using Regular One-Way Functions [112]

3.5.3 Going beyond Regular One-Way Functions [117]

3.6 Pseudorandom Functions [118]

3.6.1 Definitions [118]

3.6.2 Construction [120]

3.7* Pseudorandom Permutations [125]

3.7.1 Definitions [125]

3.7.2 Construction [127]

3.8 Miscellaneous [130]

3.8.1 Historical Notes [130]

3.8.2 Suggestion for Further Reading [131]

3.8.3 Open Problems [132]

3.8.4 Exercises [132]

4 Encryption Schemes [139]

5 Digital Signatures and Message Authentication [141]

6 Zero-Knowledge Proof Systems [143]

6.1 Zero-Knowledge Proofs: Motivation [143]

6.1.1 The Notion of a Proof [144]

6.1.2 Gaining Knowledge [146]

6.2 Interactive Proof Systems [148]

6.2.1 Definition [148]

6.2.2 An Example (Graph Non-Isomorphism in IP) [153]

6.2.3 Augmentation to the Model [156]

6.3 Zero-Knowledge Proofs: Definitions [157]

6.3.1 Perfect and Computational Zero-Knowledge [157]

6.3.2 An Example (Graph Isomorphism in PZK) [162]

6.3.3 Zero-Knowledge w.r.t. Auxiliary Inputs [167]

6.3.4 Sequential Composition of Zero-Knowledge Proofs [169]

6.4 Zero-Knowledge Proofs for NP [175]

6.4.1 Commitment Schemes [175]

6.4.2 Zero-Knowledge proof of Graph Coloring [180]

6.4.3 The General Result and Some Applications [191]

6.4.4 Efficiency Considerations [194]

6.5 * Negative Results [196]

6.5.1 Implausibility of an Unconditional ``NP in ZK'' Result [197]

6.5.2 Implausibility of Perfect Zero-Knowledge proofs for all of NP [198]

6.5.3 Zero-Knowledge and Parallel Composition [199]

6.6* Witness Indistinguishability and Hiding [202]

6.6.1 Definitions [202]

6.6.2 Parallel Composition [205]

6.6.3 Constructions [206]

6.6.4 Applications [208]

6.7* Proofs of Knowledge [208]

6.7.1 Definition [209]

6.7.2 Observations [211]

6.7.3 Applications [212]

6.7.4 Proofs of Identity (Identification schemes) [213]

6.8* Computationally-Sound Proofs (Arguments) [217]

6.8.1 Definition [218]

6.8.2 Perfect Commitment Schemes [219]

6.8.3 Perfect Zero-Knowledge Arguments for NP [225]

6.8.4 Zero-Knowledge Arguments of Polylogarithmic Efficiency [227]

6.9* Constant Round Zero-Knowledge Proofs [228]

6.9.1 Using commitment schemes with perfect secrecy [230]

6.9.2 Bounding the power of cheating provers [234]

6.10* Non-Interactive Zero-Knowledge Proofs [237]

6.10.1 Definition [237]

6.10.2 Construction [237]

6.11* Multi-Prover Zero-Knowledge Proofs [237]

6.11.1 Definitions [238]

6.11.2 Two-Senders Commitment Schemes [240]

6.11.3 Perfect Zero-Knowledge for NP [244]

6.11.4 Applications [246]

6.12 Miscellaneous [247]

6.12.1 Historical Notes [247]

6.12.2 Suggestion for Further Reading [249]

6.12.3 Open Problems [250]

6.12.4 Exercises [250]

7 Cryptographic Protocols [255]

8* New Frontiers [257]

9 The Effect of Cryptography on Complexity Theory [259]

10* Related Topics [261]

A Annotated List of References (compiled Feb. 1989) [263]

A.1 General [269]

A.2 Hard Computational Problems [269]

A.3 Encryption [272]

A.4 Pseudorandomness [273]

A.5 Signatures and Commitment Schemes [275]

A.6 Interactive Proofs, Zero-Knowledge and Protocols [276]

A.7 Additional Topics [285]

A.8 Historical Background [290]