resources. It is estimated that it is physically impossible to ever execute more than 2300 operations, regardless of any possible future technological improvements.

When a distribution is computationally indistinguishable from a stream of random bits, then we call the distribution “pseudorandom.”

Pseudorandomness. A distribution mX over {0, 1}n is (K, ε)-pseudorandom if it is (K, ε)-indistinguishable from the uniform distribution. That is, for every T ⊆ {0, 1}n of circuit complexity ≤ K,

algorithm G that, given n, s, computes Gn(s) in time 2O(t(n)). Then G is called a t(n)-quick pseudorandom generator.

Suppose that an O(log n)-quick pseudorandom generator ( abbreviated logQPRG) exists, and suppose that f is a function and A is a polynomial time randomized algorithm that computes f with probability at least 3/4. We now describe a derandomization of algorithm A.

Let I be an input, and let m be the number of random bits used by A on input I. Let K be an efficiently computable upper bound to the circuit complexity of T := {r : A(r, I) = f(I)}. Choose n to be large enough so that: (i) n2 ≥ K, (ii) n ≥ m, and (iii) n ≥ 5. Because of our assumption that A runs in polynomial time, n is polynomial in the length of I. (It should be noted that we may not know how to construct a circuit for T, because it seems that to construct such a circuit we need to know f(I). In order to compute a polynomially bounded upper bounds to the circuit complexity of T, however, we just need to find out how large is the circuit for T that we would be able to build if we knew f (I ).)

Now, compute A(Gn(s), I) for each s, and output the value that is returned most often. This completes the description of a polynomial time deterministic algorithm for computing f.

Regarding correctness, we assumed

, and so

f(I) is the number of perfect matchings in the graph represented by I and A is the Jerrum-Sinclair-Vigoda probabilistic approximation algorithm for this problem [ 13]. The only difference is that we take the median of the outputs instead of the most common one.

 

Suppose, for concreteness, that we have a function G : {0, 1}128 → {0, 1}240 which is (260, 2− 20)-pseudorandom. Then we can design a symmetric-key cryptosystem in which the key k is a 128-bit random string, and the encryption is a one-time pad that uses G(k) as a key, allowing up to a terabyte of communication between the parties. By Shannon’s analysis, in such a cryptosystem, the cypher texts leak information about the private messages being exchanged. But it is possible to use the definition of pseudorandomness to prove that an eavesdropper analyzes the traffic using computational resources that can be simulated by a circuit of size ≤ 260 (which is true of any realizable computation with current technology) can only gain negligible information about the private messages. It is beyond the goals of this short article to describe the connection between pseudorandomness and cryptographic security, and the proper definitional framework to discuss cryptographic security in a setting in which the eavesdropper is computationally bounded. The curious reader is referred to work of Goldwasser and Micali [ 8] and to the exposition in the textbook of Katz and Lindell [ 11].

Application to derandomization. The following definition is due to Nisan and Wigderson [ 12].

Quick Pseudorandom Generator.

Suppose that for every n there is a Gn : {0, 1}t(n) → {0, 1}n that is (n2, 1/n)- pseudorandom, and that there is an

( 1)

CONDI TIONAL CONSTRUC TIONS OF
PSEUDORANDOM GENERATORS

The next question that arises is whether QPRGs exist, and what assumptions must be made to prove their existence. Various efforts have been made in this area. Blum and Micali construct no( 1)QPRGs, according to a slightly different definition than above, using a specific number-theo-retic assumption [ 9]. Yao proves that the Blum-Micali definition is equivalent to a definition based on indistinguishability and constructs no( 1)QPRGs under a more general assumption [ 10]. Yao also recognizes that no( 1)QPRGs imply a 2no( 1) derandomization of every probabilistic algorithm.

Nisan and Wigderson introduced the definition of quick pseudorandom generator that we gave in the previous section and presented a new construction that works under considerably weaker assumptions than the existence of one-way functions [ 12]. On the other hand, the Nisan-Wigderson generator does not satisfy the stronger properties of the pseudorandom generators of Blum, Micali, Yao, Håstad et al. [ 9, 10, 14]. This is unavoidable because the existence of such stronger pseudorandom generators is equivalent to the existence of one-way functions. The Nisan-Wigderson construction also “scales” very well, and it gives more efficient QPRGs if one is willing to start from stronger assumptions. A sufficiently strong assumption implies optimal logQPRGs, and this is the only version of the Nisan-Wigderson results that we will discuss.

We first need to define a notion of average-case circuit complexity. We say that a set S ⊆ {0, 1}n is (K, ε)-hard on average if, for every set T computable by a circuit of size ≤ K, we have , where we use the notation 1 S for the characteristic function of the set S.

Otherwise, the set T = {r : A(r, I) = f(I)} contradicts the pseudorandomness of Gn .

This means that, at the cost of a polynomial-time slowdown, we have simulated the randomized algorithm without using any randomness at all.

Note the similarity with the argument we gave earlier about ideal randomness generators: The proof is essentially the same, but with a quick pseudorandom generator instead of an ideal randomness generator.

A similar approach works also if A is only guaranteed to approximate f with high probability, for example if