One way functions and pseudorandom generators (Q1100894)

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 \textit{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 \textit{M. Blum} and \textit{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 \textit{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.