R. Impagliazzo
M. Luby
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.
- 1.Blum, M., "Independent Unbiased Coin Flips From a Correlated Biased Source: A Finite State Markov Chain", 25tn FOCS, 1984, pp. 425-433.Google Scholar
- 2.Blum, M., and Mica li, S., "How to Generate Cryptographically Strong Sequences of Pseudo- Random Bits", SIAM J. or~ Computing, Vol. 13, 1084, pp. 850-864, FOCS 1082. Google ScholarDigital Library
- 3.Carter, J., and M. Wegman, "Universal Classes of Hash Functions"~ JCSS, 1979, Vol. 18, pp. 143-154.Google ScholarCross Ref
- 4.Chor, B., and O. Goldreich, "Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity", SIAM J. on Computin#, Vol. 17, t988, FOCS 1985. Google ScholarDigital Library
- 5.Goldreich, O., S. Goldwasser, and S. Micali, "How to Construct Random Functions", J. of ACM, Vol. 33, No. 4, 1986, pp. 792-807, FOCS 1984. Google ScholarDigital Library
- 6.Goldreich, O., Krawczyk, H. and Luby, M., "On tile Existence of Pseudorandom Generators'', 29th FOES, 1988, pp. 12-24.Google Scholar
- 7.Goldreich, O., and L.A. Lev}n, "A Hard-Core Predicate for any One-Way Function", these proceedings. Google ScholarDigital Library
- 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.Google Scholar
- 9.Goldwasser, S. and Micali, S., "Probabilistic Encryption," JCSS, Vol. 28, No. 2, April 1984, pp. 270-299, STOC 1982.Google ScholarCross Ref
- 10.Goldwasser, S., Micali, S. and Rackoff, C., "The Knowledge Complexity of Interactive Proof Systems,'' SIAM J. on Computing, Vol. 18, No. 1, 1989, pp. 186-208, STOC i985. Google ScholarDigital Library
- 11.Impagliazzo, R. and Luby, M., "One-way functions are essential for information based cryptography,'' submitted to CRYPTO 1989.Google Scholar
- 12.Impagliazzo, R. and Rud{ch, S., "Limits on the Provable Consequences of One-way Functions", these proceedings Google ScholarDigital Library
- 13.Karp, R., Lipton, R., "Turing Machines that Take Advice," L ~Enseignement Mathematique, Vol. 28, pp. 191-209 (1982), STOC 1980Google Scholar
- 14.Levin, L.A., "One-Way Function and Pseudorandom Generators": Combinatorica, Vol. 7, No. 4, 1987, pp. 357-363, STOC 1985. Google ScholarDigital Library
- 15.Luby M., and Rackoff, C., "How to Construct Pseudorandom Permutations From Pseudorandora Functions", SiAM J. on Computing, Vol. 17, 1988, pp. 37;}-386, STOC 1986 Google ScholarDigital Library
- 16.Mclnnes, J., "Cryptography Using Weak Sources of Randomness,'; Tech. Report 19~/87, U. of Toronto, 1987.Google Scholar
- 17.Naor, M., personal communication, 1988.Google Scholar
- 18.Naor, M. and Yung, M., "Universal One-way Hash Functions and Their Applications", these proceedings. Google ScholarDigital Library
- 19.Renyi, A., Probability Theory, North- Itolland, Amsterdam, 1970.Google Scholar
- 20.Shannon, C., "A Mathematical Theory of Communication'', Bell Systems Technical Journal, 27, 1948, pp. 379-423 and pp. 623-656.Google ScholarCross Ref
- 21.Santha, M. and Vazirani, U., "Generating Quasi-random Sequences from Slightly-random Sources", 25ta FOCS, 1984, pp. 434-440, JCSS, Vol. 33, No. 1, 1986. Google ScholarDigital Library
- 22.Vazirani, U., "Towards a Strong Communication Complexity Theory or Generating Quasirandom Sequences from Two Communicating Slightly-random Sources'", 17ta STOC, 1985, pp. 366-378, Combinatorica, Vol. 7, No.4, 1987. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 24.Yao, A.C., "Theory and Applications of Trapdoor Functions", 23ra FOGS, 1982, pp. 80-91.Google Scholar
Index Terms
- Pseudo-random generation from one-way functions
Recommendations
Pseudo-random Generators from One-way Functions (Abstract)
CRYPTO '91: Proceedings of the 11th Annual International Cryptology Conference on Advances in CryptologyOne of the basic primitives in cryptography and other areas of computer science is a pseudo-random generator. The usefulness of a pseudo-random generator is demonstrated by the fact that it can be used to construct a private key cryptosystem that is ...
Non-adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions
Advances in Cryptology – EUROCRYPT 2023AbstractIn this work we give the first non-adaptive construction of universal one-way hash functions (UOWHFs) from arbitrary one-way functions. Our construction uses calls to the one-way function, has a key of length , and can be implemented ...
Pseudorandom generators from one-way functions: a simple construction for any hardness
TCC'06: Proceedings of the Third conference on Theory of CryptographyIn a seminal paper, Håstad, Impagliazzo, Levin, and Luby showed that pseudorandom generators exist if and only if one-way functions exist. The construction they propose to obtain a pseudorandom generator from an n-bit one-way function uses $\mathcal{O}(...
Comments