Abstract
Pseudorandom generators (suggested and developed by Blum and Micali and Yao) are efficient deterministic programs that expand a randomly selected k -bit seed into a much longer pseudorandom bit sequence which is indistinguishable in polynomial time from an (equally long) sequence of unbiased coin tosses. Pseudorandom generators are known to exist assuming the existence of functions that cannot be efficiently inverted on the distributions induced by applying the function iteratively polynomially many times. This sufficient condition is also a necessary one, but it seems difficult to check whether particular functions, assumed to be one-way, are also one-way on their iterates. This raises the fundamental question whether the mere existence of one-way functions suffices for the construction of pseudorandom generators.
In this paper we present progress towards resolving this question. We consider regular functions, in which every image of a k -bit string has the same number of preimages of length k. We show that if a regular function is one-way then pseudorandom generators do exist. In particular, assuming the intractability of general factoring, we can now prove that pseudorandom generators do exist. Other applications are the construction of pseudorandom generators based on the conjectured intractability of decoding random linear codes, and on the assumed average case difficulty of combinatorial problems as subset-sum.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
W. Alexi, B. Chor, O. Goldreich and C.P. Schnorr, “RSA and Rabin Functions: Certain Parts Arc As Hard As the Whole”, SIAM Jour. on Computing, Vol. 17, 1988, pp. 194–209.
L. Blum, M. Blum and M. Shub, A Simple Secure Unpredictable Pseudo-Random Number Generator, SIAM Jour. on Computing, Vol. 15, 1986, pp. 364–383.
Blum, M, and Micali, S., “How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits”, SIAM Jour. on Computing, Vol. 13, 1984, pp. 850–864.
Carter, J., and M. Wegman, “Universal Classes of Hash Functions”, JCSS, 1979, Vol. 18, pp. 143–154.
Chor, B., and O. Goldreich, “On the Power of Two-Point Sampling”, to appear in Jour. of Complexity.
Chor, B., O. Goldreich, and S. Goldwasser, “The Bit Security of Modular Squaring Given Partial Factorization of the Modulos”, Advances in Cryptology-Crypto 85 Proceedings, ed. H.C. Williams, Lecture Notes in Computer Science, 218, Springer Verlag, 1985, pp. 448–457.
W. Diffie, and M. E. Hellman, “New Directions in Cryptography”, IEEE transactions on Info. Theory, IT-22 (Nov. 1976), pp. 644–654
S. Even, Graph Algorithms, Computer Science Press, 1979.
Goldreich, O., S. Goldwasser, and S. Micali, “How to Construct Random Functions”, Jour. of ACM, Vol. 33, No. 4, 1986, pp. 792–807.
Goldreich, O., H. Krawczyk and M. Luby, “On the Existence of Pseudorandom Generators”, Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp 12–24.
Goldreich, O., and L.A. Levin, “A Hard-Core Predicate for any One-Way Function”, in preparations.
Goldreich, O., and S. Micali, “The Weakest Pseudorandom Bit Generator Implies the Strongest One”, manuscript, 1984.
Goldwasser, S., and S. Micali, “Probabilistic Encryption”, JCSS, Vol. 28, No. 2, 1984, pp. 270–299.
Impagliazzo, R., L.A., Levin and M.G. Luby, “Pseudorandom Number Generation from any One-Way Function”, preprint, 1988.
A. Joffe, “On a Set of Almost Deterministic k-Independent Random Variables”, the Annals of Probability, 1974, Vol. 2, No. 1, pp. 161–162.
L.A. Levin, “One-Way Function and Pseudorandom Generators”, Combinatorica, Vol. 7, No. 4, 1987, pp. 357–363. A preliminary version appeared in Proc. 17th STOC, 1985, pp. 363–365.
L.A. Levin, “Homogeneous Measures and Polynomial Time Invariants”, Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp 36–41.
M. Luby, “A Simple Parallel Algorithm for the Maximal Independent Set Problem”, SIAM J. Comput., Vol. 15, No. 4, Nov. 1986, pp. 1036–1054.
M. Luby and C. Rackoff, “How to Construct Pseudorandom Permutations From Pseudorandom Functions”, SIAM Jour. on Computing, Vol. 17, 1988, pp. 373–386.
McWilliams, F.J., and N.J.A. Sloane, The Theory of Error Correcting Codes, North-Holland Publishing Company, 1977.
M.O. Rabin, “Digitalized Signatures and Public Key Functions as Intractable as Factoring”, MIT/LCS/TR-212, 1979.
R. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public Key Cryptosystems”, Comm. ACM, Vol. 21, Feb. 1978, pp 120–126
A. Shamir, “On the Generation of Cryptographically Strong Pseudorandom Sequences”, ACM Transaction on Computer Systems, Vol. 1, No. 1, February 1983, pp. 38–44.
Yao, A.C., “Theory and Applications of Trapdoor Functions”, Proc. of the 23rd IEEE Symp. on Foundation of Computer Science, 1982, pp. 80–91.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goldreich, O., Krawczyk, H., Luby, M. (1990). On the Existence of Pseudorandom Generators. In: Goldwasser, S. (eds) Advances in Cryptology — CRYPTO’ 88. CRYPTO 1988. Lecture Notes in Computer Science, vol 403. Springer, New York, NY. https://doi.org/10.1007/0-387-34799-2_12
Download citation
DOI: https://doi.org/10.1007/0-387-34799-2_12
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-0-387-97196-4
Online ISBN: 978-0-387-34799-8
eBook Packages: Springer Book Archive