Randomness is Linear in Space

By Noam Nisan, David Zuckerman. 1996

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): “There are good constructions of strong extractors; see [29, 31].”
Correcting errors without leaking partial information (2005, methodology): “[23] N. Nisan, D. Zuckerman.”
Message-Locked Encryption and Secure Deduplication (2013, methodology): “Our SXE (Sample-extract-encrypt) MLE scheme is inspired by locallycomputable extractors [3, 36, 46] and the sample-then-extract paradigm [40, 46].”
Foundations of Cryptography: Volume 1, Basic Tools (2001, unknown): “4 For example, one can use a generic transformation of [177].”
Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors (2000, methodology): “As noted in the defining paper of [ NZ96 ], an extractor can be vi ewed as a bipartite graph with left-hand side and right-hand side , where we place an edge between and for every such that . The definition of extractors can be viewed as an expansion pr operty of this graph, and our extractor constr”
Quantum random number generators (2016, background): “Seeded randomness extractors were first defined in (Nisan and Zuckerman, 1996) in the context of randomized algorithms.”
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing (1997, methodology): “The only previousresult achieving such a quality-size trade-o is by Nisan and Zuckerman [29].”
ENTROPY WAVES, THE ZIG-ZAG GRAPH PRODUCT, AND NEW CONSTANT-DEGREE (2004, background): “ctors. The current paper is part of research described in our conference paper [RVW00] which deals with constructions of both expanders and extractors. Extractors are combinatorial objects, deﬁned by [NZ96], which, roughly speaking, “purify” arbitrary nonuniform probability distributions into unifor”
PUFKY: A Fully Functional PUF-Based Cryptographic Key Generator (2012, methodology): “In addition to these best practice methods, strong extractors [18] have been proposed as unconditionally secure extractors of uniform randomness.”
Information-Theoretic Key Agreement: From Weak to Strong Secrecy for Free (2000, background): “For an introduction and some constructions, see for example [15], [17], or [16], and the references therein.”
Recent Developments in Explicit Constructions of Extractors (2002, methodology): “unconditional constructions of pseudo-random generators for probabilistic algorithms with small memory [ NZ96 , INW94, RR99].”
Undirected ST-connectivity in log-space (2005, background): “[1], and continued with Nisan and Zuckerman [35] is to fully derandomize (i.”
Reusable cryptographic fuzzy extractors (2004, background): “Intuitively, a (non-fuzzy) strong randomness extractor [13] is a randomized function that tranforms its input from any biased distribution of sufficient min-entropy into an output that appears to be drawn from an almost uniform distribution.”
Differential Privacy (2006, unknown): “Finally, it chooses a seed s and uses a strong randomness extractor to obtain from w an (cid:5) -bit almost-uniformly distributed string r [16, 17]; that is, r = Ext( s, w ), and the distribution on r is within statistical distance (cid:6) from U (cid”
Cryptography from Anonymity (2006, background): “Anonymous communication has also been exploited in the context of practically oriented applications such as voting [13] and electronic cash [49].”
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes (2007, methodology): “For example, this allows extractors to be used for ef.ciently simulating randomized algorithms using only a weak random source [Zuckerman 1996; Nisan and Zuckerman 1996].”