zbMATH — the first resource for mathematics

One way functions and pseudorandom generators. (English) Zbl 0641.68061
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 A. N. Kolmogorov [Probl. Peredachi Inf. 1, No.1, 3-11 (1965; Zbl 0271.94018)], but testing that requires an unrealistic amount of time (say, exhaustive search for the seed). Such pseudorandom generators were first discovered by M. Blum and S. Micali [SIAM J. Comput. 13, 850-864 (1984; Zbl 0547.68046)] 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. By A. C. Yao [“Theory and application of trapdoor functions”, Proc. 23rd Annu. IEEE Symp. Found. Comput. Sci., 80-91 (1982)] 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.

68Q25 Analysis of algorithms and problem complexity
94A60 Cryptography
65C10 Random number generation in numerical analysis
Full Text: DOI
[1] L. Blum, M. Blum andM. Shub, A Simple Secure Pseudo-Random Number Generator,Advances in Cryptology (ed. D. Chaum, R. L. Rivest and A. T. Sherman), Plenum Press, 1983, 61–78.
[2] M. Blum andS. Micali, How to generate Crytographically Strong Sequences of Pseudo Random Bits,FOCS Symp. Proc. (1982);SIAM J. on Computing,13 (1984), 850–864. · Zbl 0547.68046
[3] O. Goldreich, S. Goldwasser andS. Micali, How to Construct Random Functions,Proc. 25th Symp. on Foundations of Computer Science (1984);SIAM J. on Computing,13 (1984), 850–864. · Zbl 0547.68046
[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. · Zbl 0256.94008
[6] A. N. Kolmogorov, Three Approaches to the Concept of the Amount of Information,Probl. Inf. Transm. (1965), 1/1. · Zbl 0271.94018
[7] L. Levin, Average Case Complete Problems,SIAM J. Comput. (1986), 285–286. · Zbl 0589.68032
[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 (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, (1983), 38–44.
[11] A. D. Wyner, The wire-tap channel,Bell System Technical Journal 54, (1975), 1355–1387. · Zbl 0316.94017
[12] A. C. Yao, Theory and Applications of Trapdoor Functions,Proc. 23rd IEEE Symp. on Foundations of Computer Science (1982), 80–91.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.