Pseudo-random generation from one-way functions
By Russell Impagliazzo, L. Levin, Michael Luby. 1989
We show that the existence of one-way functions is necessary and sufficient for the existence of pseudo-random generators in the following sense. Let ƒ be an easily computable function such that when <italic>x</italic> is chosen randomly: (1) from ƒ(<italic>x</italic>) it is hard to recover an <italic>x</italic><supscrpt>1</supscrpt> with ƒ(<italic>x</italic><supscrpt>1</supscrpt>) = ƒ(<italic>x</italic>) by a small circuit, or; (2) ƒ has small degeneracy and from ƒ(<italic>x</italic>) it is hard to recover <italic>x</italic> by a fast algorithm. From one-way functions of type (1) or (2) we show how to construct pseudo-random generators secure against small circuits or fast algorithms, respectively, and vice-versa. Previous results show how to construct pseudo-random generators from one-way functions that have special properties ([Blum, Micali 82], [Yao 82], [Levin 85], [Goldreich, Krawczyk, Luby 88]). We use the results of [Goldreich, Levin 89] in an essential way.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
Citations in the corpus
- On the Difficulties of Disclosure Prevention in Statistical Databases or The Case for Differential Privacy (2010, background): “In particular, from the Leftover Hash Lemma [26] it is known that If H = {h : {0, 1}n 7→ {0, 1}m} is a pairwise independent family where m = k − 2 log(1/ε), then Ext(x, h) def = h(x) is a strong (k, ε)-extractor.”
- Quantum Cryptography (2006, unknown): “The possibility of doing privacy amplification in the classical setting, and of doing it by means of universal hashing, was pioneered by Bennett, Brassard and Robert in [12] and further worked out in [9, 13, 33, 36].”
- Correcting errors without leaking partial information (2005, background): “(The extractor one gets by plugging random linear codes into Lemma 4 is in fact the usual pairwise independent hashing construction [19].”
- Lecture Notes on Cryptography (2001, methodology): “We saw before that we can construct PRBGs from one-way functions [115, 111].”
- Free randomness can be amplified (2011, methodology): “w = P X? i jA ? i w , i.e. that P X 1:::X jA:::A is no-signalling. Implications for randomness extraction A further application of our result is in the context of randomness extraction, introduced in [27, 28]. This is the task of taking a string of bits about which there may be some side information”
- Robust key generation from signal envelopes in wireless networks (2007, methodology): “In the proof of the following lemma we rely on the leftover hash lemma [33] to implement the extractor H:”