L A Levin
ABSTRACT
One-way are those functions which are easy to compute, but hard to invert on a non-negligible fraction of instances. The existence of such functions with some additional assumptions was shown to be sufficient for generating perfect pseudorandom strings |Blum, Micali 82|, |Yao 82|, |Goldreich, Goldwasser, Micali 84|. Below, among a few other observations, a weaker assumption about one-way functions is suggested, which is not only sufficient, but also necessary for the existence of pseudorandom generators. The main theorem can be understood without reading the sections 3-6.
- L. Blum, M. Blum, M. Shub, A Siml)l~ Secure Pseudo-Random Number Generator, Advances in Cryptology ed. D. Chaum. R.I. Rivest and A.T. S}herman, Plem\num Pres, 1983. pp 61-78Google Scholar
- M. Blunl, S. Mieali, llow to generate ~;ryptographically Strong Sequences of Pseudo Random Bits, FOCS Symp. Proc. (1982); SIAM J. on Cornput, Jug. 13 ( 1984 ) pp.85()--8~~4.Google Scholar
- O. Goldreich, S. Goldwasser, S. Mirali, How toConstruct Random Functions, PRco. 25th Symp. on l~))undations' of Computer Science (1984).Google Scholar
- S. Goldwasser, Probabilistic Encryption: 'l'heory and Applications. Ph.D. Dissert., University of California at Berkeley (1984), Section 4.2.3. Google ScholarDigital Library
- L. kevin, Universal Sequential Search Problems, Probl. Inf. 7~ansm. 9/3, (1973)pp. 265-266.Google Scholar
- L, Levin, Average Case Complete Problems. 1984 ACM Syrup. on Theory of Computing, Proc.Google Scholar
- L. Levin: Randomness Conservation Inequalities, Information and Control 60 (1984). Google ScholarDigital Library
- A. Shamir, On i, he Generation of Cryptograpitically Strong I'seudo-Random Sequences, Lec. turc Notes in Computer Science 62, Springer ~erlag, 1981, pI>. 544-550. Google ScholarDigital Library
- A. D. Wyner, The wire-tap channel, Bell System 'l~:chnica!Journal 54, (1975), pp. 1355-1387.Google Scholar
- A. C. Yao, Theory and Applications of Trapdoor Functions, t>roc. 23rd IEEE Syrup. on l;bun. dations of Computer Science {1982) pp. 80-91.Google Scholar
Index Terms
- One-way functions and pseudorandom generators
Recommendations
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}(...
Efficiency improvements in constructing pseudorandom generators from one-way functions
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computingWe give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Hastad, Impagliazzo, Levin, and Luby [SICOMP '99]. The key to our ...
Efficient pseudorandom generators from exponentially hard one-way functions
ICALP'06: Proceedings of the 33rd international conference on Automata, Languages and Programming - Volume Part IIIn their seminal paper [HILL99], Håstad, Impagliazzo, Levin and Luby show that a pseudorandom generator can be constructed from any one-way function. This plausibility result is one of the most fundamental theorems in cryptography and helps shape our ...
Comments