PAPERBACK
\$52.75

• #### 12 Missing Pieces, Derandomization, and Concluding Remarks 175-178

one would like to conserve the number of random bits needed in a computation. Second, the deterministic character of pseudorandom bit sequences permits the easy reproducibility of computations. A third reason arises from cryptography: the existence of secure pseudorandom bit generators is essentially equivalent to the existence of secure private-key cryptosystems.

For Monte Carlo simulations, one often wants pseudorandom numbers, which are numbers simulating either independent draws from a fixed probability distribution on the real line R, or more generally numbers simulating samples from a stationary random process. It is possible to simulate samples of any reasonable distribution using as input a sequence of i.i.d. 0-1 valued random variables (see Devroye, 1986, and Knuth and Yao, 1976). Hence the problem of constructing pseudorandom numbers is in principle reducible to that of constructing pseudorandom bits.

Section 6.2 describes explicitly some pseudorandom bit generators, as well as some general principles for constructing pseudorandom bit generators. Most of these generators have underlying group-theoretic or number-theoretic structure.

Section 6.3 describes the subject of computational information theory and indicates its connection to cryptography. The basic object in this theory is the concept of a secure pseudorandom bit generator, which was proposed by Blum and Micali (1982) and Yao (1982). The basic properties characterizing a secure pseudorandom bit generator are ''randomness-increasing" and "computationally unpredictable." Recently obtained results are that if one of the following objects exist then they all exist:

1. a secure pseudorandom bit generator,

2. a one-way function, and

3. a secure (block-type) private-key cryptosystem.

The central unsolved question is whether any of these objects exist. However, good candidates are known for one-way functions. A major difficulty in settling the existence problem for this theory is summarized in the following heuristic:

Unpredictability Paradox. If a deterministic function is unpredictable, then it is difficult to prove anything about it; in particular, it is difficult to prove that it is unpredictable.

The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001