Abstract
In 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}(n^8)\) random bits in the input (which is the most important complexity measure of such a construction). In this work we study how much this can be reduced if the one-way function satisfies a stronger security requirement. For example, we show how to obtain a pseudorandom generator which satisfies a standard notion of security using only \(\mathcal{O}(n^4log^2(n))\) bits of randomness if a one-way function with exponential security is given, i.e., a one-way function for which no polynomial time algorithm has probability higher than 2 − cn in inverting for some constant c.
Using the uniform variant of Impagliazzo’s hard-core lemma given in [7] our constructions and proofs are self-contained within this paper, and as a special case of our main theorem, we give the first explicit description of the most efficient construction from [6].
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-540-32732-5_32
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
Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. Siam Journal on Computation 13(4), 850–864 (1984)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. Journal of the ACM 33(4), 792–807 (1986)
Goldreich, O., Krawczyk, H., Luby, M.: On the existence of pseudorandom generators. Siam Journal on Computation 22(6), 1163–1175 (1993)
Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pp. 25–32 (1989)
Haitner, I., Harnik, D., Reingold, O.: On the power of the randomized iterate. Technical Report TR05-135, Electronic Colloquium on Computational Complexity (ECCC) (2005)
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. Siam Journal on Computation 28(4), 1364–1396 (1999)
Holenstein, T.: Key agreement from weak bit agreement. In: Proceedings of the Thirty Seventh Annual ACM Symposium on Theory of Computing, pp. 664–673 (2005)
Holenstein, T., Renner, R.: On the smooth Rényi entropy of independently repeated random experiments (in preparation, 2005)
Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: The 36th Annual Symposium on Foundations of Computer Science, pp. 538–545 (1995)
Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions (extended abstract). In: Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pp. 12–24 (1989)
Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. Siam Journal on Computation 17(2), 373–386 (1988)
Luby, M., Wigderson, A.: Pairwise independence and derandomization. Technical Report ICSI TR-95-035, International Computer Science Institute, Berkeley, CA (1995)
Naor, M.: Bit commitment using pseudorandomness. Journal of Cryptology 4(2), 151–158 (1991)
Shoup, V.: Sequences of games: a tool for taming complexity in security proofs. Technical Report 332 (2004), http://eprint.iacr.org/2004/332
Wee, H.: On obfuscating point functions. In: Proceedings of the Thirty Seventh Annual ACM Symposium on Theory of Computing, pp. 523–532 (2005)
Yao, A.C.: Theory and applications of trapdoor functions (extended abstract). In: The 23rd Annual Symposium on Foundations of Computer Science, pp. 80–91 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Holenstein, T. (2006). Pseudorandom Generators from One-Way Functions: A Simple Construction for Any Hardness. In: Halevi, S., Rabin, T. (eds) Theory of Cryptography. TCC 2006. Lecture Notes in Computer Science, vol 3876. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11681878_23
Download citation
DOI: https://doi.org/10.1007/11681878_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32731-8
Online ISBN: 978-3-540-32732-5
eBook Packages: Computer ScienceComputer Science (R0)