2012 · 22 citations · 18 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsProbability TheoryCryptographic ComplexityGenerating FunctionsRandomized AlgorithmsRandomized ComputationOne-way FunctionsPseudo-random Number GenerationPseudo-random Number GeneratorsPseudorandom FunctionsPseudorandom GeneratorsPseudorandomness
We show that a black-box construction of a pseudorandom generator from a one-way function needs to make Ω(n/log(n)) calls to the underlying one-way function. The bound even holds if the one-way function is guaranteed to be regular. In this case it matches the best known construction due to Gold Reich, Krawczyk, and Luby (SIAM J. Comp. 22, 1993), which uses O(n/log(n)) calls.
18
How to construct random functions
Oded Goldreich, Shafi Goldwasser, Silvio Micali · Journal of the ACM · 1986 · 2.1K citations · Full text
A Pseudorandom Generator from any One-way Function
Johan Håstad, Russell Impagliazzo, Leonid A. Levin et al. · SIAM Journal on Computing · 1999 · 1.7K citations
A hard-core predicate for all one-way functions
Oded Goldreich, Leonid A. Levin · 1989 · 1.2K citations
Theory and application of trapdoor functions
Andrew Chi-Chih Yao · 1982 · 954 citations