How to recycle random bits

By Russell Impagliazzo, David Zuckerman. 1989

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

Private Summation in the Multi-Message Shuffle Model (2020, neutral): “The following deﬁnition and lemma from [17] are fundamental to why this protocol is secure.”
Differentially Private Summation with Multi-Message Shuffling (2019, background): “The following definition and lemma from [6] are fundamental to why this protocol is secure.”
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing (1997, background): “in saving randomness [20], weak random sources [36], pseudorandom generators [15, 19] and interactive proofs [16].”
Leftover Hashing Against Quantum Side Information (2010, background): “Following its discussion, we extend the scenario to include side information that is potentially stored in a quantum state.”
Correcting errors without leaking partial information (2005, methodology): “To illustrate the framework, we show that random linear codes are optimal in terms of both error-correction and entropic security (this corresponds to reproving the “leftover hash” lemma [14]).”
Cryptography from Anonymity (2006, unknown): “Finally, the Leftover Hash Lemma [30] guarantees that SD((V, hV (Π)), (V, U)) ≤ 2−Ω(H∞(Π)− ) = 2−Ω(log ( 2k k )− ) from which the lemma follows.”
Random walks in peer-to-peer networks (2004, background): “The isolation of the second property has been one of the most celebrated results in complexity theory [3], [4], [5], [6].”
Estimating Renyi Entropy of Discrete Distributions (2014, background): “In particular, the Rényi entropy of order 2, H2(p), measures the quality of random number generators [19], [30], determines the number of unbiased bits that can be extracted from a physical source of randomness [6], [14], helps test graph expansion [8] and closeness of distributions [5], [34], and c”
Sequences of games: a tool for taming complexity in security proofs (2004, unknown): “It is in fact possible to construct entropy smoothing hash function families without additional hypothesis (the Leftover Hash Lemma may be used for this [ IZ89 ]).”
Linear degree extractors and the inapproximability of max clique and chromatic number (2006, unknown): “Random walks on expanders have been used to amplify the success probability of RP and BPP algorithms without using many additional random bits [2, 25, 13].”
Lower bounds for covering times for reversible Markov chains and random walks on graphs (1989, methodology): “Several other uses of random walks on expanders can be found in Ajtai et al [4], Cohen and Wigderson [97], Impagliazzo and Zuckerman [188].”