One Way Functions and Pseudorandom Generators^{∗}^{†}

Leonid A. Levin^{‡}

Received 1 September 1985 Revised 31 August 1986

Abstract

Pseudorandom generators transform in polynomial time a short random “seed” into a long “pseudorandom” string. This string cannot be random in the classical sense of [Kolmogorov 65], but testing that requires an unrealistic amount of time (say, exhaustive search for the seed). Such pseudorandom generators were first discovered in [Blum, Micali 82] assuming that the function (a^{x} mod b) is one-way, i.e., easy to compute, but hard to invert on a noticeable fraction of instances. In [Yao 82] this assumption was generalized to the existence of any one-way permutation. The permutation requirement is sufficient but still very strong. It is unlikely to be proven necessary, unless something crucial, like P=NP, is discovered. Below, among other observations, a weaker assumption about one-way functions is proposed, which is not only sufficient, but also necessary for the existence of pseudorandom generators.

Notations

Let S be the set of finite strings and Ω the set of infinite strings in the alphabet {±1}; let ∥x∥ be the length of x and x ∘ y be the concatenation of x and y. We identify S (in lexicographical order) with I N = {0, 1, ...} and denote the empty string by ∅.

Let us fix an arbitrary function r : I N → I N with monotone unbounded log_{n} r(n) < n and, for every ε > 0, agree to consider infeasible the functions > r(n^{ε}) and negligible the ones < 1/r(n^{ε}) (see 5.6).

Let U(x) be the Universal Algorithm which divides x into the “program prefix” and the “input” after the first occurrence of a distinguished string. Arbitrary functions below can often be replaced, without loss of generality, by the following modifications of U. Let U(x) = U(x), if ∥U(x)∥ = ∥x∥; otherwise U diverges. Let u(x) = U(x), if U(x) halts in time ∥x∥^{2} (see 5.1); otherwise u(x) = x. Let \overline{u}(x) = u(x), if u(x) preserves the “program prefix” and \overline{u}(x) = x otherwise.

1 One-way functions

Let f, h : S → S be length preserving. A probabilistic algorithm A inverts f on h for an instance x and random ω ∈ Ω if for y = h(x) either y ∉ f(S) and A(ω, y) diverges or f(A(ω, y)) = y. A polynomial time computable f is one-way on h (denoted OW(f/h)) if any A inverting it on h converges in an infeasible time on at least a polynomial fraction of instances of each length (or “on average”: see 5.3). So, h just modifies the frequencies of instances.

Let us consider several conjectures about the existence of one-way functions.

(A) ∃f, h OW(f/h). This is equivalent to OW(\overline{u}/U) and, when infeasible means non-polynomial, to P≠NP. A generic example is f(G, H) = (G, 1...1) if H is a Hamiltonian cycle of a graph G; otherwise f(G, H) = 1...1. And h produces those graphs whose Hamiltonian cycles are the hardest to find (see 5.2).

(B) ∃f, h OW(f/h) and h also runs in polynomial time. This is equivalent to OW(\overline{u}/u). If it is false, the P≠NP question remains open but loses its practical value. The inverse f^{−1}(h(x)) always exists, if h(x) has a form f(h(x)). An interesting variation is, when h is f or f^{k}, k(∥x∥) > 0. This implies (B) even for noncomputable k(n) ≤ n^{O(1)}, since h(k ∘x) = k ∘f^{k}(x) can be used. Using f′(x_{1} ∘...∘x_{i}) = f(x_{1})∘...∘f(x_{i}), the above variation of (B) can be shown equivalent to B_{k}, which postulates that the inverting time for \overline{u} on \overline{u}^{k} is infeasible on a constant fraction of instances. The criterion in section 4 for the existence of pseudorandom generators is B_{∗}, i.e., B_{k} for all k(n) < n log r(n) (see 5.6).

∗Supported by NSF grants #DCR-8304498, DCR-8607492

†Combinatorica 7(4):357–363, 1987. A version of this paper appeared in the Proceedings of the 17-th Symposium on Theory of Computing, 1985.

‡Boston University, MIT

(C) ∃f, h OW(f/h) and h is a permutation. (C) is much stronger than (B). It is equivalent to OW(\overline{u}/i) where i(x) = x, since h preserves the uniform distribution of instances. (C) means that NP problems (like Tiling: see [Levin 86]) are hard even on generic instances. If ∥f(x)∥ = ∥x∥ is not required, then (C) is equivalent to a modification of (B) where the inverting algorithm has access not only to the instance h(x), but to the x itself, explaining the origin of the instance. Just replace f, h by f_{h}, i, where f_{h}(x, z) is x if h(x) = f(z) and 1...1 otherwise. The possibility that (C) is false may explain a common experience (so strongly emphasized by D. Hilbert) that most natural mathematical problems are solved within a few centuries, which is a “very polynomial” time.

(D) ∃f OW(f/f^{k}) and f is a permutation. These conjectures, equivalent for all k, are proven in [Yao 82] sufficient for the existence of pseudorandom generators.

2 Pseudorandomness

A test is a probabilistic algorithm t : Ω^{2} × I N → [−1, 1]. Positive t(ω, α, n) indicates a “bet” that the tested function α is random rather than generated as α(i) = G_{s}(i) by an algorithm G from an n-bit random seed s. And ω is the source of the test’s own coin flips. Modifying slightly [Yao 82], we restrict t’s running time by |t(ω, α, n)|^{−O(1)} rather than by n^{O(1)}. So, t can run very slow, at the expense of diminishing value of its output. Let t_{G}(n) be the expected value of t(ω, G_{s}, n) − t(ω, α, n) for uniformly distributed α, ω ∈ Ω, s ∈ {±1}^{n}.

Now, G is called a pseudorandom generator if (1) G_{s}(i) is computable within time polynomial in ∥s∥i, and (2) G_{s} is “indistinguishable” from random strings, i.e., |t_{G}| is negligible, for any test t. The much more powerful parallel generators run in time polynomial in ∥s∥ log i and withstand tests which can query entries of α in any order rather than sequentially scan them. Such a goal was mentioned in [Blum, Blum, Shub 83] and reduced in [Goldreich, Goldwasser, Micali 84] to constructing sequential generators.

A predicting test first chooses a focal string x = x(ω). Then it queries α(y) for several y ≠ x, generates a prediction p ∈ [−1, 1] for α(x) and outputs α(x)p. Obviously, the test’s expectation, i.e., the covariation of p with α(x) is 0, when α is truly random. The following proposition is a modification of a theorem in [Yao, 82] and its generalization in [Goldreich, Goldwasser, Micali 84].

Proposition 1 A polynomial time algorithm G is pseudorandom, unless it fails some predicting test.

Proof. Let t′′ be a test with a non-negligible t′′_{G} which can be estimated statistically (see 5.5). We truncate t′′ to output 0 when |t′′| < |t′′_{G}/2| and normalize it to t = t′′_{G}(n)^{O(1)}t′′ so that t can be computed in time |t|^{−1/2}. Let ω_{1} consist of even and ω_{2} of odd digits of ω. Let test t.j(ω, α, n) act like t(ω_{1}, α, n), except that it substitutes coin flips c_{i}(ω_{2}) for the answers α(x_{i}) to the first j different queries x_{i}, i ≤ j (t.j = 0 if < j queries are made). Obviously, h_{j} = t.j_{G} < 1/j^{2} and h_{0} = h. The predicting test t′ chooses j(ω_{2}) at random with probability l_{j} = O(1)/j∥j∥^{2}. Then t′ runs t.j, sets x(ω) := x_{j}, and produces p := t.j(ω, α, n)c_{j}(ω_{2})/l_{j}. Let e_{j} be the expected value of t.j · c_{j} · G_{s}(x_{j}). Let \overline{h}_{j} be a modification of h_{j} in which −α(x_{j+1}) is used by t.j instead of α(x_{j+1}). Obviously, h_{j} = (h_{j−1} + \overline{h}_{j−1})/2 and t′_{G} = ∑_{j} e_{j}. Considering cases c_{j} = ±G(x_{j}), one can see that e_{j} = (h_{j−1} − \overline{h}_{j−1})/2 = h_{j−1} − h_{j} and t′_{G} = t_{G}. (See also 5.4).

3 Multiplicative Isolation Lemma

One of the important ideas of [Yao 82] is that the methods of [Wyner 75] can be applied for computational as well as for purely probabilistic unpredictability. The following is a simple implementation of this idea adjusted to the needs of section 4. Weaker versions (with polynomials instead of (p_{l})^{n}) of the Corollary below were given in [Goldwasser 84], [Rackoff 85]. The question, whether an exponential bound can be achieved, was raised by S. Micali.

Let f : S → S; A : S → [−1, 1]; b : S → [−1, 1]; p : I N → [0, 1]; ε : I N → [0, 1]; l : I N → I N be all computable in time T (∥x∥) > ∥x∥^{2} and h = 2| log ε|/ε. Let the covariation cov_{x}(A(x), b(x)) denote the average of A(x)b(x) over all x of a given length. Then b is called (p, T)-isolated from f if no probabilistic algorithm A(f(x)) running in time ≤ T (∥x∥) has cov_{x}(A(f(x)), b(x)) ≥ p(∥x∥).

The range of A can be always narrowed to ±1 without affecting the covariation. We just replace the real output with the ±1 result of a biased coin flip with the same expected value.

Lemma 1 Let f(x ∘ y) = f_{0}(x) ∘ f_{1}(y) and b(x ∘ y) = b_{0}(x)b_{1}(y), for ∥x∥ = l(∥x ∘ y∥). Then b is (p, T)- isolated from f, unless for some p_{0}, p_{1}, T′ and both θ ∈ {0, 1}, T′ < T h^{2}p_{θ}, b_{θ} is not (p_{θ}, T′)-isolated from f_{θ} and p_{0}p_{1} > p − ε, for corresponding lengths.

Proof. Let an algorithm A(f(z)) predict b(z), in time T with covariation p. We employ three algorithms Q_{0}(n), L_{0}(X), R_{0}(Y) dependent on f, b, p, ε, and A. Let q_{0}(X) = cov_{y}(b_{1}(y), A(X ∘ f_{1}(y))). Let q be “near maximum” of q_{0}(f_{0}(x)) i.e. max{0, q_{0}(f_{0}(x)) − q} averages to ε/4 and q^{±} be q(1 ± ε/4p). First Q_{0} finds an x with q_{0}(f_{0}(x)) ≥ q^{−}, with o(ε) probability of error.

Q_{0}(n) starts with q^{−} := 0. For i = h, h − 1, ... it generates a string x_{i} of length l(n) at random and computes a lower statistical estimate q_{i} of q_{0}(f_{0}(x_{i})) with accuracy i/h and probability of error o(ε/h) (see 5.5). If q_{i} > q^{−}, Q sets q^{−} := q_{i}, x := x_{i},. It stops when q^{−}ε/8p > i/h.

Now, R_{0} reads the input Y = f_{1}(y) and outputs A(f_{0}(x) ∘ Y). Obviously, the covariation p_{0} ≥ q^{−} − o(ε) will be achieved. And, L_{0}(X) = q_{0}(X)/q^{+} (or sign(q_{0}(X)), if |q_{0}(X)| > q^{+}) achieves the needed covariation p_{1} = (p − ε/4)/q^{+}. A rough statistical average \overline{q}_{0} over hp_{1}^{2}/ε random samples is used instead of q_{0}. The sample size does not affect its covariation with b_{0}, but assures \overline{q}_{0}(X) ≤ q^{+} with reliability 1−o(ε), whenever q_{0}(X) ≤ q.

The above algorithms run in time T h^{2}p_{1}. If p_{0} < p_{1}, we use Q_{1}, L_{1}, R_{1}, defined correspondingly, instead of Q_{0}, L_{0}, R_{0}. If the problem remains, we use L_{0}, L_{1} with q = \sqrt{p}.

Corollary 1 Let x = x_{0} ∘ ... ∘ x_{l(∥x∥)}; ∥x_{i}∥ = ∥f(x_{i})∥ = ∥x_{1}∥ except for ∥x_{0}∥ ≤ ∥x_{1}∥; T_{l}(k) = T (⌊k/l(k)⌋); p_{l}(k) = p(⌊k/l(k)⌋); f_{l}(x) = f(x_{0}) ∘ ... ∘ f(x_{l(∥x∥)}) and b_{l}(x) = ∏ b(x_{i}). Then, b_{l} is ((p_{l})^{n}, h^{2}T_{l})-isolated from f_{l} for any n(∥x∥) < l(∥x∥), if b is (p, T)-isolated from f. Here h = n| log p_{l}|/p_{l}^{n}(1 − p_{l})^{O(1)}. Thus, isolation is about (T^{−1/3}, T^{1/3}) when l is log T_{l}/3| log p_{l}|.

We just use L to predict b_{k} from f_{k} with covariation about (p_{k})^{k} for as small k as possible. Then we use R to predict b from f. This works, since otherwise the above k could be decreased.

4 The criterion

Recall the assumption B_{∗} that inverting \overline{u} takes an infeasible time on a constant fraction of outputs of \overline{u}^{k}(x) for every 0 < k < ∥x∥ log r(∥x∥).

Theorem 1 B_{∗} is necessary and sufficient for the existence of pseudorandom generators.

Necessity. Let G be a pseudorandom generator and let f(s∘x) = G_{s}(1)∘...∘G_{s}(2∥s∥), for ∥x∥ = ∥s∥. If B_{∗} fails, some probabilistic algorithm A inverts f on f^{k}(z) for some k(∥z∥) in time T (ω, f^{k}(z)), and the average of 1/T k over ω, z, ∥z∥ = n is not negligible. Let h_{j} be the average over α, ω of t.j(ω, α, n) = 1/T (ω, f^{j}(z)) for z = α(1) ∘ ... ∘ α(2n). Let the test t choose j(n, ω) at random with probability l_{j} = O(1)/j∥j∥^{2} and then run t.j. Then t_{G} = −h_{0} + ∑_{j} h_{j}(l_{j} − l_{j+1}). But f has an inverse on ≤ 2^{−n} of z’s. So, h_{0} ≤ 2^{−n} is negligible while h_{k(∥z∥)} and, thus, t_{G} are not.

Construction. We combine the techniques from [Blum Micali 82], [Yao 82] and [Goldreich Goldwasser Micali 84]. Let C(x) be an error correcting code (see [Justesen 72]) from which x can be restored in polynomial time even if any 5% of digits of C(x) are altered. Let b(s) be the i-th digit of C(s′) where s = s′ ∘ i ∈ S; ∥i∥ = ⌈log ∥C(s)∥⌉ and f(s) = \overline{u}(s′) ∘ i. Any feasible time probabilistic algorithm A guessing b(f^{k}(s)) as, A(ω, f^{k+1}(s)) must be wrong for at least 5% of i-s on a constant fraction of s′, ω. Otherwise \overline{u} could be inverted on \overline{u}^{k+1}(x) in a feasible time, which contradicts (B_{∗}). So b is (1 − ε, T) -isolated from f for some constant ε > 0 and any feasible T (n).

For l(n) = ⌊log r(\sqrt{n})⌋ and k(∥s∥) ≤ 2∥s∥, the Corollary in section 3 implies that v_{k}(s) = b_{l}(f_{l}^{k}(s)) is independent from f_{l}^{k+1}, i.e., (p, T)-isolated for any feasible T/p. Let g_{x∘y}(s) = g_{y}(g_{x}(s)) ∈ {±1}^{∥s∥} and g_{−1}(s) ∘ g_{1}(s) = v_{1}(s) ∘ ... ∘ v_{2∥s∥}(s). Let \overline{x} be a prefixless code of x, say, every digit of x is doubled and the last digit of the result altered. The parallel pseudo-random generator G_{s}(x) outputs the last bit of g\overline{x}(s). (See also 5.4)

Unpredictability. Let S_{x} consist of all prefixes of \overline{x} ∈ S with the last digits altered and \overline{x}. Any \overline{y} extends an element of S_{x}. For α : S → \{±1\}^{n}, let α_{x}^{∗}(y) be the last digit of g_{y_{2}}(α(y_{1})), where y_{1} ∘ y_{2} = \overline{y}, y_{1} ∈ S_{x}. Clearly, α_{x}^{∗} = G_{s} for any x, if for all y α(y) = g_{y}(s). Let t be a predicting test with non-negligible t_{G} and x = x(ω) be its focal string. Let t^{∗}(ω, α, n) be t(ω, α_{x}^{∗}, n) (or 0 if t < t_{G}/2). For a truly random α no correlated predictions are possible and t^{∗} averages to 0, while t_{G}^{∗} ≥ t_{G}/2. Note that t^{∗} queries α only on S_{x}.

Let us consider a hybrid α.j of g with a truly random α. It copies α except that the k-th bit α.j_{k}(y) of α.j(y ∘ −1) ∘ α.j(y ∘ 1) is v_{k}(α.j(y)) when k + 2n∥y∥ > j. Having f_{l}^{k+1}(α(y)) and values of α on all z ≠ y, one can easily compute α.j(z) for any z ≠ y and j ≥ k + 2n∥y∥. Note that α.j(y) = α(y) for j > 2n∥y∥ and α.0(y) = g_{y}(α(∅)). Now we proceed as in section 2: compute x = x(ω), choose at random its prefix y and k ≤ 2n and put j := k + 2n∥y∥. Then from f_{l}^{k+1}(α(y)) (and irrelevant values of α(z) for z ≠ y) we compute a prediction p := t^{∗}(ω, α.j, n)α.j_{k}(y)∥x∥ for v_{k}(α(y)). Their covariation is t_{G}^{∗}/2n, since each j contributes (t_{α.j−1}^{∗} − t_{α.j}^{∗})/2n. This contradicts the independence of v_{k} from f_{l}^{k+1}, noted above.

5 Notes

5.1 Turing machines

Any simple time bound > ∥x∥ log ∥x∥ in the definition of u works as well. One can even take O(∥x∥) if the Turing machine model is modified slightly. Standard Turing machines create difficulties in accurate complexity considerations. For example, the halting problem with the time bound, say ∥x∥^{3}, takes more time than O(∥x∥^{3}). These problems disappear if Turing machines have unlimited capacity for creating and destroying additional heads in the leftmost cell of the tape. These heads work independently: they can communicate only in neighboring cells and do not collide. The total running time of all heads taken as complexity makes these machines close to standard ones in terms of efficiency.

5.2 Optimal inverting algorithm

For any algorithm f there is an inverse A with optimal (up to a constant factor) running time for f(A(y)). It is not known, of course, whether the running time of A is polynomial or exponential compared to the running time of f. It is only observed that there is no speed up for inverting problems [Levin 73/84]. Thus, we can treat the time for inverting f as a definite function.

5.3 Averaging

The above conjectures (A-D) remain equivalent (due to a “padding argument”) if OW uses time, infeasible “on average”, rather than on a polynomial fraction. The averaging should be done in the following machine independent way. A function t(x) is called constant on average for probability distribution μ, if its expectation ∑ t(x)μ(x) < ∞. An example is t(x) = m(x)/μ(x), where ∑ m(x) < ∞. Any l(x) ≤ ∥x∥t(x) is called linear on average. The “average” growth rate of f is then f_{l}(n) = max{f(x) : l(x) ≤ n}, in contrast to the worst case growth rate: max{f(x) : ∥x∥ ≤ n}. A function f is infeasible on average if f_{l} is infeasible for all such l. The norm is the largest (up to a constant factor) linear on average l with enumerable subgraph {(x, q) : q < l(x)}. It can be obtained when m is the distribution of outputs of U(α) on random α ∈ Ω. The rare instances have large norms and affect little the average growth rate.

Combining this concept with the optimal inverting algorithm we get a uniquely (within a constant factor) defined average inverting time I(f/h) of algorithm f on the probability distribution generated by h.

5.4 Improvements

1. The program of t′′ in the proof in section 2 need not be known. It can be chosen at random! Moreover, a slightly more complicate construction makes the inputs G, n unnecessary as well.

2. The generator G in section 4 may be sped up in case of ∥x∥ >> ∥s∥. Just preprocess x into x′ = (x mod s′) where s′ is a new random prime seed independent of s. This transformation is secure in case of truly random functions. Thus, it must be secure in the pseudorandom case as well.

5.5 Statistical Estimates

The following simplification of the Central Limit Theorem, pointed out by A.S. Nemirovsky suffice for our needs: Let f_{i,j}, i ≤ a, j ≤ b^{2} be independent random variables with the same expectation M and standard deviations ≤ 1. The standard deviation of F_{i} = ∑_{j} f_{i,j}/b^{2} is ≤ 1/b and the probability that |F_{i}−M| ≥ 2/b is ≤ 1/4. So, the probability that most of F_{i} (and thus their median m) are to the right (or left) of [M ± 2/b], is exponentially small in a.

5.6 Better precision

1. In case log log r(n) = o(log n) all results of the paper remain true if infeasible are considered functions > r^{ε}(n/ log^{1/ε} r(n)). In any case B_{∗} remains equivalent if n log r(n) is increased to r(n^{o(1)}) (the same proof of necessity in section 4 applies).

2. Let f be invertible in a feasible time only on a negligible fraction of instances. Suppose for some coding y = C_{ε}(x), a list of strings including x can be computed in polynomial (in ∥x∥/ε) time from any y′ with 1/2 + ε fraction of digits common with y. Then for a negligible ε(∥x∥), b′ will be independent from f. So, one can take l = 1 and MIL from section 3 need not be used at all; n log r(n) can be replaced by O(n) in the definition of B_{∗} and a more accurate threshold of r^{ε}(n) can be used instead of r(n^{ε}) in the definition of infeasibility. P. Elias has shown that Random Linear Codes have all needed properties, if they are decodable in polynomial time. In this case b(s, i), equal to the inner product of s, i as vectors in Z_{2}^{n}, is independent from f′(s, i) = (f(s), i) and b(x, f^{k}(y)) is a pseudorandom generator.

Acknowledgments. I am most grateful to P. Gacs, O. Goldreich, S. Goldwasser, P. Elias and S. Micali for a great help.

References

[1] L. Blum, M. Blum, M. Shub. A Simple Secure Pseudo-Random Number Generator. Advances in Cryptology, ed. D. Chaum, R.L. Rivest and A.T. Sherman, Plenum Press, 1983, pp 61-78.

[2] M. Blum, S. Micali. How to generate Cryptographically Strong Sequences of Pseudo Random Bits. FOCS-1982; SIAM J. Comput. 13:850-864, 1984.

[3] O. Goldreich, S. Goldwasser, S. Micali. How to Construct Random Functions. Proc. 25th Symp. on Foundations of Computer Science, 1984; J. ACM, 33(4):792-807, 1986.

[4] S.Goldwasser. Probabilistic Encryption: Theory and Applications, Ph.D. Dissert., University of California at Berkeley (1984), Section 4.2.3.

[5] J.Justesen. A class of constructive, asymptotically-good, algebraic codes. IEEE Trans. Inform. Theory, IT-18, 5, (1972), 652-656.

[6] A.N. Kolmogorov. Three Approaches to the Concept of the Amount of Information. Probl. Inf. Transm., 1(1), 1965.

[7] L. Levin. Average Case Complete Problems. SIAM J. Comput. 1:285-286, 1986.

[8] L. Levin. Randomness Conservation Inequalities. Information and Control 61, 1984, section 1.3; In less detail in Theorem 2 of: Universal Sequential Search Problems, Probl. Inf. Transm. 9(3), 1973.

[9] C. Rackoff. Personal communication. 1985.

[10] A. Shamir. On the Generation of Cryptographically Strong Pseudo-Random Sequences. ACM Trans. on Comp. Syst. 1:38-44, 1983.

[11] A. D. Wyner. The wire-tap channel. Bell System Technical Journal 54:1355-1387, 1975.

[12] A. C. Yao. Theory and Applications of Trapdoor Functions. Proc. 23rd IEEE Symp. on Foundations of Computer Science pp. 80-91, 1982.