A PSEUDORANDOM GENERATOR FROM ANY ONE-WAY FUNCTION^{∗}

JOHAN HÅSTAD^{†}, RUSSELL IMPAGLIAZZO^{‡}, LEONID A. LEVIN^{§}, AND MICHAEL LUBY^{¶}

SIAM J. COMPUT. \begin{matrix}c \\ ◯ \end{matrix} 1999 Society for Industrial and Applied Mathematics Vol. 28, No. 4, pp. 1364–1396

Abstract. Pseudorandom generators are fundamental to many theoretical and applied aspects of computing. We show how to construct a pseudorandom generator from any one-way function. Since it is easy to construct a one-way function from a pseudorandom generator, this result shows that there is a pseudorandom generator if and only if there is a one-way function.

Key words. one-way function, pseudorandom generator, cryptography, complexity theory

AMS subject classifications. 68P25, 68Q25, 68Q99

PII. S0097539793244708

1. Introduction. One of the basic primitives in the study of the interaction between randomness and feasible computation is a pseudorandom generator. Intuitively, a pseudorandom generator is a polynomial time-computable function g that stretches a short random string x into a long string g(x) that “looks” random to any feasible algorithm, called an adversary. The adversary tries to distinguish the string g(x) from a random string the same length as g(x). The two strings “look” the same to the adversary if the acceptance probability for both strings is essentially the same. Thus, a pseudorandom generator can be used to efficiently convert a small amount of true randomness into a much larger number of effectively random bits.

The notion of randomness tests for a string evolved over time: from set-theoretic tests to enumerable [K65], recursive, and finally limited time tests. Motivated by cryptographic applications, the seminal paper [BM82] introduced the idea of a generator which produces its output in polynomial time such that its output passes a general polynomial time test. The fundamental paper [Yao82] introduced the definition of a pseudorandom generator most commonly used today and proves that this definition and the original of [BM82] are equivalent.

The robust notion of a pseudorandom generator, due to [BM82], [Yao82], should be contrasted with the classical methods of generating random looking bits as described in, e.g., [Knuth97]. In studies of classical methods, the output of the generator is considered good if it passes a particular set of standard statistical tests. The linear congruential generator is an example of a classical method for generating random looking bits that pass a variety of standard statistical tests. However, [Boyar89] and [K92] show that there is a polynomial time statistical test which the output from this

∗Received by the editors February 22, 1993; accepted for publication (in revised form) August 18, 1997; published electronically April 7, 1999.

http://www.siam.org/journals/sicomp/28-4/24470.html †Department of Numerical Analysis and Computer Science, Royal Institute of Technology, S-

100 44 Stockholm 70, Sweden (Johanh@nada.kth.se). This research was supported by the Swedish National Board for Technical Development.

‡Department of Computer Science, University of California at San Diego, La Jolla, CA 92093 (Russell@cs.ucsd.edu). This research was supported by NSF grant CCR 88-13632.

§Computer Science Department, Boston University, 111 Cummington St., Boston, MA 02215 (Lnd@cs.bu.edu). This research was supported by NSF grants CCR-9015276 and CCR-9610455.

¶International Computer Science Institute, University of California at Berkeley, 1947 Center Street, Berkeley, CA 94704 (Luby@icsi.berkeley.edu). This research was supported by NSERC grant A8092 and NSF grants CCR-9016468 and CCR-9304722.

generator does not pass.

The distinction between the weaker requirement that the output pass some particular statistical tests and the stronger requirement that it pass all feasible tests is particularly important in the context of many applications. As pointed out by [BM82], in cryptographic applications the adversary must be assumed to be as malicious as possible, with the only restriction on tests being computation time. A pseudorandom generator can be directly used to design a private key cryptosystem secure against all such adversaries.

In the context of Monte Carlo simulation applications, a typical algorithm uses long random strings, and a typical analysis shows that the algorithm produces a correct answer with high probability if the string it uses is chosen uniformly. In practice, the long random string is not chosen uniformly, as this would require more random bits than it is typically reasonable to produce (and store). Instead, a short random string is stretched into a long string using a simple generator such as a linear congruential generator, and this long string is used by the simulation algorithm. In general, it is hard to directly analyze the simulation algorithm to prove that it produces the correct answer with high probability when the string it uses is produced using such a method. A pseudorandom generator provides a generic solution to this problem. For example, [Yao82] shows how pseudorandom generators can be used to reduce the number of random bits needed for any probabilistic polynomial time algorithm and thus shows how to perform a deterministic simulation of any polynomial time probabilistic algorithm in subexponential time based on a pseudorandom generator. The results on deterministic simulation were subsequently generalized in [BH89], [BFNW96].

Since the conditions are rather stringent, it is not easy to come up with a natural candidate for a pseudorandom generator. On the other hand, there seem to be a variety of natural examples of another basic primitive: the one-way function. Informally, f is one-way if it is easy to compute but hard on average to invert. If P=NP, then there are no one-way functions, and it is not even known if P ≠ NP implies there are one-way functions. However, there are many examples of functions that seem to be one-way in practice and that are conjectured to be one-way. Some examples of conjectured one-way functions are the discrete logarithm problem modulo a large randomly chosen prime (see, e.g., [DH76]), factoring a number that is the product of two large randomly chosen primes (see, e.g., [RSA78]), problems from coding theory (see, e.g., [McEl78], [GKL93]), and the subset sum problem for appropriately chosen parameters (see, e.g., [IN96]).

The paper [BM82] is the first to construct a pseudorandom generator based on a one-way function. They introduce an elegant construction that shows how to construct a pseudorandom generator based on the presumed difficulty of the discrete logarithm problem. The paper [Yao82] substantially generalizes this result by showing how to construct a pseudorandom generator from any one-way permutation. (Some of the arguments needed in the proof were missing in [Yao82] and were later completed by [Levin87]. Also, [Levin87] conjectured that a much simpler construction would work for the case of one-way permutations, and this was eventually shown in [GL89].)

There are several important works that have contributed to the expansion of the conditions on one-way functions under which a pseudorandom generator can be constructed. [GMT82] and [Yao82] show how to construct a pseudorandom generator based on the difficulty of factoring, and this was substantially simplified in [ACGS88]. When f is a one-way permutation, the task of inverting f(x) is to find x. In the case when f is not a permutation, the natural extension of successful inversion is finding any x′ such that f(x′) = f(x). The paper [Levin87] introduces one-way functions which remain one-way after several iterations and shows them to be necessary and sufficient for the construction of a pseudorandom generator. The paper [GKL93] shows how to construct a pseudorandom generator from any one-way function with the property that each value in the range of the function has roughly the same number of preimages. This expanded the list of conjectured one-way functions from which pseudorandom generators can be constructed to a variety of nonnumber theoretic functions, including coding theory problems.

However, the general question of how to construct a pseudorandom generator from a one-way function with no structural properties was left open. This paper resolves this question. We give several successively more intricate constructions, starting with constructions for one-way functions with a lot of structure and finishing with the constructions for one-way functions with no required structural properties.

This paper is a combination of the results announced in the conference papers [ILL89] and [H90].

1.1. Concepts and tools. Previous methods, following [BM82], rely on constructing a function that has an output bit that is computationally unpredictable given the other bits of the output, but is nevertheless statistically correlated with these other bits. [GL89] provide a simple and natural input bit which is hidden from (a padded version of) any one-way function. Their result radically simplifies the previous constructions of pseudorandom generators from one-way permutations and in addition makes all previous constructions substantially more efficient. We use their result in a fundamental way.

Our overall approach is different in spirit from previous constructions of pseudorandom generators based on one-way functions with special structure. Previous methods rely on iterating the one-way function many times, and from each iteration they extract a computationally unpredictable bit. The approach is to make sure that after many iterations the function is still one-way. In contrast, as explained below in more detail, our approach concentrates on extracting and smoothing entropy in parallel from many independent copies of the one-way function. Our overall construction combines this parallel approach with a standard method for iteratively stretching the output of a pseudorandom generator.

The notion of computational indistinguishability provides one of the main conceptual tools in our paper. Following [GM84] and [Yao82], we say that two probability distributions D and E are computationally indistinguishable if no feasible adversary can distinguish D from E. In these terms, a pseudorandom generator is intuitively the following: let g be a polynomial time computable function that maps strings of length n to longer strings of length ℓ_{n} > n. Let X be a random variable that is uniformly distributed on strings of length n and let Y be a random variable that is uniformly distributed on strings of length ℓ_{n}. Then g is a pseudorandom generator if g(X) and Y are computationally indistinguishable.

The Shannon entropy of a distribution is a good measure of its information content. A fundamental law of information theory is that the application of a function cannot increase entropy. For example, because X has n bits of entropy, g(X) can also have at most n bits of entropy (see Proposition 2.6). The work presented in this paper focuses on a computational analogue of Shannon entropy, namely computational entropy. We say the computational entropy of g(X) is at least the Shannon entropy of Y if g(X) and Y are computationally indistinguishable. If g(X) is a pseudorandom generator, the computational entropy of g(X) is greater than the Shannon entropy of its input X, and in this sense g amplifies entropy.

We introduce the following generalizations of a pseudorandom generator based on computational entropy. We say that g(X) is a pseudoentropy generator if the computational entropy of g(X) is significantly more than the Shannon entropy of X. We say that g(X) is a false-entropy generator if the computational entropy of g(X) is significantly more than the Shannon entropy of g(X).

We show how to construct a false-entropy generator from any one-way function, a pseudoentropy generator from any false-entropy generator, and finally a pseudorandom generator from any pseudoentropy generator. (The presentation of these results in the paper is in reverse order.)

We use hash functions and their analysis in a fundamental way in our constructions. This approach has its roots in [GKL93]. In [GL89], it turns out that the easily computable bit that is hidden is the parity of a random subset of the input bits, i.e., the inner product of the input and a random string. This random inner product can be viewed as a hash function from many bits to one bit.

Due to its importance in such basic algorithms as primality testing, randomness has become an interesting computational resource in its own right. Recently, various studies for extracting good random bits from biased “slightly random” sources that nevertheless possess a certain amount of entropy have been made; these sources model the imperfect physical sources of randomness, such as Geiger counter noise and Zener diodes, that would have to actually be utilized in real life. (See [Blum84], [SV86], [V87], [VV85], [CG88], and [McIn87].) One of our main technical lemmas (Lemma 4.8) can be viewed as a hashing lemma which is used to manipulate entropy in various ways: it can be viewed as a method for extracting close to uniform random bits from a slightly random source using random bits as a catalyst.

1.2. Outline. An outline of the paper is as follows.

In section 2 we give notation, especially as related to probability distributions and ensembles. In section 3, we define the basic primitives used in the paper and a general notion of reduction between primitives. We spend a little more time on this than is conventional in papers on cryptography, since we want to discuss the effects of reductions on security in quantitative terms.

Section 4 introduces the basic mechanisms for finding hidden bits and manipulating entropy with hash functions. The main result of the section is a reduction from a false-entropy generator to a pseudorandom generator via a pseudoentropy generator.

In section 5, we present a construction of a pseudorandom generator from a oneway function where preimage sizes can be estimated. Although such one-way functions are very common, and so this is an important special case, the main reason for including this is to develop intuition for general one-way functions.

Section 6 presents the most technically challenging construction: that of a falseentropy generator from any one-way function. Combined with section 4, this yields the main result of the paper: the construction of a pseudorandom generator from any one-way function.

In section 7, we present a somewhat more direct and efficient construction of a pseudorandom generator from any one-way function. This section uses the ideas from sections 4, 5, and 6, but avoids some redundancy involved in combining three generic reductions. Section 8 concludes by placing our results in the context of modern cryptographic complexity.

2. Basic notation. N is the set of natural numbers. If S is a set, then ♯S is the number of elements in S. If S and T are sets, then S \ T is the set consisting of all elements in S that are not in T. If a is a number, then |a| is the absolute value of a, ⌈a⌉ is the smallest integer greater than or equal to a, and log(a) is the logarithm base two of a.

Let x and y be bit strings. We let ⟨x, y⟩ denote the sequence x followed by y, and when appropriate we also view this as the concatenation of x and y. If x ∈ {0, 1}^{n}, then x_{i} is the ith bit of x, x_{{i,...,j}} is ⟨x_{i}, …, x_{j}⟩, and x ⊕ y is ⟨x_{1} ⊕ y_{1}, …, x_{n} ⊕ y_{n}⟩.

An m × n bit matrix x is indicated by x ∈ {0, 1}^{m×n}. We write x_{i,j} to refer to the (i, j)-entry in x. We can also view x as a sequence x = ⟨x_{1}, …, x_{m}⟩ of m strings, each of length n, where in this case x_{i} is the ith row of the matrix, or we can view x as a bit string of length mn, which is the concatenation of the rows of the matrix.

The ⊙ operation indicates matrix multiplication over GF[2]. If x ∈ {0, 1}^{n} appears to the left of ⊙, then it is considered to be a row vector, and if it appears to the right of ⊙, it is considered to be a column vector. Thus, if x ∈ {0, 1}^{n} and y ∈ {0, 1}^{n}, then x ⊙ y = ∑_{i=1}^{n} x_{i} · y_{i} mod 2. More generally, if x ∈ {0, 1}^{ℓ×m} and y ∈ {0, 1}^{m×n}, then x ⊙ y is the ℓ × n bit matrix, where the (i, j)-entry is r ⊙ c, where r is the ith row of x and c is the jth column of y.

2.1. Probability notation. In general, we use capital and Greek letters to denote random variables and random events. Unless otherwise stated, all random variables are independent of all other random variables.

A distribution D on a finite set S assigns a probability D(x) ≥ 0 to each x ∈ S, and thus ∑_{x∈S} D(x) = 1. We say a random variable X is distributed according to D on S if for all x ∈ S, Pr[X = x] = D(x), and we indicate this by X ∈_{D} S. We write D : {0, 1}^{ℓ_{n}} to indicate that D is supported on strings of length ℓ_{n}. We sometimes, for convenience, blur the distinction between a random variable and its distribution. If X_{1} and X_{2} are random variables (that are not necessarily independent), then (X_{1}|X_{2} = x_{2}) denotes the random variable that takes on value x_{1} with the conditional probability Pr[X_{1} = x_{1}|X_{2} = x_{2}] = Pr[X_{1} = x_{1} ∧ X_{2} = x_{2}]/ Pr[X_{2} = x_{2}].

If f is a function mapping S to a set T, then f(X) is a random variable that defines a distribution E, where for all y ∈ T, E(y) = ∑_{x∈S,f(x)=y} D(x). We let f(D) indicate the distribution E.

We let X ∈_{U} S indicate that X is uniformly distributed in S; i.e., for all x ∈ S, Pr[X = x] = 1/♯S. We let U_{n} indicate the uniform distribution on {0, 1}^{n}; i.e., X is distributed according to U_{n} if X ∈_{U} {0, 1}^{n}.

We sometimes want to indicate a random sample chosen from a distribution, and we do this by using the same notation as presented above for random variables except that we use lowercase letters; i.e., x ∈_{D} S indicates that x is a fixed element of S chosen according to distribution D.

If X is a real-valued random variable, then E[X] denotes the expected value X. If E is a probabilistic event, then Pr[E] denotes the probability that event E occurs.

Definition 2.1 (statistical distance). Let D and E be distributions on a set S. The statistical distance between D and E is

L_{1}(D, E) = ∑_{x∈S} |Pr[D(x)] − Pr[E(x)]| /2.

Proposition 2.2. For any function f with domain S and for any pair of distributions D and E on S, L_{1}(f(D), f(E)) ≤ L_{1}(D, E).

2.2. Entropy. The following definition of entropy is from [S48].

Definition 2.3 (information and entropy). Let D be a distribution on a set S. For each x ∈ S, define the information of x with respect to D to be I_{D}(x) = − log(D(x)). Let X ∈_{D} S. The (Shannon) entropy of D is H(D) = E[I_{D}(X)]. Let D_{1} and D_{2} be distributions on S that are not necessarily independent, and let X_{1} ∈_{D_{1}} S and X_{2} ∈_{D_{2}} S. Then the conditional entropy of D_{1} with respect to D_{2}, H(D_{1}|D_{2}), is E_{x_{2}∈_{D_{2}} S}[H(X_{1}|X_{2} = x_{2})].

We sometimes refer to the entropy H(X) of random variable X, which is equal to H(D). We sometimes refer to the conditional entropy H(X_{1}|X_{2}) of X_{1} conditioned on X_{2}, which is equal to H(D_{1}|D_{2}).

The following variant definition of entropy is due to [Renyi70].

Definition 2.4 (Renyi entropy). Let D be a distribution on a set S. The Renyi entropy of D is H_{Ren}(D) = − log(Pr[X = Y]), where X ∈_{D} S and Y ∈_{D} S are independent.

There are distributions that have arbitrarily large entropy but have only a couple of bits of Renyi entropy.

Proposition 2.5. For any distribution D, H_{Ren}(D) ≤ H(D).

We sometimes use the following proposition implicitly. This proposition shows that a function cannot increase entropy in a statistical sense.

Proposition 2.6. Let f be a function and let D be a distribution on the domain of f. Then H(f(D)) ≤ H(D).

The following definition characterizes how much entropy is lost by the application of a function f to the uniform distribution.

Definition 2.7 (degeneracy of f). Let f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} and let X ∈_{U} {0, 1}^{n}. The degeneracy of f is D_{n}(f) = H(X|f(X)) = H(X) − H(f(X)).

2.3. Ensembles. We present all of our definitions and results in asymptotic form. Ensembles are used to make the asymptotic definitions, e.g., to define primitives such as one-way functions and pseudorandom generators, and to define the adversaries that try to break the primitives. In all cases, we use n ∈ N as the index of the ensemble and, implicitly, the definition and/or result holds for all values of n ∈ N.

In our definitions of ensembles, the input and output lengths are all polynomially related. To specify this, we use the following.

Definition 2.8 (polynomial parameter). We say parameter k_{n} is a polynomial parameter if there is a constant c > 0 such that for all n ∈ N,

\frac{1}{cn^{c}} ≤ k_{n} ≤ cn^{c}.

We say k_{n} is a P-time polynomial parameter if in addition there is a constant c′ > 0 such that, for all n, k_{n} is computable in time at most c′n^{c′}.

In many uses of a polynomial parameter k_{n}, k_{n} is integer valued, but it is sometimes the case that k_{n} is real valued.

Definition 2.9 (function ensemble). We let f : {0, 1}^{t_{n}} → {0, 1}^{ℓ_{n}} denote a function ensemble, where t_{n} and ℓ_{n} are integer-valued P-time polynomial parameters and where f with respect to n is a function mapping {0, 1}^{t_{n}} to {0, 1}^{ℓ_{n}}. If f is injective, then it is a one-to-one function ensemble. If f is injective and ℓ_{n} = t_{n}, then it is a permutation ensemble. We let f : {0, 1}^{t_{n}} × {0, 1}^{ℓ_{n}} → {0, 1}^{m_{n}} denote a function ensemble with two inputs. In this case, we sometimes consider f as being a function of the second input for a fixed value of the first input, in which case we write f_{x}(y) in place of f(x, y).

Definition 2.10 (P-time function ensemble). We say f : {0, 1}^{t_{n}} × {0, 1}^{ℓ_{n}} → {0, 1}^{m_{n}} is a T_{n}-time function ensemble if f is a function ensemble such that, for all x ∈ {0, 1}^{t_{n}}, for all y ∈ {0, 1}^{ℓ_{n}}, f(x, y) is computable in time T_{n}. We say f is a Ptime function ensemble if there is a constant c such that, for all n, T_{n} ≤ cn^{c}. We say f is a mildly nonuniform P-time function ensemble if it is a P-time function ensemble except that it has an additional input a_{n} called the advice, that is, an integer-valued polynomial parameter that is not necessarily P-time computable.

These definitions generalize in a natural way to functions with more than two inputs. Sometimes we describe functions that have variable length inputs or outputs; in these cases we implicitly assume that the string is padded out with a special blank symbol to the appropriate length.

In some of our intermediate reductions, we use certain statistical quantities in order to construct our new primitive. For example, we might use an approximation of the entropy of a distribution in our construction of a pseudoentropy generator. Although in many cases these quantities are not easy to approximate, the number of different approximation values they can take on is small. This is the reason for the definition of a mildly nonuniform P-time function ensemble in the above definition. In all the definitions we give below, e.g., of one-way functions, false-entropy generators, pseudoentropy generators, and pseudorandom generators, there is also an analogous mildly nonuniform version. In Proposition 4.17, we show how to remove mild nonuniformity in the final construction of a pseudorandom generator.

Definition 2.11 (range and preimages of a function). Let f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} be a function ensemble. With respect to n, define

range_{f} = {f(x) : x ∈ {0, 1}^{n}}.

For each y ∈ range_{f}, define

pre_{f}(y) = {x ∈ {0, 1}^{n} : f(x) = y}.

Definition 2.12 (regular function ensemble). We say function ensemble f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} is σ_{n}-regular if ♯pre_{f}(y) = σ_{n} for all y ∈ range_{f}.

Definition 2.13 (D̃_{f}). Let f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} be a P-time function ensemble. For z ∈ range_{f}, define the approximate degeneracy of z as

D̃_{f}(z) = ⌈log(♯pre_{f}(z))⌉ .

Notice that D̃_{f}(z) is an approximation to within an additive factor of 1 of the quantity n − I_{f(X)}(z). Furthermore, E[D̃_{f}(f(X))] is within an additive factor of 1 of the degeneracy of f. If f is a σ_{n}-regular function then, for each z ∈ range_{f}, D̃_{f}(z) is within an additive factor of 1 of log(σ_{n}), which is the degeneracy of f.

Definition 2.14 (probability ensemble). We let D : {0, 1}^{ℓ_{n}} denote a probability ensemble, where ℓ_{n} is an integer-valued P-time polynomial parameter and where D with respect to n is a probability distribution on {0, 1}^{ℓ_{n}}.

Definition 2.15 (P-samplable probability ensemble). We let D : {0, 1}^{ℓ_{n}} denote a probability ensemble that, with respect to n, is a distribution on {0, 1}^{ℓ_{n}} that can be generated from a random string of length r_{n} for some r_{n}; i.e., there is a function ensemble f : {0, 1}^{r_{n}} → {0, 1}^{ℓ_{n}} such that if X ∈_{U} {0, 1}^{r_{n}} then f(X) has the distribution D. We say D is a T_{n}-samplable probability ensemble if, for all x ∈ {0, 1}^{r_{n}}, f(x) is computable in time T_{n}. We say D is P-samplable if f is a P-time function ensemble, and D is mildly nonuniformly P-samplable if f is a mildly nonuniform P-time function ensemble.

Definition 2.16 (copies of functions and ensembles). Let k_{n} be an integer-valued P-time polynomial parameter. If D : {0, 1}^{ℓ_{n}} is a probability ensemble, then D^{k_{n}} : {0, 1}^{ℓ_{n}k_{n}} is the probability ensemble where, with respect to parameter n, D^{k_{n}} consists of the concatenation of k_{n} independent copies of D. Similarly, if f : {0, 1}^{m_{n}} → {0, 1}^{ℓ_{n}} is a function ensemble, then f^{k_{n}} : {0, 1}^{m_{n}k_{n}} → {0, 1}^{ℓ_{n}k_{n}} is the function ensemble where, for y ∈ {0, 1}^{k_{n}×m_{n}},

f^{k_{n}}(y) = ⟨f(y_{1}), …, f(y_{k_{n}})⟩.

3. Definitions of primitives and reductions. Primitives described in this paper include one-way functions and pseudorandom generators. The primitives we describe can be used in cryptographic applications but are also useful as described in the introduction in other applications. In the definition of the primitives, we need to describe what it means for the primitive to be secure against an attack by an adversary. We first introduce adversaries and security and then describe the basic primitives that we use thereafter.

3.1. Adversaries and security. An adversary is, for example, trying to invert a one-way function or trying to distinguish the output of a pseudorandom generator from a truly random string. The time–success ratio of a particular adversary is a measure of its ability to break the cryptographic primitive. (Hereafter, we use “primitive” in place of the more cumbersome and sometimes misleading phrase “cryptographic primitive.”) The security of a primitive is a lower bound on the time–success ratio of any adversary to break the primitive.

In the constructions of some primitives, we allow both private and public inputs. A public input is part of the output of the primitive and is known to the adversary at the time it tries to break the primitive. When we construct one primitive based on another, the constructed primitive often has public inputs. At first glance it could seem that these public inputs are not useful because an adversary knows them at the time it tries to break the constructed primitive. On the contrary, public inputs turn out to be quite useful. Intuitively, this is because their value is randomly chosen, and the adversary cannot a priori build into its breaking strategy a strategy for all possible values.

The private input to a primitive is not directly accessible to the adversary. The security parameter of a primitive is the length of its private input. This is because the private input to the primitive is what is kept secret from the adversary, and thus it makes sense to measure the success of the adversary in terms of this.

Definition 3.1 (breaking adversary and security). An adversary A is a function ensemble. The time–success ratio of A for an instance f of a primitive is defined as R_{t_{n}} = T_{n}/sp_{n}(A), where t_{n} is the length of the private input to f, T_{n} is the worstcase expected running time of A over all instances parameterized by n, and sp_{n}(A) is the success probability of A for breaking f. In this case, we say A is an R-breaking adversary for f. We say f is R-secure if there is no R-breaking adversary for f.

A mildly nonuniform adversary for a mildly nonuniform P-time function ensemble f that has advice a_{n} is a function ensemble A which is given a_{n} as an additional input. The success probability and time–success ratio for a mildly nonuniform adversary is the same as for uniform adversaries.

The definition of the success probability sp_{n}(A) for f depends on the primitive in question; i.e., this probability is defined when the primitive is defined. Intuitively, the smaller the time–success ratio of an adversary for a primitive, the better the adversary is able to break the primitive, i.e., it uses less time and/or has a larger success probability.

The above definitions are a refinement of definitions that appear in the literature. Previously, an adversary was considered to be breaking if it ran in polynomial time and had inverse polynomial success probability. The advantage of the definition introduced here is that it is a more precise characterization of the security of a primitive. This is important because different applications require different levels of security. For some applications polynomial security is enough (e.g., R_{t_{n}} = t_{n}^{10}) and for other applications better security is crucial (e.g., R_{t_{n}} = 2^{log^{2}(t_{n})}, or even better R_{t_{n}} = 2^{\sqrt{t_{n}}}).

3.2. One-way function.

Definition 3.2 (one-way function). Let f : {0, 1}^{t_{n}} → {0, 1}^{ℓ_{n}} be a P-time function ensemble and let X ∈_{U} {0, 1}^{t_{n}}. The success probability of adversary A for inverting f is

sp_{n}(A) = Pr[f(A(f(X))) = f(X)].

Then f is an R-secure one-way function if there is no R-breaking adversary for f.

A function cannot be considered to be “one-way” in any reasonable sense in case the time to invert it is smaller than the time to evaluate it in the forward direction. Thus, for example, if there is an O(t_{n})-breaking adversary for f, then it is not secure at all. On the other hand, an exhaustive adversary that tries all possible inputs to find an inverse is t_{n}^{O(1)} · 2^{t_{n}}-breaking. Thus, the range of securities that can be hoped for falls between these two extremes.

3.3. Pseudorandom generator. The following definition can be thought of as the computationally restricted adversary definition of statistical distance. The original idea is from [GM84] and [Yao82].

Definition 3.3 (computationally indistinguishable). Let D : {0, 1}^{ℓ_{n}} and E : {0, 1}^{ℓ_{n}} be probability ensembles. The success probability of adversary A for distinguishing D and E is

sp_{n}(A) = | Pr[A(X) = 1] − Pr[A(Y) = 1]|,

where X has distribution D and Y has distribution E. D and E are R-secure computationally indistinguishable if there is no R-breaking adversary for distinguishing D and E.

The following alternative definition of computationally indistinguishable more accurately reflects the trade-off between the running time of the adversary and its success probability. In the alternative definition, success probability is defined as sp′_{n}(A) = (sp_{n}(A))^{2}. This is because it takes 1/sp′_{n}(A) trials in order to approximate sp_{n}(A) to within a constant factor.

Definition 3.4 (computationally indistinguishable (alternative)). This is exactly the same as the original definition, except the success probability of adversary A is sp′_{n}(A) = (sp_{n}(A))^{2}.

In all cases except where noted, the strength of the reduction is the same under either definition of computationally indistinguishable, and we find it easier to work with the first definition. However, there are a few places where we explicitly use the alternative definition to be able to claim the reduction is linear-preserving.

Strictly speaking, there are no private inputs in the above definition, and thus by default we use n as the security parameter. However, in a typical use of this definition, D is the distribution defined by the output of a P-time function ensemble (and thus D is P-samplable), in which case the length of the private input to this function ensemble is the security parameter. In some circumstances, it is important that both D and E are P-samplable; e.g., this is the case for Proposition 4.12.

The paper [Yao82] originally gave the definition of a pseudorandom generator as below, except that we parameterize security more precisely.

Definition 3.5 (pseudorandom generator). Let g : {0, 1}^{t_{n}} → {0, 1}^{ℓ_{n}} be a P-time function ensemble where ℓ_{n} > t_{n}. Then g is an R-secure pseudorandom generator if the probability ensembles g(U_{t_{n}}) and U_{ℓ_{n}} are R-secure computationally indistinguishable.

The definition of a pseudorandom generator only requires the generator to stretch the input by at least one bit. The following proposition provides a general way to produce a pseudorandom generator that stretches by many bits from a pseudorandom generator that stretches by at least one bit. This proposition appears in [BH89] and is due to O. Goldreich and S. Micali.

Proposition 3.6. Suppose g : {0, 1}^{n} → {0, 1}^{n+1} is a pseudorandom generator that stretches by one bit. Define g^{(1)}(x) = g(x), and inductively, for all i ≥ 1,

g^{(i+1)}(x) = ⟨g(g^{(i)}(x)_{{1,...,n}}), g^{(i)}(x)_{{n+1,...,n+i}}⟩.

Let k_{n} be an integer-valued P-time polynomial parameter. Then g^{(k_{n})} is a pseudorandom generator. The reduction is linear-preserving.

In section 3.6 we give a formal definition of reduction and what it means to be linear-preserving, but intuitively it means that g^{(k_{n})} as a pseudorandom generator is almost as secure as pseudorandom generator g.

3.4. Pseudoentropy and false-entropy generators. The definitions in this subsection introduce new notions (interesting in their own right) which we use as intermediate steps in our constructions.

The difference between a pseudorandom generator and a pseudoentropy generator is that the output of a pseudoentropy generator doesn’t have to be computationally indistinguishable from the uniform distribution; instead it must be computationally indistinguishable from some probability ensemble D that has more entropy than the input to the generator. Thus, a pseudoentropy generator still amplifies randomness so that the output randomness is more computationally than the input randomness, but the output randomness is no longer necessarily uniform.

Definition 3.7 (computational entropy). Let f : {0, 1}^{t_{n}} → {0, 1}^{ℓ_{n}} be a Ptime function ensemble and let s_{n} be a polynomial parameter. Then f has R-secure computational entropy s_{n} if there is a P-time function ensemble f′ : {0, 1}^{m_{n}} → {0, 1}^{ℓ_{n}} such that f(U_{t_{n}}) and f′(U_{m_{n}}) are R-secure computationally indistinguishable and H(f′(U_{m_{n}})) ≥ s_{n}.

Definition 3.8 (pseudoentropy generator). Let f : {0, 1}^{t_{n}} → {0, 1}^{ℓ_{n}} be a Ptime function ensemble and let s_{n} be a polynomial parameter. Then f is an R-secure pseudoentropy generator with pseudoentropy s_{n} if f(U_{t_{n}}) has R-secure computational entropy t_{n} + s_{n}.

If f is a pseudorandom generator, then it is easy to see that it is also a pseudoentropy generator. This is because f(U_{t_{n}}) and U_{ℓ_{n}} are computationally indistinguishable and by definition of a pseudorandom generator, ℓ_{n} > t_{n}. Consequently, H(U_{ℓ_{n}}) = ℓ_{n} ≥ t_{n} + 1; i.e., f is a pseudoentropy generator with pseudoentropy at least 1.

A false-entropy generator is a further generalization of pseudoentropy generator.

A false-entropy generator doesn’t necessarily amplify the input randomness; it just has the property that the output randomness is more computationally than it is statistically.

Definition 3.9 (false-entropy generator). Let f : {0, 1}^{t_{n}} → {0, 1}^{ℓ_{n}} be a Ptime function ensemble and let s_{n} be a polynomial parameter. Then f is an R-secure false-entropy generator with false entropy s_{n} if f(U_{t_{n}}) has R-secure computational entropy H(f(U_{t_{n}})) + s_{n}.

Note that, in the definition of computational entropy, the function ensemble f′ that is computationally indistinguishable from f is required to be P-time computable. This is consistent with the definition of a pseudorandom generator, where the distribution from which the pseudorandom generator is indistinguishable is the uniform distribution. There is also a nonuniform version of computational entropy, where f′ is not necessarily P-time computable, and corresponding nonuniform versions of a pseudoentropy generator and false-entropy generator. It turns out to be easier to construct a false-entropy generator f, where f′ is not necessarily P-time computable from a one-way function, than it is to construct a false-entropy generator f, where f′ is P-time samplable. Using this approach and a nonuniform version of Proposition 4.12,

[ILL89] describes a nonuniform reduction from a one-way function to a pseudorandom generator. However, a uniform reduction using Proposition 4.12 requires that f′ be P-time computable. Thus, one of the main difficulties in our constructions below is to build a false-entropy generator f, where f′ is P-time computable.

3.5. Hidden bits. In the construction of a pseudorandom generator from a oneway function, one of the key ideas is to construct from the one-way function another function which has an output bit that is computationally unpredictable from the other output bits (it is “hidden”) and yet statistically somewhat predictable from the other output bits. This idea is used in the original construction of a pseudorandom generator from the discrete logarithm problem [BM82] and has been central to all such constructions since that time.

Definition 3.10 (hidden bit). Let f : {0, 1}^{t_{n}} → {0, 1}^{ℓ_{n}} and b : {0, 1}^{t_{n}} → {0, 1} be P-time function ensembles. Let D : {0, 1}^{t_{n}} be a P-samplable probability ensemble, let X ∈_{D} {0, 1}^{t_{n}}, and let β ∈_{U} {0, 1}. Then b(X) is R-secure hidden given f(X) if ⟨f(X), b(X)⟩ and ⟨f(X), β⟩ are R-secure computationally indistinguishable.

3.6. Reductions. All the results presented in this paper involve a reduction from one type of primitive to another.

We make the following definitions to quantify the strength of reductions. The particular parameterization of security and the different quantitative measures of the security-preserving properties of a reduction are derived from [Luby96], [HL92].

Intuitively, a reduction constructs from a first primitive f on inputs of length t_{n} a second primitive g^{(f)} on inputs of length t′_{n}. The reduction also specifies an oracle TM M^{(·)} such that if there is an adversary A for breaking g^{(f)}, then M^{(A)} is an adversary for breaking f. How much security is preserved by the reduction is parameterized by S.

Definition 3.11 (reduction). Let t_{n} and t′_{n} be polynomial parameters and let S : N ×ℜ^{+} → ℜ^{+}. An S-reduction from primitive 1 to primitive 2 is a pair of oracles g^{(·)} and M^{(·)} so that the following hold:

• For each P-time function ensemble f : {0, 1}^{t_{n}} → {0, 1}^{ℓ_{n}} that instantiates primitive 1, g^{(f)} : {0, 1}^{t′_{n}} → {0, 1}^{ℓ′_{n}} instantiates primitive 2.

• g^{(f)} is a P-time function ensemble, and on inputs of length t′_{n}, it only makes calls to f on inputs of length t_{n}.

• Suppose A is an adversary with time–success ratio R′_{t′_{n}} for g^{(f)} on inputs of length t′_{n}. Define R_{t_{n}} = S(n, R′_{t′_{n}}). Then M^{(A)} is an adversary with time–success ratio R_{t_{n}} for f on inputs of length t_{n}.

To discuss the security-preserving properties of the reduction, we compare how well A breaks g^{(f)} with how well M^{(A)} breaks f on inputs of similar size. We say the reduction is

• linear-preserving if R_{N} = N^{O(1)} · O(R′_{N}),

• poly-preserving if R_{N} = N^{O(1)} · R′_{O(N)}^{O(1)},

• weak-preserving if R_{N} = N^{O(1)} · R′_{N^{O(1)}}^{O(1)}. A mildly nonuniform reduction has the same properties except that g^{(·)} and M^{(·)}

are both allowed access to an integer-valued polynomial parameter a_{n} that depends on f. The same notions of security preservation apply to mildly nonuniform reductions.

f can always be broken in time exponential in t_{n}. Therefore, if R′_{t′_{n}} ≥ 2^{t_{n}}, or even

R′_{t′_{n}} ≥ 2^{t_{n}^{Ω(1)}} = 2^{n^{Ω(1)}} in the case of a weak-preserving reduction, M^{(A)} can ignore the oracle and break f by brute force. Therefore, we can assume without loss of generality that R′_{t′_{n}} ≤ 2^{t_{n}}.

Obvious from the definition of reduction are the following propositions that say that security is preserved by reductions and that reductions can be composed.

Proposition 3.12. If (g^{(·)}, M^{(·)}) is a (mildly nonuniform) S-reduction from primitive 1 to primitive 2 and f is a (mildly nonuniform) P-time function ensemble that instantiates primitive 1 with security R_{t_{n}}, then g^{(f)} is a (mildly nonuniform) P-time function ensemble that instantiates primitive 2 with security R′_{t′_{n}}.

Proposition 3.13. If (g_{1}^{(·)}, M_{1}^{(·)}) is a (mildly nonuniform) S_{1}-reduction from primitive 1 to primitive 2, and if (g_{2}^{(·)}, M_{2}^{(·)}) is a (mildly nonuniform) S_{2}-reduction

from primitive 2 to primitive 3, then (g_{1}^{(g_{2}^{(·)})}, M_{1}^{(M_{2}^{(·)})}) is a (mildly nonuniform) Sreduction from primitive 1 to primitive 3, where S(N, R) = S_{2}(N, S_{1}(N, R)).

Although we phrase our definitions in terms of asymptotic complexity, one can easily interpret them for fixed length inputs in the context of an actual implementation, just as one does for algorithm analysis.

Clearly, in standard situations, t′_{n} ≥ t_{n} and R_{t_{n}} ≥ R′_{t′_{n}}, and the closer these two inequalities are to equalities the more the security of f is transferred to g. We now describe how the slack in these inequalities affects the security-preserving properties of the reduction.

The number of calls M^{(A)} makes to A is invariably either a constant or depends polynomially on the time–success ratio of A, and thus R_{t_{n}} is at most polynomial in R′_{t′_{n}}. The slackness in this inequality turns out not to be the major reason for a loss in security in the reduction; instead the loss primarily depends on how much larger t′_{n} is than t_{n}. If t′_{n} is much larger than t_{n}, then R_{t_{n}} is much larger as a function of t_{n} than R′_{t′_{n}} is as a function of t′_{n}. We can formalize this as follows.

Proposition 3.14.

• If t′_{n} = t_{n}, M^{(A)} runs in time polynomial in n (not counting the running time of A), and sp_{n}(M^{(A)}) = sp_{n}(A)/n^{O(1)}, then the reduction is linear-preser-ving.

• If t′_{n} = O(t_{n}), M^{(A)} runs in time polynomial in R′_{t′_{n}}, and sp_{n}(M^{(A)}) =

sp_{n}^{O(1)}(A)/n^{O(1)}, then the reduction is poly-preserving.

• If t′_{n} = t_{n}^{O(1)}, M^{(A)} runs in time polynomial in R′_{t′_{n}}, and sp_{n}(M^{(A)}) =

sp_{n}^{O(1)}(A)/n^{O(1)}, then the reduction is weak-preserving.

It is important to design the strongest reduction possible. The techniques described in this paper can be directly used to yield poly-preserving reductions from regular or nearly regular (with polynomial time computable degree of regularity) oneway functions to pseudorandom generators [Luby96], and this covers almost all the conjectured one-way functions. However, the reduction for general one-way functions is only weak-preserving.

4. Hidden bits, hash functions, and computational entropy.

4.1. Constructing a hidden bit. How do we go about constructing a function such that one of its output bits is computationally unpredictable yet statistically correlated with its other output bits? The following fundamental proposition of [GL89] (strengthened in [Levin93]) provides the answer.

Proposition 4.1. Let f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} be a one-way function. Then X ⊙R is hidden given ⟨f(X), R⟩, where X, R ∈_{U} {0, 1}^{n}. The reduction is linear-preserving with respect to the alternative definition of computationally indistinguishable.

Proposition 4.1 presents an elegant, simple, and general method of obtaining a hidden bit from a one-way function. We need the following stronger proposition of [GL89] (see also [Levin93]) in some of our proofs.

Proposition 4.2. There is an oracle TM M with the following properties: Let A be any adversary that accepts as input n bits and outputs a single bit. Then M^{(A)} on input parameter δ_{n} > 0 outputs a list L of n-bit strings with the following property: For any fixed x ∈ {0, 1}^{n}, if it is the case that

| Pr[A(R) = x ⊙ R] − Pr[A(R) ≠ x ⊙ R]| ≥ δ_{n},

where R ∈_{U} {0, 1}^{n}, then, with probability at least 1/2, it is the case that x ∈ L. (The probability here depends only on the values of the random bits used by M^{(A)}.) The running time of M^{(A)} is polynomial in n, 1/δ_{n}, and the running time of A. Also, the number of n-bit strings in L is bounded by O(1/δ_{n}^{2}).

The following proposition is an immediate consequence of Proposition 4.1 and Definition 3.10.

Proposition 4.3. Let f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} be a one-way function. Then ⟨f(X), R, X⊙R⟩ and ⟨f(X), R, β⟩ are computationally indistinguishable, where X, R ∈_{U} {0, 1}^{n} and β ∈_{U} {0, 1}. The reduction is linear-preserving with respect to the alternative definition of computationally indistinguishable.

4.2. One-way permutation to a pseudorandom generator. We describe a way to construct a pseudorandom generator from any one-way permutation which is substantially simpler (and has stronger security-preserving properties) than the original construction of [Yao82]. The construction and proof described here is due to [GL89].

Proposition 4.4. Let f : {0, 1}^{n} → {0, 1}^{n} be a one-way permutation. Let x, r ∈ {0, 1}^{n} and define P-time function ensemble g(x, r) = ⟨f(x), r, x ⊙ r⟩. Then g is a pseudorandom generator. The reduction is linear-preserving with respect to the alternative definition of computationally indistinguishable.

Proof. Let X, R ∈_{U} {0, 1}^{n}, and β ∈_{U} {0, 1}. Because f is a permutation, ⟨f(X), R, β⟩ is the uniform distribution on {0, 1}^{2n+1}. By Proposition 4.3, g(X, R) and ⟨f(X), R, β⟩ are computationally indistinguishable, where the reduction is linearpreserving with respect to the alternative definition of computationally indistinguishable.

Proposition 4.4 works when f is a permutation because (1) f(X) is uniformly distributed and hence already looks random;

(2) for any x ∈ {0, 1}^{n}, f(x) uniquely determines x. So no entropy is lost by the

application of f. For a general one-way function neither (1) nor (2) necessarily holds. Intuitively, the rest of the paper constructs a one-way function with properties (1) and (2) from a general one-way function. This is done by using hash functions to smooth the entropy of f(X) to make it more uniform and to recapture the entropy of X lost by the application of f(X).

Proposition 4.4 produces a pseudorandom generator that only stretches the input by one bit. To construct a pseudorandom generator that stretches by many bits, combine this with the construction described previously in Proposition 3.6.

4.3. One-to-one one-way function to a pseudoentropy generator. We now describe a construction of a pseudoentropy generator from any one-to-one oneway function. This construction, together with Theorem 4.14, yields a pseudorandom generator from any one-to-one one-way function. The overall construction is different in spirit than the original construction of [GKL93]: it illustrates how to construct a pseudoentropy generator in a particularly simple way using [GL89]. Although the assumptions and the consequences are somewhat different, the construction is the same as described in Proposition 4.4.

Proposition 4.5. Let f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} be a one-to-one one-way function. Let x, r ∈ {0, 1}^{n} and define P-time function ensemble g(x, r) = ⟨f(x), r, x ⊙ r⟩. Then g is a pseudoentropy generatorw̃ith pseudoentropy 1. The reduction is linearpreserving with respect to the alternative definition of computationally indistinguishable.

Proof. Let X, R ∈_{U} {0, 1}^{n} and β ∈_{U} {0, 1}. Proposition 4.3 shows that g(X, R) and ⟨f(X), R, β⟩ are computationally indistinguishable, where the reduction is linearpreserving with respect to the alternative definition of computationally indistinguishable. Because f is a one-to-one function and β is a random bit, H(f(X), R, β) = 2n+1, and thus g(X, R) has pseudoentropy 1.

Note that it is not possible to argue that g is a pseudorandom generator. For example, let f(x) = ⟨0, f′(x)⟩, where f′ is a one-way permutation. Then f is a oneto-one one-way function and yet g(X, R) = ⟨f(X), R, X ⊙ R⟩ is not a pseudorandom generator, because the first output bit of g is zero independent of its inputs, and thus its output can easily be distinguished from a uniformly chosen random string.

4.4. Universal hash functions. The concept of a universal hash function, introduced in [CW79], has proved to have a far-reaching and broad spectrum of applications in the theory of computation.

Definition 4.6 (universal hash functions). Let h : {0, 1}^{ℓ_{n}} × {0, 1}^{n} → {0, 1}^{m_{n}} be a P-time function ensemble. Recall from Definition 2.9 that for fixed y ∈ {0, 1}^{ℓ_{n}}, we view y as describing a function h_{y}(·) that maps n bits to m_{n} bits. Then h is a (pairwise independent) universal hash function if, for all x ∈ {0, 1}^{n}, x′ ∈ {0, 1}^{n} \ {x}, and for all a, a′ ∈ {0, 1}^{m_{n}},

Pr[(h_{Y} (x) = a) and (h_{Y} (x′) = a′)] = 1/2^{2m_{n}},

where Y ∈_{U} {0, 1}^{ℓ_{n}}.

Intuitively, a universal hash function has the property that every distinct pair x and x′ are mapped randomly and independently with respect to Y.

In all of our constructions of function ensembles using universal hash functions, the description of the hash function y is viewed as a public input to the function ensemble and thus is also part of the output. The following construction of a universal hash function is due to [CW79].

Definition 4.7 (matrix construction). Let

h : {0, 1}^{(n+1)m_{n}} × {0, 1}^{n} → {0, 1}^{m_{n}}

be the following P-time function ensemble: For x ∈ {0, 1}^{n} and y ∈ {0, 1}^{(n+1)×m_{n}}, h_{y}(x) = ⟨x, 1⟩ ⊙ y.

We concatenate a 1 to x in the above definition to cover the case when x = 0^{n}. Hereafter, whenever we refer to universal hash functions, one can think of the construction given above. However, any universal hash function that satisfies the required properties may be used. We note that there are more efficient hash functions in terms of the number of bits used in specification. One such example is using Toeplitz matrices (see for example [GL89] or [Levin93]). A Toeplitz matrix is a matrix that is constant on any diagonal, and thus to specify an n×m Toeplitz matrix we can specify values for the m + n − 1 diagonals. This is the simplest bit-efficient construction of a universal hash function, so we adopt it as the default for the remainder of the paper.

4.5. Smoothing distributions with hashing. The following lemma is a key component in most of the subsequent reductions we describe.

Lemma 4.8. Let D : {0, 1}^{n} be a probability ensemble that has Renyi entropy at least m_{n}. Let e_{n} be a positive-integer-valued parameter. Let h : {0, 1}^{ℓ_{n}} × {0, 1}^{n} → {0, 1}^{m_{n}−2e_{n}} be a universal hash function. Let X ∈_{D} {0, 1}^{n}, Y ∈_{U} {0, 1}^{ℓ_{n}}, and Z ∈_{U} {0, 1}^{m_{n}−2e_{n}}. Then

L_{1}(⟨h_{Y} (X), Y ⟩, ⟨Z, Y ⟩) ≤ 2^{−(e_{n}+1)}.

This lemma is a generalization of a lemma that appears in [S83]. There, D is the uniform distribution on a set S ⊆ {0, 1}^{n} with ♯S = 2^{m_{n}}. The papers [McIn87] and [BBR88] also proved similar lemmas. For the special case of linear hash functions, this lemma can be derived from [GL89] by considering unlimited adversaries. A generalization to a broader class of hash functions appears in [IZ89].

The lemma can be interpreted as follows: the universal hash function smooths out the Renyi entropy of X to the almost uniform distribution on bit strings of length almost m_{n}. The integer parameter e_{n} controls the trade-off between the uniformity of the output bits of the universal hash function and the amount of entropy lost in the smoothing process. Thus, we have managed to convert almost all the Renyi entropy of X into uniform random bits while maintaining our original supply of random bits Y.

Proof. Let ℓ = ℓ_{n}, e = e_{n}, m = m_{n}, and s = m − 2e. For all y ∈ {0, 1}^{ℓ}, a ∈ {0, 1}^{s}, and x ∈ {0, 1}^{n}, define X (h_{y}(x) = a) = 1 if h_{y}(x) = a and 0 otherwise. We want to show that

E_{Y} [ ∑_{a∈{0,1}^{s}} |E_{X}[X (h_{Y} (X) = a)] − 2^{−s}|] /2 ≤ 2^{−(e+1)}.

We show below that for all a ∈ {0, 1}^{s},

E_{Y} [|E_{X}[X (h_{Y} (X) = a)] − 2^{−s}|] ≤ 2^{−(s+e)},

and from this the proof follows.

For any random variable Z, E[|Z|^{2}] ≥ E[|Z|]^{2} by Jensen’s inequality. Letting Z = E[X (h_{Y} (X) = a)] − 2^{−s}, we see that it is sufficient to show for all a ∈ {0, 1}^{s},

E_{Y} [(E_{X}[X (h_{Y} (X) = a)] − 2^{−s})^{2}] ≤ 2^{−2(s+e)}.

Let X′ ∈_{D} {0, 1}^{n}. Using some elementary expansion of terms and rearrangements of summation, we can write the above as

E_{X,X′}[E_{Y} [(X (h_{Y} (X) = a) − 2^{−s})(X (h_{Y} (X′) = a) − 2^{−s})]].

For each fixed value of X to x and X′ to x′, where x ≠ x′, the expectation with respect to Y is zero because of the pairwise independence property of universal hash functions. For each fixed value of X to x and X′ to x′, where x = x′,

E[(X (h_{Y} (x) = a) − 2^{−s})^{2}] = 2^{−s}(1 − 2^{−s}) ≤ 2^{−s}.

Because the Renyi entropy of D is at least m, it follows that Pr[X = X′] ≤ 2^{−m}. Thus, the entire sum is at most 2^{−(m+s)}, which is equal to 2^{−2(s+e)} by the definition of s.

In this lemma, D is required to have Renyi entropy at least m_{n}. In many of our applications, the distribution in question has at least Renyi entropy m_{n}, and thus the lemma applies because of Proposition 2.5. For other applications, we need to work with Shannon entropy. The following technical result due to [S48] allows us to convert Shannon entropy to Renyi entropy by looking at product distributions.

Proposition 4.9. Let k_{n} be an integer-valued polynomial parameter.

• Let D : {0, 1}^{n} be a probability ensemble. There is a probability ensemble

E : {0, 1}^{nk_{n}} satisfying – H_{Ren}(E) ≥ k_{n}H(D) − nk_{n}^{2/3},

– L_{1}(E, D^{k_{n}}) ≤ 2^{−k_{n}^{1/3}}.

• Let D_{1} : {0, 1}^{n} and D_{2} : {0, 1}^{n} be not necessarily independent probability ensembles; let D = ⟨D_{1}, D_{2}⟩. There is a probability ensemble E : {0, 1}^{2nk_{n}}, with E = ⟨E_{1}, E_{2}⟩, satisfying the following:

– For every value E_{1} ∈ {0, 1}^{nk_{n}} such that Pr_{E_{1}}[E_{1}] > 0, H_{Ren}(E_{2}|E_{1} = E_{1}) ≥ k_{n}H(D_{2}|D_{1}) − nk_{n}^{2/3}.

– L_{1}(E, D^{k_{n}}) ≤ 2^{−k_{n}^{1/3}}. Corollary 4.10. Let k_{n} be an integer-valued P-time polynomial parameter. • Let D : {0, 1}^{n} be a probability ensemble, let m_{n} = k_{n}H(D) − 2nk_{n}^{2/3}, and let h : {0, 1}^{p_{n}} × {0, 1}^{nk_{n}} → {0, 1}^{m_{n}} be a universal hash function. Let

X′ ∈_{D^{kn}} {0, 1}^{k_{n}×n} and let Y ∈_{U} {0, 1}^{p_{n}}. Then
L_{1}(⟨h_{Y} (X′), Y ⟩, U_{m_{n}+p_{n}}) ≤ 2^{1−k_{n}^{1/3}}.

• Let D_{1} : {0, 1}^{n} and D_{2} : {0, 1}^{n} be not necessarily independent probability ensembles, and let D = ⟨D_{1}, D_{2}⟩. Let m_{n} = k_{n}H(D_{2}|D_{1}) − 2nk_{n}^{2/3}. Let h : {0, 1}^{p_{n}} × {0, 1}^{nk_{n}} → {0, 1}^{m_{n}} be a universal hash function. Let

⟨X′_{1}, X′_{2}⟩ ∈_{D^{kn}} {0, 1}^{k_{n}×2n} and let Y ∈_{U} {0, 1}^{p_{n}}. Then
L_{1}(⟨h_{Y} (X′_{2}), Y, X′_{1}⟩, ⟨U_{m_{n}+p_{n}}, X′_{1}⟩) ≤ 2^{1−k_{n}^{1/3}}.

Proof. For the proof, combine Proposition 4.9, Lemma 4.8, Proposition 2.2, and Proposition 2.5.

4.6. Pseudoentropy generator to a pseudorandom generator. Let f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} be a pseudoentropy generator with pseudoentropy s_{n}. In this subsection, we construct a pseudorandom generator based on f. We first start with two preliminary propositions. The following proposition is the computational analogue of Proposition 2.2.

Proposition 4.11. Let D : {0, 1}^{n} and E : {0, 1}^{n} be two probability ensembles and let f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} be a P-time function ensemble. Let D and E be computationally indistinguishable. Then f(D) and f(E) are computationally indistinguishable. The reduction is linear-preserving.

The following proposition first appeared in [GM84].

Proposition 4.12. Let k_{n} be an integer-valued P-time polynomial parameter. Let D : {0, 1}^{ℓ_{n}} and E : {0, 1}^{ℓ_{n}} be P-samplable probability ensembles. Let D and E be computationally indistinguishable. Then D^{k_{n}} and E^{k_{n}} are computationally indistinguishable. The reduction is weak-preserving.

More precisely, there is a probabilistic oracle TM M with the following properties: If A is an R′_{nk_{n}}-breaking adversary for distinguishing D^{k_{n}} and E^{k_{n}}, then M^{(A)} is an R_{n}-breaking adversary for distinguishing D and E, where R_{n} is essentially equal to k_{n}R′_{nk_{n}}. It is crucial that D and E are P-samplable because the sampling algorithms are used by M. The reduction is only weak-preserving because distinguishing D^{k_{n}} and E^{k_{n}} with respect to private inputs of length nk_{n} only translates into distinguishing D and E on private inputs of length n.

We now give the construction of a pseudorandom generator g from a pseudoentropy generator f.

Construction 4.13. Let f : {0, 1}^{n} → {0, 1}^{m_{n}} be a P-time function ensemble and let s_{n} be a P-time polynomial parameter. Let k_{n} = (⌈(2m_{n} + 1)/s_{n}⌉)^{3} and j_{n} = ⌊k_{n}(n + s_{n}) − 2m_{n}k_{n}^{2/3}⌋. Let h : {0, 1}^{p_{n}} × {0, 1}^{k_{n}m_{n}} → {0, 1}^{j_{n}} be a universal hash function. Let u ∈ {0, 1}^{k_{n}×n}, y ∈ {0, 1}^{p_{n}}, and define P-time function ensemble g(u, y) = ⟨h_{y}(f^{k_{n}}(u)), y⟩.

Theorem 4.14. Let f and g be as described in Construction 4.13. Let f be a pseudoentropy generator with pseudoentropy s_{n}. Then g is a pseudorandom generator. The reduction is weak-preserving.

Proof. Let f′ : {0, 1}^{n′_{n}} → {0, 1}^{m_{n}} be the P-time function ensemble that witnesses the pseudoentropy generator of f as guaranteed in Definition 3.7 of computational entropy; i.e., f′(X′) and f(X) are R-secure computationally indistinguishable and H(f′(X′)) ≥ n + s_{n}, where X ∈_{U} {0, 1}^{n} and X′ ∈_{U} {0, 1}^{n′_{n}}. Let U ∈_{U} {0, 1}^{k_{n}×n}, W ∈_{U} {0, 1}^{k_{n}×n′_{n}}, and Y ∈_{U} {0, 1}^{p_{n}}. By Proposition 4.12, f^{k_{n}}(U) and f′^{k_{n}}(W) are computationally indistinguishable. From Proposition 4.11, it follows that g(U, Y) = ⟨h_{Y} (f^{k_{n}}(U)), Y ⟩ and ⟨h_{Y} (f′^{k_{n}}(W)), Y ⟩ are computationally indistinguishable. Because H(f′(X′)) ≥ n + s_{n}, by choice of k_{n} and j_{n}, using Corollary 4.10, it follows that L_{1}(⟨h_{Y} (f′^{k_{n}}(W)), Y ⟩, U_{j_{n}+p_{n}}) ≤ 2^{−k_{n}^{1/3}}. Thus, it follows that g(U, Y) and U_{j_{n}+p_{n}} are computationally indistinguishable. Note that by choice of k_{n}, the output length j_{n} + p_{n} of g is longer than its input length nk_{n} + p_{n}.

4.7. False entropy generator to a pseudoentropy generator. Let f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} be a false-entropy generator with false entropy s_{n}. In this subsection, we construct a mildly nonuniform pseudoentropy generator based on f. An idea is to extract D̃_{f}(f(X)) bits of entropy out of X without compromising the false entropy. (See section 2.3 for the definition of D̃_{f}.) Let X ∈_{U} {0, 1}^{n}. The major obstacles are that D̃_{f} is not necessarily a P-time function ensemble and that f could be a very nonregular function, and thus the variance of D̃_{f}(f(X)) could be quite high as a function of X, and we cannot guess its value consistently with accuracy.

Let k_{n} be an integer-valued P-time polynomial parameter and let U ∈_{U} {0, 1}^{k_{n}×n}. The intuition behind the following construction is that the false entropy of f^{k_{n}} is k_{n} times that of f and that the degeneracy of f^{k_{n}} is k_{n} times that of f. Furthermore, if k_{n} is large enough then, with high probability with respect to U, D̃_{f^{kn}} (f^{k_{n}}(U)) is close to the degeneracy of f^{k_{n}}. Thus we use a universal hash function h to extract roughly the degeneracy of f^{k_{n}}(U) bits of entropy out of U without compromising the false entropy of f^{k_{n}}(U).

Construction 4.15. Let f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} be a P-time function ensemble. Let s_{n} be a P-time polynomial parameter and assume for simplicity that s_{n} ≤ 1. Let e_{n} be an approximation of H(f(X)) to within an additive factor of s_{n}/8, where X ∈_{U} {0, 1}^{n}. Fix k_{n} = ⌈(4n/s_{n})^{3}⌉ and j_{n} = ⌈k_{n}(n − e_{n}) − 2nk_{n}^{2/3}⌉. Let h : {0, 1}^{p_{n}} × {0, 1}^{nk_{n}} → {0, 1}^{j_{n}} be a universal hash function. For u ∈ {0, 1}^{k_{n}×n} and r ∈ {0, 1}^{p_{n}}, define P-time function ensemble

g(e_{n}, u, r) = ⟨f^{k_{n}}(u), h_{r}(u), r⟩.

Lemma 4.16. Let f and g be as described in Construction 4.15. Let f be a falseentropy generator with false entropy s_{n}. Then g is a mildly nonuniform pseudoentropy generator with pseudoentropy 1. The reduction is weak-preserving.

Proof. Let Z ∈_{U} {0, 1}^{j_{n}}. First, note that H(X|f(X)) = n − H(f(X)) = n − e_{n}. From this and Corollary 4.10 (letting X_{1} = f(X), X_{2} = X in the corollary), it follows that L_{1}(g(e_{n}, U, R,), ⟨f^{k_{n}}(U), Z, R⟩) ≤ 2^{−k_{n}^{1/3}}.

We now prove that g(e_{n}, U, R) has computational entropy at least p_{n} + nk_{n} + 1. Let D : {0, 1}^{ℓ_{n}} be the P-samplable probability ensemble such that D and f(X) are computationally indistinguishable and such that

H(D) ≥ H(f(X)) + s_{n}.

Since D and f(X) are computationally indistinguishable, ⟨f^{k_{n}}(U), Z, R⟩ and ⟨D^{k_{n}}, Z, R⟩ are computationally indistinguishable by Proposition 4.12, which together with the first claim implies that g(e_{n}, U, R) and ⟨D^{k_{n}}, Z, R⟩ are computationally indistinguishable. Now,

H(D^{k_{n}}, Z, R) ≥ k_{n} · (H(f(X)) + s_{n}) + j_{n} + p_{n} ≥ k_{n}(e_{n} + 7s_{n}/8) + j_{n} + p_{n},

and because by choice of k_{n} and j_{n} this is at least p_{n} + nk_{n} + 1. Thus g has computational entropy at least p_{n} + nk_{n} + 1, and the lemma follows.

4.8. Mildly nonuniform to a uniform pseudorandom generator.

Proposition 4.17. Let a_{n} be any value in {0, …, k_{n}}, where k_{n} is an integervalued P-time polynomial parameter. Let g : {0, 1}^{⌈log(k_{n})⌉} × {0, 1}^{n} → {0, 1}^{ℓ_{n}} be a P-time function ensemble, where ℓ_{n} > nk_{n}. Let x′ ∈ {0, 1}^{k_{n}×n} and define P-time function ensemble g′(x′) = ⊕_{i=1}^{k_{n}}g(i, x′_{i}). Let g be a mildly nonuniform pseudorandom generator when the first input is set to a_{n}. Then g′ is a pseudorandom generator. The reduction is weak-preserving.

Proof. Let X ∈_{U} {0, 1}^{n}, X′ ∈_{U} {0, 1}^{k_{n}×n}, and Z ∈_{U} {0, 1}^{ℓ_{n}}. Suppose there is an adversary A that has distinguishing probability

sp_{n}(A) = |Pr[A(g′(X′)) = 1] − Pr[A(Z) = 1]| .

We describe an oracle TM M such that, for all i = 1, …, k_{n}, M^{(A)}(i) has sp_{n}(A) distinguishing probability for g(i, X) and Z. For all i, the running time for M^{(A)}(i) is the running time for A plus the time to compute the output of g on k_{n} − 1 inputs. This works with respect to all i, in particular when i = a_{n}, from which the result follows.

For each i = 1, …, k_{n}, M^{(A)}(i) works as follows. On input u (and i), M^{(A)}(i) randomly generates x′_{1}, …, x′_{i−1}, x′_{i+1}, …, x′_{k_{n}} ∈_{U} {0, 1}^{n} and computes v = ⊕_{j≠i}g(j, x′_{j}) ⊕ u. Then M^{(A)}(i) runs A on input v and outputs A(v). By the nature of ⊕, if u is chosen randomly according to Z, then M^{(A)}(i) = 1 with probability Pr[A(Z) = 1], whereas if u is chosen randomly according to g(i, X), then M^{(A)}(i) = 1 with probability Pr[A(g′(X′)) = 1]. Thus, for each value of i, M^{(A)}(i) has distinguishing probability sp_{n}(A) for g(i, X) and Z.

Note that it may be the case that, for most fixed values of i ∈ {1, …, k_{n}}, g(i, X) is completely predictable. On the other hand, even if there is a value a_{n} for each n such that g(a_{n}, X) is pseudorandom, the value of a_{n} may not be P-time computable. This is exactly the case when the lemma is useful; i.e., it is useful to transform the mildly nonuniform pseudorandom generator g into a pseudorandom generator g′.

Note that in the given construction the length of the output of g′ on inputs of length nk_{n} is ℓ_{n} > nk_{n}, and thus g′ stretches the input to a string of strictly greater length.

This reduction is only weak-preserving, and the reason is the usual one; i.e., the breaking adversary for g′(X′) on inputs of length nk_{n} is transferred into a breaking adversary for g(i, X) on inputs of length only n.

If g in Proposition 4.17 does not satisfy the property that ℓ_{n} > nk_{n}, then for each fixed i we can use Proposition 3.6 to stretch the output of g(i, x) (viewed as a function of x) into a string of length longer than nk_{n} and then exclusive-or together the stretched outputs.

4.9. Summary. Putting together the results in this section, we have

• a reduction from a one-way permutation to a pseudorandom generator (from subsection 4.2);

• a reduction from a one-to-one one-way function to a pseudorandom generator(combining subsections 4.3 and 4.6);

• a reduction from a pseudoentropy generator to a pseudorandom generator (from subsection 4.6);

• a reduction from a false-entropy generator to a pseudorandom generator (combining subsections 4.7, 4.6, and 4.8).

5. Extracting entropy from one-way functions. In this section we show how to construct a pseudoentropy generator from any one-way function f with the additional property that the number of inverses of f can be computed in polynomial time; i.e., the function D̃_{f} is a P-time function ensemble. Combined with the results summarized in subsection 4.9, this gives a construction of a pseudorandom generator from a one-way function with this property.

One of the reasons for giving the first construction is because it illustrates some of the additional ideas needed for our construction of a false-entropy generator from any one-way function. A general one-way function f does not necessarily have the property that D̃_{f} is a P-time function ensemble, and considerably more effort is needed to construct a pseudorandom generator from it. In the next section, we describe how to construct a false-entropy generator from any one-way function. Combined with the results summarized in subsection 4.9, this gives a construction of a pseudorandom generator from any one-way function.

5.1. One-way function with approximable preimage sizes to a pseudoentropy generator. To see where we get into trouble with the construction given in Proposition 4.5, suppose f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} is a 2^{n/4}-regular one-way function, and let X, R ∈_{U} {0, 1}^{n} and β ∈_{U} {0, 1}. Then, although ⟨f(X), R, X ⊙ R⟩ and ⟨f(X), R, β⟩ are computationally indistinguishable, H(f(X), R, X ⊙ R) is only about 7n/4 + 1, and thus we have lost about n/4 bits of the input entropy through the application of f. Similarly, although X ⊙ R is hidden given ⟨f(X), R⟩, it is also almost completely statistically uncorrelated.

The way to overcome these problems is to create a new function which is the original one-way function concatenated with the degeneracy of the function number of bits hashed out of its input to regain the lost entropy. Then Proposition 4.5 can be applied to the new function to obtain a pseudoentropy generator. We first show how to construct a pseudoentropy generator in the case when D̃_{f} is a P-time function ensemble.

Construction 5.1. Let f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} be a P-time function ensemble and suppose that D̃_{f} is a P-time function ensemble. Let h : {0, 1}^{p_{n}} × {0, 1}^{n} → {0, 1}^{n+2} be a universal hash function. For x ∈ {0, 1}^{n} and y ∈ {0, 1}^{p_{n}}, define P-time function ensemble

f′(x, y) = ⟨f(x), h_{y}(x)_{{1,...,D̃_{f} (f(x))+2}}, y⟩.

Lemma 5.2. Let f and f′ be as described in Construction 5.1.

(1) Let f be a one-way function. Then f′ is a one-way function. The reduction is poly-preserving.

(2) Let X ∈_{U} {0, 1}^{n} and Y ∈_{U} {0, 1}^{p_{n}}. Then H(f′(X, Y)) ≥ n + p_{n} − 1/2. Proof of Lemma 5.2(1). Suppose adversary A inverts f′(X, Y) with probability

δ_{n} in time T_{n}. We prove that the following oracle TM M using A on input z = f(x) finds x′ ∈ pre_{f}(z) with probability at least δ_{n}^{3}/128 when x ∈_{U} {0, 1}^{n}.

Description of M^{(A)}(z). Compute D̃_{f}(z). Choose α ∈_{U} {0, 1}^{D̃_{f} (z)+2}. Choose y ∈_{U} {0, 1}^{p_{n}}. If A(z, α, y) outputs x′ with f(x′) = z then output x′.

Let j_{n} = 2 ⌈log(2/δ_{n})⌉. For all z ∈ range_{f}, for all y ∈ {0, 1}^{p_{n}}, define random variable

β_{z,y} = h_{y}(W)_{{1,...,D̃_{f} (z)−j_{n}}},

where W ∈_{U} pre_{f}(z). Then the probability that there is a γ ∈ {0, 1}^{2+j_{n}} such that A inverts f on input ⟨f(X), ⟨β_{f(X),Y} , γ⟩, Y ⟩ is at least δ_{n}.

Fix z ∈ range_{f}, and let β′_{z} ∈_{U} {0, 1}^{D̃_{f} (z)−j_{n}}. By Lemma 4.8,

L_{1}(⟨β_{z,Y} , Y ⟩, ⟨β′_{z}, Y ⟩) ≤ δ_{n}/2.

Therefore, the probability that there is a γ ∈ {0, 1}^{2+j_{n}} such that A inverts f on input ⟨f(X), ⟨β′_{f(X)}, γ⟩, Y ⟩ is at least δ_{n}/2. If we choose γ ∈_{U} {0, 1}^{2+j_{n}}, we have that the probability that A inverts f(X) on input ⟨f(X), ⟨β′_{f(X)}, γ⟩, Y ⟩ is at least

2^{−(2+j_{n})} · \frac{δ_{n}}{2} ≥ \frac{δ_{n}^{3}}{128}.

Note that this is the input distribution in the call to A within M^{(A)}. Note also that the run time of M^{(A)} is dominated by the time to run A. Thus, the time–success ratio of M^{(A)} for inverting f′ is about 128T_{n}/δ_{n}^{3}.

Proof of Lemma 5.2(2). Fix z ∈ range_{f} and let x, x′ ∈ pre_{f}(z) such that x ≠ x′. From the properties of a universal hash function,

Pr[h_{Y} (x)_{\{1,...,D̃_{f} (z)+2\}} = h_{Y} (x′)_{\{1,...,D̃_{f} (z)+2\}}] = 2^{−(D̃_{f} (z)+2)} ≤ \frac{1}{4 · ♯pre_{f}(z)}.

By calculating the Renyi entropy it follows that

H(f′(X, Y)) ≥ − log (\frac{5}{4} · 2^{−n+p_{n}}) = n + p_{n} + 2 − log(5).

The result follows since log(5) ≤ 5/2.

Corollary 5.3. Let f, h, and f′ be as described in Construction 5.1. Let r ∈ {0, 1}^{n} and define P-time function ensemble g(x, y, r) = ⟨f′(x, y), r, x ⊙ r⟩. Let f be a one-way function. Then g is a pseudoentropy generator with pseudoentropy 1/2. The reduction is poly-preserving.

Proof. The proof is the same as the proof of Proposition 4.5. Let X, R ∈_{U} {0, 1}^{n}, Y ∈_{U} {0, 1}^{p_{n}}, and β ∈_{U} {0, 1}. From Lemma 5.2 (1) and Proposition 4.3 it follows that g(X, Y, R) and ⟨f′(X, Y), R, β⟩ are computationally indistinguishable, where the reduction is poly-preserving. From Lemma 5.2 (2) it follows that H(f′(X, Y), R, β) ≥ 2n + p_{n} + 1/2. On the other hand, the input entropy to g(X, Y, R) is 2n + p_{n}, and thus it follows that g has pseudoentropy 1/2.

Theorem 5.4. A pseudorandom generator can be constructed from a one-way function f where D̃_{f} is a P-time function ensemble. The reduction is weak-preser-ving.

Proof. For the proof, combine Construction 5.1 with Construction 4.13, and use Corollary 5.3 and Theorem 4.14.

The following theorem, an easy corollary of Theorem 5.4, was previously obtained by [GKL93] using a different construction and proof techniques.

Theorem 5.5. Let f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} be a σ_{n}-regular one-way function, where σ_{n} is a P-time polynomial parameter. Then a pseudorandom generator can be constructed from f. The reduction is weak-preserving.

Proof. Note that in this case D̃_{f}(f(x)) = ⌈log(σ_{n})⌉ for all x ∈ {0, 1}^{n}. Furthermore, ⌈log(σ_{n})⌉ ∈ {0, …, n}. Using this, combining Construction 5.1 with Construction 4.13, and using Corollary 5.3 and Theorem 4.14 yield a mildly nonuniform pseudorandom generator. Then Proposition 4.17 shows how to construct a pseudorandom generator from this.

Based on the ideas presented above, [Luby96, Theorems 10.1 and 9.3] gives versions of Theorems 5.4 and 5.5 where the reduction is poly-preserving when the security parameter is P-time computable.

6. Any one-way function to a false-entropy generator.

6.1. Finding determined hidden bits. The final step in the general construction of a pseudorandom generator from a one-way function is to construct a false-entropy generator from any one-way function. This is the technically most difficult part of this paper. This construction uses some of the ideas from Construction 5.1. Let

f : {0, 1}^{n} → {0, 1}^{ℓ_{n}} (6.1)

be a one-way function and let

h : {0, 1}^{p_{n}} × {0, 1}^{n} → {0, 1}^{n+⌈log(2n)⌉} (6.2)

be a universal hash function. Similar to Construction 5.1, for x ∈ {0, 1}^{n}, i ∈ {0, …, n − 1}, and r ∈ {0, 1}^{p_{n}}, define P-time function ensemble

f′(x, i, r) = ⟨f(x), h_{r}(x)_{{1,...,i+⌈log(2n)⌉}}, i, r⟩. (6.3)

Note that from Lemma 5.2, the restricted function f′(x, D̃_{f}(f(x)), r) is an almost one-to-one one-way function, except that this is not necessarily a P-time function ensemble since D̃_{f} may not be a P-time function ensemble, and this is the main difficulty we must overcome.

Let X ∈_{U} {0, 1}^{n}, R ∈_{U} {0, 1}^{p(n)}, Y ∈_{U} {0, 1}^{n}, and β ∈_{U} {0, 1}. From the proof of Lemma 5.2 and Corollary 5.3, we claim and formalize below that if i ≤ D̃_{f}(f(X)), then a time limited adversary cannot distinguish X⊙Y from β given Y and f′(X, i, R).

Let

T = {⟨x, i⟩|x ∈ {0, 1}^{n}, i ∈ {0, …, D̃_{f}(f(x))}},
\overline{T} = \{⟨x, i⟩|x ∈ \{0, 1\}^{n}, i ∈ \{D̃_{f}(f(x)) + 1, …, n − 1\}\}.

Lemma 6.1. Let W = ⟨X̃, Ĩ⟩ ∈_{U} T , R ∈_{U} {0, 1}^{p(n)}, Y ∈_{U} {0, 1}^{n}, and β ∈_{U} {0, 1}. Let f be a one-way function. Then

⟨f′(W, R), X̃ ⊙ Y, Y ⟩ and ⟨f′(W, R), β, Y ⟩

are computationally indistinguishable. The reduction is poly-preserving.

Proof. Let A be an R′-breaking adversary for distinguishing the two distributions. Then A is also an R′-breaking adversary for hidden bit X̃ ⊙ Y given ⟨f′(W, R), Y ⟩. Then, from Proposition 4.2, there is an oracle TM M′ such that M^{′(A)} is an R′′- breaking adversary for inverting f′(W, R), where R′′(n) = n^{O(1)} · R′(n)^{O(1)}. Finally, we use the same idea as in Lemma 5.2; i.e., the success probability of M^{′(A)} on input ⟨f(x), α, i, R⟩ for α ∈_{U} {0, 1}^{i+⌈log(2n)⌉} is at least inverse polynomial in the success probability of M^{′(A)} on input f′(x, i, R) for each fixed ⟨x, i⟩ ∈ T . Consider the following oracle TM N: N^{A} on input f(x) chooses i ∈_{U} {0, …, n − 1}, α ∈_{U} {0, 1}^{i+⌈log(2n)⌉}, and r ∈_{U} {0, 1}^{p_{n}} and runs M^{′(A)} on input ⟨f(x), α, i, r⟩. Since Pr[⟨x, i⟩ ∈ T ] ≥ 1/n when i ∈_{U} {0, …, n − 1}, it follows that N^{A}(f(X)) produces an inverse with probability at least 1/n times the probability M^{′(A)}(f′(W, R)) produces an inverse.

If i ≥ D̃_{f}(f(X)), then X is almost completely determined by f′(X, i, R), and thus X ⊙ Y is almost completely determined by f′(X, i, R) and Y.

The interesting case is when i = D̃_{f}(f(X)), in which case, from Lemma 6.1, the adversary is unable to distinguish X ⊙ Y from β given Y and f′(X, i, R), and yet from Lemma 5.2(2), X ⊙ Y is almost completely determined by f′(X, i, R) and Y. It is from this case that we can extract a little bit of false entropy.

6.2. Construction and main theorem. We now describe the construction of a false-entropy generator g based on f′. Let

k_{n} ≥ 125n^{3}. (6.4)

Part of the construction is to independently and randomly choose k_{n} sets of inputs to f′ and concatenate the outputs. In particular, let X′ ∈_{U} {0, 1}^{k_{n}×n}, I′ ∈_{U} {0, 1}^{k_{n}×⌈log(n)⌉}, R′ ∈_{U} {0, 1}^{k_{n}×p_{n}}. Part of the construction is then f′^{k_{n}}(X′, I′, R′).

Let I ∈_{U} {0, …, n − 1}, let

p_{n} = Pr[I ≤ D̃_{f}(f(X))], (6.5)

and let

m_{n} = k_{n}p_{n} − 2k_{n}^{2/3}. (6.6)

We show later that it is sufficient to have an approximation of p_{n} to within an additive factor of 1/n for the entire construction to work. We need this to be able to claim that g described below is mildly nonuniform. For now we assume we have the exact value of p_{n}. Let Y′ ∈_{U} {0, 1}^{k_{n}×n}. The value of k_{n} is chosen to be large enough so that with high probability it is the case that I′_{j} ≤ D̃_{f}(f(X′_{j})) for at least m_{n} of the k_{n} possible values of j, and in this case, from Lemma 6.1, X′_{j} ⊙ Y′_{j} looks like a random bit to a time limited adversary given Y′_{j} and f′(X′_{j}, I′_{j}, R′_{j}).

The problem is that we don’t know for which set of m_{n} values of j the bit X′_{j} ⊙Y′_{j} looks random to a time limited adversary. Instead, the idea is to hash m_{n} bits out of all k_{n} such bits and release the hashed bits. The intuition is that these m_{n} hashed bits will look random to a time limited adversary, even though there are really at most (p_{n} − 1/n)k_{n} bits of randomness left in these k_{n} bits after seeing Y′ and f′^{k_{n}}(X′, I′, R′), and thus there are approximately m_{n} − (p_{n} − 1/n)k_{n} ≈ n^{2} bits of false entropy. Let

h′ : {0, 1}^{p′_{n}} × {0, 1}^{k_{n}} → {0, 1}^{m_{n}} (6.7)

be a universal hash function, let U ∈_{U} {0, 1}^{p′_{n}}, and define P-time function ensemble

g(p_{n}, X′, Y′, I′, R′, U) (6.8)

= ⟨h′_{U}(⟨X′_{1} ⊙ Y′_{1}, …, X′_{k_{n}} ⊙ Y′_{k_{n}}⟩), f′^{k_{n}}(X′, I′, R′), U, Y′⟩.

Theorem 6.2. Let f be a one-way function and g be as described above in (6.1)– (6.8). Then g is a mildly nonuniform false-entropy generator with false entropy 10n^{2}. The reduction is weak-preserving.

Proof. Let Z ∈_{U} {0, 1}^{m_{n}}, and let

D = ⟨h′_{U}(⟨X′_{1} ⊙ Y′_{1}, …, X′_{k_{n}} ⊙ Y′_{k_{n}}⟩), f′^{k_{n}}(X′, I′, R′), U, Y′⟩,
E = ⟨Z, f′^{k_{n}}(X′, I′, R′), U, Y′⟩.

Note that D is the distribution of the output of g, and E is the same except that the m_{n} output bits of h′ have been replaced by random bits. Lemma 6.4 shows that H(E) ≥ H(D) + 10n^{2}. Corollary 6.6 shows that if f is a one-way function, then we have that D and E are computationally indistinguishable, where the overall reduction is weak-preserving.

What remain to prove Theorem 6.2 are the proofs of Lemmas 6.4 and 6.5 of the next subsection. (Corollary 6.6 follows immediately from Lemmas 6.5 and 6.1.) Before we turn to this, we state the main result of this paper based on Theorem 6.2.

Theorem 6.3. There are one-way functions iff there are pseudorandom generators.

Proof. That pseudorandom generators imply one-way functions follows from [Levin87]. The converse now follows from Theorem 6.2 and the results are summarized in subsection 4.9.

6.3. The main lemmas.

Lemma 6.4. H(E) ≥ H(D) + 10n^{2}.

Proof. The entropy of D and E excluding the first m_{n} bits is exactly the same. The additional entropy in the first m_{n} bits of E is equal to m_{n}. An upper bound on the additional entropy in the first m_{n} bits of D is the additional entropy in ⟨X′_{1} ⊙ Y′_{1}, …, X′_{k_{n}} ⊙ Y′_{k_{n}}⟩. For each j ∈ {1, …, k_{n}} where I′_{j} < D̃_{f}(f(X′_{j})), the amount of entropy added by X′_{j} ⊙ Y′_{j} is at most 1. On the other hand, under the condition that I′_{j} ≥ D̃_{f}(f(X′_{j})), X′_{j} ⊙ Y′_{j} is determined by ⟨f′(X′_{j}, I′_{j}, R′_{j}), Y′_{j}⟩ with probability at least 1 − 1/2n, and thus the additional entropy under this condition is at most 1/2n. Since I′_{j} < D̃_{f}(f(X′_{j})) with probability p_{n} − 1/n, it follows that the additional entropy added by X′_{j} ⊙ Y′_{j} is at most p_{n} − 1/2n. Therefore, the additional entropy in the first m_{n} bits of D is at most k_{n}(p_{n} − 1/2n) = m_{n} + 2k_{n}^{2/3} − k_{n}/2n < m_{n} − 10n^{2} by choice of k_{n}.

Lemma 6.5. Let A be an adversary with distinguishing probability

δ_{n} = Pr[A(D) = 1] − Pr[A(E) = 1]

for D and E. (We assume without loss of generality that Pr[A(D) = 1] > Pr[A(E) = 1].) Let W = ⟨X̃, Ĩ⟩ ∈_{U} T , R ∈_{U} {0, 1}^{p(n)}, Y ∈_{U} {0, 1}^{n}, and β ∈_{U} {0, 1}. There is an oracle TM M such that M^{(A)} distinguishes between

⟨f′(W, R), X̃ ⊙ Y, Y ⟩ and ⟨f′(W, R), β, Y ⟩

with probability at least δ_{n}/(16k_{n}). The running time of M^{(A)} is polynomial in the running time of A.

The proof of Lemma 6.5 is the most technically involved in this paper. Before proving this lemma, we give the main corollary to this lemma, and then we give some motivation for the proof of the lemma.

Corollary 6.6. Let f be a one-way function. Then D and E are computationally indistinguishable. The reduction is weak-preserving.

Proof. For the proof, combine Lemma 6.1 with Lemma 6.5.

We now give some intuition to the proof of Lemma 6.5. The oracle TM M^{(A)} will use a nonstraightforward hybrid of distributions argument to be able to distinguish the two distributions in the statement of the lemma. To give some intuition about this nonstraightforward hybrid, we first describe a related straightforward hybrid argument that we do not know how to implement efficiently.

Consider the following distribution. For j ∈ {1, …, k_{n}}, let C_{j} = 1 with probability p_{n} and C_{j} = 0 with probability 1 − p_{n}. For all j, if C_{j} = 1 then let ⟨X̃′_{j}, Ĩ′_{j}⟩ ∈_{U} T , and if C_{j} = 0 then let ⟨X̃′_{j}, Ĩ′_{j}⟩ ∈_{U} \overline{T} . Let R′, Y′, and U be as defined previously. If these random variables are used to define a distribution using the same construction as used to define D, with ⟨X̃′_{j}, Ĩ′_{j}⟩ replacing ⟨X′_{j}, I′_{j}⟩, then the distribution is D, except that it is described in a slightly different way. Now, suppose this distribution is altered as follows: if C_{j} = 1, then change the jth input bit of h_{U} from X̃′_{j} ⊙ Y′_{j} to B_{j} ∈_{U} {0, 1}. Call this distribution D′.

From Lemma 6.1 intuitively it should be the case that a time limited adversary should not be able to distinguish D from D′. On the other hand, it is not hard to see using Lemma 4.8 that the statistical distance between D′ and E is exponentially small in n. Thus, if adversary A can distinguish between D and E, we should be able to use this to distinguish ⟨f′(W, R), X̃ ⊙ Y, Y ⟩ and ⟨f′(W, R), β, Y ⟩ as in the statement of Lemma 6.5.

The question is whether we can really prove that D′ is computationally indistinguishable from D. Toward resolving this question, consider the following family of hybrid distributions. For all j ∈ {0, …, k_{n}}, let F^{(j)} be the hybrid distribution between D and E, which is the same as D′ up to position j and the same as D thereafter; i.e., it is the same as D except that for all i ≤ j, if C_{i} = 1 then change the ith input bit of h_{U} from X̃′_{i} ⊙ Y′_{i} to B_{i} ∈_{U} {0, 1}. Then F^{(0)} = D and F^{(k_{n})} ≈ E. Let J ∈_{U} {1, …, k_{n}}. Then E_{J}[A(F^{(J−1)}) − A(F^{(J)})] = δ_{n}/k_{n}.

An inefficient oracle TM could work as follows on input ⟨f′(w, r), b, y⟩: the first phase chooses j ∈_{U} {1, …, k_{n}} and chooses a sample from F^{(j)}. If c_{j} = 0, then the oracle TM produces a random bit and stops. In the more interesting case, where c_{j} = 1, it replaces the inputs corresponding to the jth position in the sample according to f′(w, r) and y, and the jth input bit of h_{u} is set to b ∈_{U} {0, 1}. Then the second phase runs the adversary A on this input and outputs the bit produced by A. The distinguishing probability for this oracle TM is δ_{n}/k_{n}. The problem is that this is not an efficient oracle TM, because it may not be possible to efficiently uniformly sample from T and \overline{T} as required. However, it is possible to sample uniformly from {0, 1}^{n} × {0, …, n − 1}: a p_{n} fraction of the samples will be randomly distributed in T and a 1 − p_{n} fraction of the samples will be randomly distributed in \overline{T} . This simple idea is used to construct the efficient adversary described below.

The efficient adversary M^{(A)} described in detail in the proof of Lemma 6.5 proceeds in two phases similar to the inefficient oracle TM described above. The first phase of M^{(A)} consists of k_{n} stages, where stage j produces a coupled pair of distributions, D^{(j)} and E^{(j)}, both of which are polynomially samplable. Each stage consists of using adversary A and sampling from the distributions produced in the previous stage to produce the pair of output distributions for the current stage. Initially, D^{(0)} = D and E^{(0)} = E, and it will turn out that D^{(k_{n})} ≈ E^{(k_{n})}.

The first j − 1 positions in both D^{(j)} and E^{(j)} are already fixed in essentially the same way in D^{(j−1)} and E^{(j−1)}, and these positions will be fixed the same way in D^{(j)} and E^{(j)}. To fill in position j in D^{(j)} and E^{(j)}, many samples of ⟨x_{j}, i_{j}⟩ are drawn uniformly from {0, 1}^{n} ×{0, …, n − 1}, and then with high probability many of them will be in T and many will be in \overline{T} . We cannot directly tell for each sample whether it is in T or \overline{T} . Thus, we must use another criterion to decide which of the samples to keep to fill in position j. The criterion employed is to use the sample for which the distinguishing probability of A between D^{(j)} and E^{(j)} is highest when the jth position is fixed according to the sample.

Let δ^{(j)} = Pr[A(D^{(j)}) = 1] − Pr[A(E^{(j)}) = 1]. Because δ^{(0)} = δ_{n} and δ^{(k_{n})} ≈ 0, it follows that

E_{j∈_{U} {1,...,k_{n}}}[δ^{(j−1)} − δ^{(j)}] ≥ δ_{n}/k_{n}.

It is because of this discrepancy between the value of δ^{(j)} and δ^{(j−1)} that f′ can be inverted in the second phase.

Intuitively, stage j of the first phase works as follows. A bit c_{j} is chosen randomly to be one with probability p_{n} and to be zero with probability 1 − p_{n}. In the distribution D^{(j)}, the jth input ⟨x′_{j}, i′_{j}, r′_{j}⟩ to f′^{k_{n}} is chosen randomly, y′_{j} is chosen randomly, u is chosen randomly, and then the jth input bit of h′_{u} is set to a random bit b_{j} if c_{j} = 1 and to the correct inner product bit if c_{j} = 0. In the distribution E^{(j)}, the jth input of f′^{k_{n}} is set the same way it is set in D^{(j)}, and thus the two distributions D^{(j)} and E^{(j)} are correlated. The choice of the jth inputs is done several times (c_{j} is chosen only once at the beginning, i.e., it is not rechosen for each of the times) and each time the distinguishing probability of A for D^{(j)} and the corresponding E^{(j)} is approximated, and the choice that maximizes the difference between these accepting probabilities determines how D^{(j)} and E^{(j)} are finally set.

The second phase of M^{(A)} chooses j ∈_{U} {1, …, k_{n}} and then uses the pair of distributions D^{(j)} and E^{(j)} produced in the first stage. The idea is to choose a random sample from both D^{(j)} and E^{(j)}, modify portions of the D^{(j)} part according to the input to M^{(A)}, run A on both the modified D^{(j)} sample and the E^{(j)} sample, and, based on the outputs, produce a one bit output. The intuition is that the distinguishing probability will be δ^{(j)}, which on average over all j is at least δ_{n}/k_{n}.

We now turn to the formal proof of Lemma 6.5.

Proof of Lemma 6.5. The oracle TM M^{(A)} works as follows on input ⟨f′(w, r), b, y⟩. Phase 1. Define D^{(0)} = D and E^{(0)} = E. Let B ∈_{U} {0, 1}^{k_{n}}. Let ρ = δ_{n}/(16k_{n})

and τ = 64n^{2}/ρ. Stage j = 1, …, k_{n} works as follows: randomly choose c_{j} ∈ {0, 1} so that c_{j} = 1 with probability p_{n}. Choose x̂_{1}, …, x̂_{τ} ∈_{U} {0, 1}^{n} and î_{1}, …, î_{τ} ∈_{U} {0, …, n − 1}. For each m ∈ {1, …, τ}, define w_{m} = ⟨x̂_{m}, î_{m}⟩ and let D_{c_{j}}^{(j−1)}(w_{m}) be the same as D^{(j−1)} except that ⟨X′_{j}, I′_{j}⟩ is fixed to w_{m} and the jth input bit of h′ is set to

\{ \begin{matrix}x̂_{m} ⊙ Y′_{j} & if c_{j} = 0, \\ B_{j} & if c_{j} = 1. \end{matrix}

Similarly, define E^{(j−1)}(w_{m}) to be the same as E^{(j−1)} except that ⟨X′_{j}, I′_{j}⟩ is fixed to w_{m}. Let

δ_{c_{j}}^{(j−1)}(w_{m}) = Pr[A(D_{c_{j}}^{(j−1)}(w_{m})) = 1] − Pr[A(E^{(j−1)}(w_{m})) = 1].

Using A and sampling O(n/ρ^{2}) times from D_{c_{j}}^{(j−1)}(w_{m}) and E^{(j−1)}(w_{m}), produce an estimate Δ_{c_{j}}^{(j−1)}(w_{m}) so that

Pr[|Δ_{c_{j}}^{(j−1)}(w_{m}) − δ_{c_{j}}^{(j−1)}(w_{m})| > ρ] ≤ 2^{−n}.

Let m_{0} ∈ {1, …, τ} be the index for which Δ_{c_{j}}^{(j−1)}(w_{m_{0}}) is maximized. Set ⟨x′_{j}, i′_{j}⟩ = w_{m_{0}}, D^{(j)} = D_{c_{j}}^{(j−1)}(w_{m_{0}}), E^{(j)} = E^{(j−1)}(w_{m_{0}}) and go to the next stage.

Phase 2. Pick j ∈_{U} {0, …, k_{n} − 1}. Let D^{(j)}(w, r, b, y) be the distribution D^{(j)} except that f′(X′_{j+1}, I′_{j+1}, R′_{j+1}) is set to f′(w, r) and the j + 1^{r}st input bit of h′ is set to b and Y′_{j+1} is set to y. Let E^{(j)}(w, r, y) be the same as E^{(j)} except that f′(X′_{j+1}, I′_{j+1}, R′_{j+1}) is set to f′(w, r) and Y′_{j+1} is set to y. Let β ∈_{U} {0, 1}, let D be a sample of D^{(j)}(w, r, b, y), and let E be a sample of E^{(j)}(w, r, y). If A(D) = A(E), then output β else output A(D).

We now prove that the oracle adversary M^{(A)} as just described distinguishes as claimed in the lemma. Let w = ⟨x, i⟩, d^{(j)}(w, r, b, y) = E[A(D^{(j)}(w, r, b, y))] and e^{(j)}(w, r, y) = E[A(E^{(j)}(w, r, y))]. Then

Pr[M^{(A)}(f′(w, r), b, y) = 1] = 1/2 + (d^{(j)}(w, r, b, y) − e^{(j)}(w, r, y))/2.

Also, it follows directly from the definitions that

E[d^{(j)}(w, R, x ⊙ Y, Y) − e^{(j)}(w, R, Y)] = δ_{0}^{(j)}(w)

and

E[d^{(j)}(w, R, β, Y) − e^{(j)}(w, R, Y)] = δ_{1}^{(j)}(w).

Let ϵ^{(j)} = E[δ_{0}^{(j)}(W) − δ_{1}^{(j)}(W)]. Thus, the distinguishing probability of M^{(A)} is

E[M^{(A)}(f′(W, R), X̃ ⊙ Y, Y)] − E[M^{(A)}(f′(W, R), β, Y)]
= E_{j}[δ_{0}^{(j)}(W) − δ_{1}^{(j)}(W)]/2 = E_{j}[ϵ^{(j)}]/2,

where j ∈_{U} {0, …, k_{n} − 1} in the last two expectations. To prove the lemma, it is sufficient to show that E_{j}[ϵ^{(j)}]/2 ≥ ρ or, equivalently,

E [ ∑_{j∈{0,...,k_{n}−1}} ϵ^{(j)}] ≥ 2ρk_{n} = δ_{n}/8. (6.9)

The expectation here is over the random choices of M^{(A)} in the first phase. Let δ^{(j)} = Pr[A(D^{(j)}) = 1] − Pr[A(E^{(j)}) = 1]. We prove (6.9) by showing the following below:

(a) E[δ^{(k_{n})}] ≤ 2^{−n}. The expectation is over the random choices of M^{(A)} in the first phase.

(b) E[δ^{(j)} − δ^{(j+1)}] ≤ ϵ^{(j)} + 4ρ. The expectation is over random choices in the j + 1^{r}st stage of Phase 1 conditional on any set of choices in the previous stages.

From (a) and (b), and because δ^{(0)} = δ_{n}, it follows that

δ_{n}/2 < δ_{n} − E[δ^{(k_{n})}]
= ∑_{j∈{0,...,k_{n}−1}} E[δ^{(j)} − δ^{(j+1)}]

≤ 4k_{n}ρ + E [ ∑_{j∈{0,...,k_{n}−1}} ϵ^{(j)}]

= δ_{n}/4 + E [ ∑_{j∈{0,...,k_{n}−1}} ϵ^{(j)}] ,

and this proves the bound in (6.9). Thus, it suffices to prove (a) and (b) above.

Proof of (a). Since Pr[c_{j} = 1] = p_{n}, applying Chernoff bounds (e.g., see [MR95]), we get that, with probability at least 1 − 2^{−n},

∑_{j∈{0,...,k_{n}−1}} c_{j} ≥ k_{n}p_{n} − k_{n}^{2/3} = m_{n} + k_{n}^{2/3}.

The entropy of the input to h′ conditional on the rest of the bits of D^{(k_{n})} is at least ∑_{j∈{0,...,k_{n}−1}} c_{j}. So, if this sum is at least m_{n} + k_{n}^{2/3}, applying Lemma 4.8, L_{1}(D^{(k_{n})}, E^{(k_{n})}) ≤ 2^{−n}. Thus, δ^{(k_{n})} = E[A(D^{(k_{n})})] − E[A(E^{(k_{n})})] ≤ 2^{−n}.

Proof of (b). Let W̄ ∈_{U} \overline{T} , and recall that W ∈_{U} T . Then, since the j + 1st input of h′ is always X′_{j+1} ⊙ Y′_{j+1} in D^{(j)},

δ^{(j)} = p_{n}E[δ_{0}^{(j)}(W)] + (1 − p_{n})E[δ_{0}^{(j)}(W̄)]
= p_{n}E[δ_{1}^{(j)}(W)] + p_{n}(E[δ_{0}^{(j)}(W)] − E[δ_{1}^{(j)}(W)]) + (1 − p_{n})(E[δ_{0}^{(j)}(W̄)])
= p_{n}E[δ_{1}^{(j)}(W)] + p_{n}ϵ^{(j)} + (1 − p_{n})(E[δ_{0}^{(j)}(W̄)])
< ϵ^{(j)} + p_{n}E[δ_{1}^{(j)}(W)] + (1 − p_{n})(E[δ_{0}^{(j)}(W̄)]).

We now show that E[δ^{(j+1)}] ≥ p_{n}E[δ_{1}^{(j)}(W)]+(1−p_{n})(E[δ_{0}^{(j)}(W̄)])−4ρ, and this concludes the proof. Let c ∈ {0, 1} and consider stage j in Phase 1. From our choice of τ and the fact that 1/n ≤ p_{n} ≤ 1 − 1/n, it follows that, with probability at least 1 − 2^{−n}, at least n/ρ of the w_{m}’s are in T , and at least n/ρ of the w_{m}’s are in \overline{T} . It then follows using Chernoff bounds that

Pr[ max_{1≤m≤τ}{δ_{c}^{(j)}(w_{m})} ≥ max{E[δ_{c}^{(j)}(W)], E[δ_{c}^{(j)}(W̄)]} − ρ]

is at least 1 − 2^{−n}. Also, with probability at least 1 − 2^{−n}, Δ_{c}^{(j)}(w_{m}) is within ρ of the corresponding δ_{c}^{(j)}(w_{m}), and thus (recalling how w_{m_{0}} is chosen above in stage j)

δ_{c}^{(j)}(w_{m_{0}}) ≥ Δ_{c}^{(j)}(w_{m_{0}}) − ρ
= max_{m∈{1,...,τ}}{Δ_{c}^{(j)}(w_{m})} − ρ
≥ max_{m∈{1,...,τ}}{δ_{c}^{(j)}(w_{m})} − 2ρ
≥ max{E[δ_{c}^{(j)}(W)], E[δ_{c}^{(j)}(W̄)]} − 3ρ

with probability at least 1 − 3 · 2^{−n}. Let δ_{c}^{(j+1)} be the value of δ^{(j+1)} conditional on c_{j+1} = c. From this we can conclude that

E[δ_{c}^{(j+1)}] ≥ max{E[δ_{c}^{(j)}(W)], E[δ_{c}^{(j)}(W̄)]} − 4ρ.

Since c_{j+1} = 1 with probability p_{n},

E[δ^{(j+1)}] = p_{n}E[δ_{1}^{(j+1)}] + (1 − p_{n})E[δ_{0}^{(j+1)}]
≥ p_{n}E[δ_{1}^{(j)}(W)] + (1 − p_{n})(E[δ_{0}^{(j)}(W̄)]) − 4ρ.

Before we continue let us just check that a good approximation of p_{n} is sufficient. Suppose that p_{n} ≤ p̃_{n} ≤ p_{n} + \frac{1}{n} and do the entire construction with p̃_{n} replacing p_{n}. Enlarge T to density p̃_{n} by making it contain some elements ⟨x, i⟩ with i = D̃_{f}(f(x)) + 1. Lemma 6.1 is easily seen to remain valid, and Lemma 6.4 just becomes more true in that the entropy of D decreases. This implies that it is sufficient to try O(n) different values of p_{n}.

7. A direct construction. We have shown how to construct a false-entropy generator from an arbitrary one-way function, a pseudoentropy generator from a false-entropy generator, and finally a pseudorandom generator from a pseudoentropy generator. The combinations of these constructions give a pseudorandom generator from an arbitrary one-way function as stated in Theorem 6.3. By literally composing the reductions given in the preceding parts of this paper, we construct a pseudorandom generator with inputs of length n^{34} from a one-way function with inputs of length n. This is obviously not a suitable reduction for practical applications. In this subsection, we use the concepts developed in the rest of this paper, but we provide a more direct and efficient construction. However, this construction still produces a pseudorandom generator with inputs of length n^{10}, which is clearly still not suitable for practical applications. (A sharper analysis can reduce this to n^{8}, which is the best we could find using the ideas developed in this paper.) The result could only be considered practical if the pseudorandom generator had inputs of length n^{2}, or perhaps even close to n. (However, in many special cases of one-way functions, the ideas from this paper are practical; see, e.g., [Luby96].)

The improvement in the direct construction given here comes from the observation that more than one of the reductions involves a product distribution, whereas only one product distribution is needed for the overall proof.

We start with a one-way function f : {0, 1}^{n} → {0, 1}^{ℓ_{n}}. We construct f′ as in (6.3), and let p_{n} be the probability that I ≤ D̃_{f}(f(X)) as in the previous section. Let X = ⟨X, I, R⟩ represent the input distribution to f′, and let c_{n} be the length of X and c′_{n} the length of f′(X). Let e_{n} = H(f′(X)). Let b(X , y) = x ⊙ y. Set k_{n} = 2000n^{6}.

Intuitively, we generate pseudorandom bits as follows: let X′ = X^{k_{n}} and Y′ = Y^{k_{n}}. We first compute f′^{k_{n}}(X′) and b^{k_{n}}(X′, Y′). Intuitively, we are entitled to recapture

k_{n}c_{n} − H⟨f′^{k_{n}}(X′), b^{k_{n}}(X′, Y′)⟩

bits from X′, because this is the conditional entropy left after we have computed f′^{k_{n}} and b^{k_{n}}. We are entitled to recapture k_{n}p_{n} bits from the b^{k_{n}}(X′, Y′) (since we get a hidden bit out of each copy whenever I ≤ D̃_{f}(f(X))). Finally, we should be able to extract e_{n}k_{n} bits from f′^{k_{n}}(X′), since e_{n} is the entropy of f′(X). Since b(n) is almost totally predictable for almost all inputs where I ≥ D̃_{f}(f(X)),

H⟨f′(X), b(X , Y)⟩ ≤ e_{n} + p_{n} − 1/n + 1/(2n).

(See the proof of Lemma 6.4.) Thus, if we add up all the output bits, we are entitled to k_{n}(c_{n}+1/(2n)), or k_{n}/(2n) more bits than the input to f′^{k_{n}}. However, our methods of extracting entropy are not perfect, so we need to sacrifice some bits at each stage; to use Corollary 4.10, we need to sacrifice 2nk_{n}^{2/3} at each stage, so we chose k_{n} to satisfy k_{n}/(2n) > 6nk_{n}^{2/3}.

Formally, let m_{n} = k_{n}(c_{n} − e_{n} − p_{n} + 1/(2n)) − 2nk_{n}^{2/3}, m′_{n} = k_{n}p_{n} − 2nk_{n}^{2/3}, and m′′_{n} = k_{n}e_{n} − 2nk_{n}^{2/3}. Let R_{1}, R_{2}, and R_{3} be indices of hash functions so that h_{R_{1}} maps k_{n}c_{n} bits to m_{n} bits, h_{R_{2}} maps k_{n} bits to m′_{n} bits, and h_{R_{3}} maps k_{n}c′_{n} bits to m′′_{n} bits. Our construction is as follows.

Construction 7.1.

g(X′, Y′, R_{1}, R_{2}, R_{3}) = ⟨h_{R_{1}}(X′), h_{R_{2}}(b^{k_{n}}(X′, Y′)), h_{R_{3}}(f′^{k_{n}}(X′)), Y′, R_{1}, R_{2}, R_{3}⟩.

Theorem 7.2. If f is a one-way function and g is as in Construction 7.1, then g is a mildly nonuniform pseudorandom generator. The reduction is weak-preserving.

Proof. It is easy to check that g outputs more bits than it inputs.

As noted above, the conditional entropy of X given f′(X) and b(X , Y) is at least c_{n} − e_{n} − p_{n} + (1/2n). Thus, from Corollary 4.10, we have that ⟨h_{R_{1}}(X′), R_{1}⟩ is statistically indistinguishable from random bits given ⟨f′^{k_{n}}(X′), b^{k_{n}}(X′, Y′), Y′⟩. Hence, g(X′, Y′, R_{1}, R_{2}, R_{3}) is statistically indistinguishable from

⟨Z_{1}, h_{R_{2}}(b^{k_{n}}(X′, Y′)), h_{R_{3}}(f′^{k_{n}}(X′)), Y′, R_{1}, R_{2}, R_{3}⟩,

where Z_{1} ∈_{U} {0, 1}^{m_{n}}. Now, from Lemmas 6.5 and 6.1, it follows that h_{R_{2}}(b^{k_{n}}(X′, Y′)) is computationally indistinguishable from random bits given ⟨f′^{k_{n}}(X′), R_{2}, Y′⟩. Thus, g(X′, Y′, R_{1}, R_{2}, R_{3}) is computationally indistinguishable from

⟨Z_{1}, Z_{2}, h_{R_{3}}(f′^{k_{n}}(X′)), Y′, R_{1}, R_{2}, R_{3}⟩,

where Z_{2} ∈_{U} {0, 1}^{m′_{n}}. Finally, from Corollary 4.10, ⟨h_{R_{3}}(f′^{k_{n}}(X′)), R_{3}⟩ is statistically indistinguishable from ⟨Z_{3}, R_{3}⟩, where Z_{3} ∈_{U} {0, 1}^{m′′_{n}}. Thus, the output of g is computationally indistinguishable from a truly random output of the same length.

If we use hash functions constructed as Toeplitz matrices, then O(m) bits are sufficient to construct a hash function on m bits and the inputs needed for the hash function is just a constant fraction of all inputs. Then the input length to g is O(nk_{n}) = O(n^{7}).

We still need to use Proposition 4.17 to get rid of the mild nonuniformity. From the arguments above, it is clear that an approximation of both e_{n} and p_{n} that is within 1/(8n) of their true values is sufficient. Since 0 ≤ e_{n} ≤ n, and 0 ≤ p_{n} < 1, there are at most O(n^{3}) cases of pairs to consider. This means that we get a total of O(n^{3}) generators, each needing an input of length O(n^{7}). Thus the total input size to the pseudorandom generator is O(n^{10}), as claimed.

8. Conclusions. A general problem is to characterize the conditions under which cryptographic applications are possible. By conditions we mean complexity theoretic conditions, e.g., P ≠ NP, the existence of one-way functions, etc. Examples of cryptographic applications are private key cryptography, identification/authentication, digital signatures, bit commitment, exchanging secrets, coin flipping over the telephone, etc.

For a variety of cryptographic applications it is known that a secure protocol can be constructed from a pseudorandom generator, e.g., the work of [GGM86], [LR88], [GMR89], [Naor88], [GMW91], shows that applications ranging from private key encryption to zero-knowledge proofs can be based on a pseudorandom generator. The results presented in this paper show that these same protocols can be based on any one-way function. The paper [NY89] gives a signature scheme that can be based on any one-way permutation, and [R90] substantially improves this by basing such a scheme on any one-way function.

Using the notion of a false-entropy generator, [G89] shows that the existence of pseudorandom generators is equivalent to the existence of a pair of P-samplable distributions which are computationally indistinguishable but statistically very different.

The paper [IL89] provides complementary results; a one-way function can be constructed from a secure protocol for any one of a variety of cryptographic applications, including private key encryption, identification/authentication, bit commitment, and coin flipping by telephone. The paper [OW93] shows that a one-way function can be constructed from any nontrivial zero-knowledge proof protocol. Thus, secure protocols for any of these applications are equivalent to the existence of one-way functions.

The results described in this paper and the previous three paragraphs show that the existence of a one-way function is central to modern complexity-based cryptography.

Some applications seem unlikely to be shown possible based on any one-way function; e.g., [IR89] gives strong evidence that exchanging secrets over a public channel is an application of this type.

A fundamental issue is that of efficiency, both in size and time; the general construction we give for a pseudorandom generator based on any one-way function increases the size of the input by a large polynomial amount and thus is only weakpreserving. This is not good news for practical applications; it would be nice to have a general poly-preserving or a linear-preserving reduction.

Acknowledgments. This research evolved over a long period of time and was greatly influenced by many people. We thank Amos Fiat, Moni Naor, Ronitt Rubinfeld, Manuel Blum, Steven Rudich, Noam Nisan, Lance Fortnow, Umesh Vazirani, Charlie Rackoff, Oded Goldreich, Hugo Krawczyk, and Silvio Micali for their insights and contributions to this work. We in particular thank Charlie, Umesh, and Manuel for their advice and enthusiasm, and Oded and Hugo for exposing the fourth author to their wealth of insights on this problem. Finally, Oded’s insightful comments on every aspect of earlier versions of this paper have improved the presentation tremendously.

REFERENCES

[ACGS88] W. Alexi, B. Chor, O. Goldreich, and C. P. Schnorr, RSA and Rabin functions: Certain parts are as hard as the whole, SIAM J. Comput., 17 (1988), pp. 194–209.

[BFNW96] L. Babai, L. Fortnow, N. Nisan, and A. Wigderson, BPP has subexponential time simulations unless EXPTIME has publishable proofs, Comput. Complexity, 3 (1993), pp. 307–318.

[BBR88] C. H. Bennett, G. Brassard, and J.-M. Robert, Privacy amplification by public discussion, SIAM J. Comput., 17 (1988), pp. 210–229.

[Blum84] M. Blum, Independent unbiased coin flips from a correlated biased source—a finite state Markov chain, Combinatoria, 6 (1986), pp. 97–108.

[BM82] M. Blum and S. Micali, How to generate cryptographically strong sequences of pseudorandom bits, SIAM J. Comput., 13 (1984), pp. 850–864.

[BH89] R. Boppana and R. Hirschfeld, Pseudo-random generators and complexity classes, in Advances in Comp. Research 5, S. Micali, ed., JAI Press, Greenwich, CT, 1989, pp. 1–26.

[Boyar89] J. Boyar, Inferring sequences produced by pseudo-random number generators, J. Assoc. Comput. Mach., 36 (1989), pp. 129–141.

[CW79] L. Carter and M. Wegman, Universal classes of hash functions, J. Comput. System Sci., 18 (1979), pp. 143–154.

[CG88] B. Chor and O. Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complex, SIAM J. Comput., 17 (1988), pp. 230–261.

[DH76] D. Diffie and M. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory, 22 (1976), pp. 644–654.

[G89] O. Goldreich, A note on computational indistinguishability, Inform. Process. Lett., 34 (1990), pp. 277–281.

[GGM86] O. Goldreich, S. Goldwasser, and S. Micali, How to construct random functions, J. Assoc. Comput. Mach., 33 (1986), pp. 792–807.

[GKL93] O. Goldreich, H. Krawczyk, and M. Luby, On the existence of pseudorandom generators, SIAM J. Comput., 22 (1993), pp. 1163–1175.

[GL89] O. Goldreich and L. A. Levin, A hard-core predicate for any one-way function, in Proc. 21st ACM Sympos. on Theory of Computing, ACM, New York, 1989, pp. 25–32.

[GMW91] O. Goldreich, S. Micali, and A. Wigderson, Proofs that yield nothing but their validity, or all languages in NP have zero-knowledge proofs, J. Assoc. Comput. Mach., 38 (1991), pp. 691–729.

[GM84] S. Goldwasser and S. Micali, Probabilistic encryption, J. Comput. System Sci., 28 (1984), pp. 270–299.

[GMR89] S. Goldwasser, S. Micali, and C. Rackoff, The knowledge complexity of interactive proof systems, SIAM J. Comput., 18 (1989), pp. 186–208.

[GMT82] S. Goldwasser, S. Micali, and P. Tong, Why and how to establish a private code on a public network, in Proc. 23rd IEEE Sympos. on Found. of Comput. Sci., IEEE, New York, 1982, pp. 134–144.

[H90] J. Håstad, Pseudo-random generators under uniform assumptions, in Proc. 22nd ACM Sympos. on Theory of Computing, ACM, New York, 1990, pp. 395–404.

[HL92] A. Herzberg and M. Luby, Public randomness in cryptography, in Advances in Cryptology, Proc. 12th Annual Cryptology Conf. (CRYPTO ’92), Santa Barbara, CA, 1992, Lecture Notes in Comput. Sci. 740, Springer-Verlag, Berlin, 1993, pp. 421– 432.

[IL89] R. Impagliazzo and M. Luby, One-way functions are essential for information based cryptography, in Proc. 30th IEEE Sympos. on Found. of Comput. Sci., IEEE, New York, 1989, pp. 230–235.

[ILL89] R. Impagliazzo, L. Levin, and M. Luby, Pseudo-random number generation from one-way functions, in Proc. 21st ACM Sympos. on Theory of Computing, ACM, New York, 1989, pp. 12–24.

[IN96] R. Impagliazzo and M. Naor, Efficient cryptographic schemes provably as secure as subset sum, J. Cryptology, 9 (1996), pp. 192–216.

[IR89] R. Impagliazzo and S. Rudich, Limits on the provable consequences of one-way functions, in 21st ACM Sympos. on Theory of Computing, ACM, New York, 1989, pp. 44–56.

[IZ89] R. Impagliazzo and D. Zuckerman, How to recycle random bits, in Proc. 30th IEEE Sympos. on Found. of Comput. Sci., IEEE, New York, 1989, pp. 248–253.

[Knuth97] D. E. Knuth, The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley, Bonn, 1998.

[K65] A. N. Kolmogorov, Three approaches to the concept of the amount of information, Problems Inform. Transmission, 1 (1965), pp. 1–7.

[K92] H. Krawczyk, How to predict congruential generators, J. Algorithms, 13 (1992), pp. 527–545.

[Levin87] L. A. Levin, One-way function and pseudorandom generators, Combinatorica, 7 (1987), pp. 357–363.

[Levin93] L. A. Levin, Randomness and non-determinism, J. Symbolic Logic, 58 (1993), pp.1102– 1103.

[Luby96] M. Luby, Pseudorandomness and Cryptographic Applications, Princeton Computer Science Notes, Princeton University Press, Princeton, NJ, 1996.

[LR88] M. Luby and C. Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM J. Comput., 17 (1988), pp. 373–386.

[McEl78] R. J. McEliece, A Public Key Cryptosystem Based on Algebraic Coding Theory, DSN Progress report, Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA, 1978.

[McIn87] J. McInnes, Cryptography Using Weak Sources of Randomness, Tech. report 194/87, University of Toronto, 1987.

[MR95] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, 1995.

[Naor88] M. Naor, Bit commitment using pseudorandom generators, J. Cryptology, 4 (1991), pp. 151–158.

[NY89] M. Naor and M. Yung, Universal one-way hash functions and their applications, in Proc. 21st ACM Sympos. on Theory of Computing, ACM, New York, 1989, pp. 33–43.

[OW93] R. Ostrovsky and A. Wigderson, One-way functions are essential for non-trivial zero-knowledge, in Proc. 2nd Israel Sympos. on the Theory of Computing and Systems, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 3–17.

[Renyi70] A. Renyi, Probability Theory, North–Holland, Amsterdam, 1970.

[RSA78] R. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM, 21 (1978), pp. 120–126.

[R90] J. Rompel, One-way functions are necessary and sufficient for secure signatures, in Proc. 22nd ACM Sympos. on Theory of Computing, ACM, New York, 1990, pp. 387–394.

[SV86] M. Santha and U. Vazirani, Generating quasi-random sequences from slightly-random sources, J. Comput. System Sci., 33 (1986), pp. 75–87.

[S48] C. Shannon, A mathematical theory of communication, Bell System Tech. J., 27 (1948), pp. 379–423; 623–656.

[S83] M. Sipser, A complexity theoretic approach to randomness, in Proc. 15th ACM Sympos. on Theory of Computing, ACM New York, 1983, pp. 330–335.

[V87] U. Vazirani, Towards a strong communication complexity theory or generating quasirandom sequences from two communicating slightly-random sources, Combinatorica, 7 (1987), pp. 375–392.

[VV85] U. Vazirani and V. Vazirani, Random polynomial time is equal to slightly-random polynomial time, in Proc. 26th IEEE Sympos. on Found. of Comput. Sci., IEEE, New York, 1985, pp. 417–428.

[Yao82] A. C. Yao, Theory and applications of trapdoor functions, in Proc. 23rd IEEE Sympos. on Found. of Comput. Sci., IEEE, New York, 1982, pp. 80–91.