Request Inspection Copy

If you are an Academic or Teacher and wish to consider this book as a prescribed textbook for your course, you may be eligible for a complimentary inspection copy. Please complete this form, including information about your position, campus and course, before adding to cart.

* Required Fields

To complete your Inspection Copy Request you will need to click the Checkout button in the right margin and complete the checkout formalities. You can include Inspection Copies and purchased items in the same shopping cart, see our Inspection Copy terms for further information.

Any Questions? Please email our text Support Team on text@footprint.com.au

Submit

Email this to a friend

* ALL required Fields

Order Inspection Copy

An inspection copy has been added to your shopping cart

Pseudorandomness and Cryptographic Applications (POD)

by Michael Luby Princeton University Press
Pub Date:
01/1996
ISBN:
9780691025469
Format:
Pbk 248 pages
Price:
AU$176.00 NZ$180.00
Product Status: Available in Approx 5 days
add to your cart
A pseudorandom generator is an easy-to-compute function that stretches a short random string into a much longer string that 'looks' just like a random string to any efficient adversary. One immediate application of a pseudorandom generator is the construction of a private key cryptosystem that is secure against chosen plaintext attack. There do not seem to be natural examples of functions that are pseudorandom generators. On the other hand, there do seem to be a variety of natural examples of another basic primitive: the one-way function. A function is one-way if it is easy to compute but hard for any efficient adversary to invert on average. The first half of the book shows how to construct a pseudorandom generator from any one-way function. Building on this, the second half of the book shows how to construct other useful cryptographic primitives, such as private key cryptosystems, pseudorandom function generators, pseudorandom permutation generators, digital signature schemes, bit commitment protocols, and zero-knowledge interactive proof systems. The book stresses rigorous definitions and proofs.


Overview and Usage Guide ix

Mini-Courses xiii

Acknowledgments 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.

Lecture 1 Introduction to private key cryptosystems, pseudorandom generators, one-way functions. Introduction of some specific conjectured one-way functions. 13

Lecture 2 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. 21

Lecture 3 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. 35

Lecture 4 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. 49

Lecture 5 Introduction of a two part paradigm for derandornizing probabilistic algorithms. Two problems are used to exemplify this approach: witness sampling and vertex partitioning. 56

Lecture 6 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.

Lecture 7 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.

Lecture 8 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. 79

Lecture 9 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. 88

Lecture 10 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. 95

Lecture 11 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. 105

Lecture 12 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. 117

Lecture 13 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. 128

Lecture 14 Construction of a pseudorandom invertible permutation generator from a pseudorandom function generator. Definition and construction of a super pseudorandom invertible permutation generator. Applications to block private key cryptosystems. 138

Lecture 15 Definition of trapdoor one-way functions, specific examples, and construction of cryptosystems without initial communication using a private line. 146

Lecture 16 Definition and construction of a universal one-way hash function. 154

Lecture 17 Definition and construction of secure one bit and many bit signature schemes. 162

Lecture 18 Definition of interactive proofs IP and the zero knowledge restriction of this class ZKIP. Definition and construction of a hidden bit commitment scheme based on a one-way function. Construction of a ZKIP for all NP based on a hidden bit commitment scheme. 174

List of Exercises and Research Problems 185

List of Primary Results 195

Credits and History 199

References 211

Notation 221

Index 225


Michael Luby is the Leader of the Theory Group and a Research Scientist at the International Computer Science Institute in Berkeley, California. He is also an Adjunct Professor in the Computer Science Division at the University of California, Berkeley.