Pseudorandomness (expositions by Oded Goldreich)

Surveys on Pseudorandomness and Computational Indistingushability

by Oded Goldreich

A fresh view at the question of randomness was taken in the theory of computing: It has been postulated that a distribution is pseudorandom if it cannot be told apart from the uniform distribution by any efficient procedure. This paradigm, originally associating efficient procedures with polynomial-time algorithms, has been applied also with respect to a variety of limited classes of such distinguishing procedures.

A Primer

The aforementioned approach is surveyed in a primer on pseudorandom generators, which was published in the ULECT series (Nr. 55) of the AMS, 2010. See freely available drafts. Related texts are listed below.

Chapters in Book

Chapter 3 in Modern Cryptography, Probabilistic Proofs and Pseudorandomness (1998) is an earlier version of the foregoing primer.
A revised version appears as Chapter 8 in a book on Complexity theory (2008).
Chapter 3 in Foundations of Cryptography (2001) focuses on the archetypical case of pseudorandom generators (withstanding any polynomial-time distinguisher).

Lecture notes (available on-line)

O. Goldreich, Lecture Notes on Pseudorandomness - Part I (polynomial-time generators), 2000. [in PDF].
L. Trevisan, Lecture Notes on Pseudorandomness - Part II (derandomization), 2000. [in PDF].

Surveys (available on-line)

O. Goldreich, Randomness, Interaction, Proofs and Zero-Knowledge, 1987. [in PDF].
See a revised version of the part on Computational Randomness, 1987 (rev. 1997). [in PDF].
O. Goldreich, N. Nisan and A. Wigderson, On Yao's XOR-Lemma, March 1995.
O. Goldreich, Pseudorandomness, 1999. ( extended, 2000.) [in PDF].
O. Goldreich, Pseudorandom Generators, Jan. 2006. [in PDF].
[This is a self-contained version of an eraly draft of chapter 8 of a book on Complexity theory.]
O. Goldreich, Pseudorandom Generators - A Primer, Jul. 2008. [in PDF].
This is the latest and most recommended exposition. It provides a comprehensive treatment of the basic notions and results, and contains proof outlines and/or sketches for the main results. [This is a self-contained and abbreviated version of chapter 8 of a book on Complexity theory.]