Overview and Usage Guide | p. ix |
Mini-Courses | p. xiii |
Acknowledgments | p. xv |
Preliminaries 3 | |
Introduction of some basic notation that is used in all subsequent lectures | |
Review of some computational complexity classes | |
Description of some useful probability facts | |
Introduction to private key cryptosystems, pseudorandom generators, One-way functions | |
Introduction of some specific conjectured One-way functions | p. 13 |
Discussions of security issues associated with the computing environment of a party, including the security parameter of a protocol | |
Definition of an adversary, the achievement ratio of an adversary for a protocol, and the security of a protocol | |
Definitions of One-way functions and One-way permutations, and cryptographic reduction | p. 21 |
Definition of a weak One-way function | |
Reduction from a weak Oneway function to a One-way function | |
More efficient security preserving reductions from a weak One-way permutation to a One-way permutation | p. 35 |
Proof that the discrete log problem is either a One-way permutation or not even weak One-way permutation via random self-reducibility | |
Definition of a pseudorandom generator, the next bit test, and the proof that the Two definitions are equivalent | |
Construction of a pseudorandom generator that stretches by a polynomial amount from a pseudorandom generator that stretches by One bit | p. 49 |
Introduction of a Two part paradigm for derandornizing probabilistic algorithms | |
Two problems are used to exemplify this approach: witness sampling and vertex partitioning | p. 56 |
Definition of inner product bit for a function and what it means to be a hidden bit | |
Description and proof of the Hidden Bit Theorem that shows the inner product bit is hidden for a One-way function | |
Definitions of statistical measures of distance between probability distributions and the analogous computational measures | |
Restatement of the, Hidden Bit Theorem in these terms and application of this theorem to construct a pseudorandom generator from a One-way permutation | |
Description and proof of the Many Hidden Bits Theorem that shows many inner product bit are hidden for a One-way function | |
Definitions of various notions of statistical entropy, computational entropy and pseudoentropy generators | |
Definition of universal hash Functions | |
Description and proof of the Smoothing Entropy Theorem | p. 79 |
Reduction from a One-way One-to-One function to a pseudorandom generator using the Smoothing Entropy Theorem and the Hidden Bit Theorem | |
Reduction from a One-way regular function to a pseudorandom generator using the Smoothing Entropy Theorem and Many Hidden Bits Theorem | p. 88 |
Definition of a false entropy generator | |
Construction and proof of a pseudorandom generator from a false entropy generator | |
Construction and proof of a false entropy generator from any One-way function in the non- uniform sense | p. 95 |
Definition of a stream private key cryptosystem, definitions of several notions of security, including passive attack and chosen plaintext | |
attack, and design of a stream private key cryptosystern that is secure against these attacks based on a pseudorandom generator | p. 105 |
Definitions and motivation for a block cryptosystern and security against chosen plaintext attack | |
Definition and construction of a pseudorandom function generator from a pseudorandom generator | |
Construction of a block private key cryptosystern secure against chosen plaintext attack based on a pseudorandom function generator | p. 117 |
Discussion of the Data Encryption Standard | |
Definition of a pseudorandom invertible permutation generator and discussion of applications to the construction of a block private key cryptosystern secure against chosen plaintext attack | |
Construction of a perfect random permutation based on a perfect random function | p. 128 |
Construction of a pseudorandom invertible permut | |
Table of Contents provided by Publisher. All Rights Reserved. |