Pseudo-random generation from one-way functions

ABSTRACT

We show that the existence of one-way functions is necessary and sufficient for the existence of pseudo-random generators in the following sense. Let ƒ be an easily computable function such that when x is chosen randomly: (1) from ƒ(x) it is hard to recover an x1 with ƒ(x1) = ƒ(x) by a small circuit, or; (2) ƒ has small degeneracy and from ƒ(x) it is hard to recover x by a fast algorithm. From one-way functions of type (1) or (2) we show how to construct pseudo-random generators secure against small circuits or fast algorithms, respectively, and vice-versa. Previous results show how to construct pseudo-random generators from one-way functions that have special properties ([Blum, Micali 82], [Yao 82], [Levin 85], [Goldreich, Krawczyk, Luby 88]). We use the results of [Goldreich, Levin 89] in an essential way.

REFERENCES

• 1: Blum, M., "Independent Unbiased Coin Flips From a Correlated Biased Source: A Finite State Markov Chain", 25tn FOCS, 1984, pp. 425-433.
• 2: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• 3: Carter, J., and M. Wegman, "Universal Classes of Hash Functions"~ JCSS, 1979, Vol. 18, pp. 143-154.
• 4: Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
• 5: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 6: Goldreich, O., Krawczyk, H. and Luby, M., "On tile Existence of Pseudorandom Generators'', 29th FOES, 1988, pp. 12-24.
• 7: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 8: Goldreich, O., Micali, M. and Wigderson, A., "Proofs that. Yield Nothing but Their Validity and a Methodology of Cryptographic Protocol Design", 27th FOCS, 1986, pp. 174-187, Tech. Report TRd93, Comp. Sci. Dept., Technion, submitted to JA CM.
• 9: Goldwasser, S. and Micali, S., "Probabilistic Encryption," JCSS, Vol. 28, No. 2, April 1984, pp. 270-299, STOC 1982.
• 10: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 11: Impagliazzo, R. and Luby, M., "One-way functions are essential for information based cryptography,'' submitted to CRYPTO 1989.
• 12: R. Impagliazzo , S. Rudich, Limits on the provable consequences of one-way permutations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.44-61, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73012]
• 13: Karp, R., Lipton, R., "Turing Machines that Take Advice," L ~Enseignement Mathematique, Vol. 28, pp. 191-209 (1982), STOC 1980
• 14: Leonid A. Levin, One-way functions and Pseudorandom generators, Combinatorica, v.7 n.4, p.357-363, Dec, 1987 [doi>10.1007/BF02579323]
• 15: Michael Luby , Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, v.17 n.2, p.373-386, April 1988 [doi>10.1137/0217022]
• 16: Mclnnes, J., "Cryptography Using Weak Sources of Randomness,'; Tech. Report 19~/87, U. of Toronto, 1987.
• 17: Naor, M., personal communication, 1988.
• 18: M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
• 19: Renyi, A., Probability Theory, North- Itolland, Amsterdam, 1970.
• 20: Shannon, C., "A Mathematical Theory of Communication'', Bell Systems Technical Journal, 27, 1948, pp. 379-423 and pp. 623-656.
• 21: Miklos Santha , Umesh V Vazirani, Generating quasi-random sequences from semi-random sources, Journal of Computer and System Sciences, v.33 n.1, p.75-87, Aug. 1986 [doi>10.1016/0022-0000(86)90044-9]
• 22: Umesh Vazirani, Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources, Combinatorica, v.7 n.4, p.375-392, Dec, 1987 [doi>10.1007/BF02579325]
• 23: Vazirani, U. and Vazirani, V., "Random Polynomial Time is Equal to Slightly-random Polynomial Time", 26th FOGS, 1985, pp. 417-428, submitted to JA Cllf.
• 24: Yao, A.C., "Theory and Applications of Trapdoor Functions", 23ra FOGS, 1982, pp. 80-91.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Generating functions

Additional Classification:
  E. Data

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms, Design, Security, Theory