Recent Developments in Explicit Constructions of Extractors

By Ronen Shaltiel. 2002

342 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

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].”
Linear degree extractors and the inapproximability of max clique and chromatic number (2006, neutral): “See the surveys [34, 39] for more on extractors.”
Quantum And Relativistic Protocols For Secure Multi-Party Computation (2009, background): “For more general extractors, constructions which require a much shorter R are known (see [24] for a recent review).”
Reusable cryptographic fuzzy extractors (2004, background): “A number of optimal constructions that also minimize the size of r are surveyed in [15].”
2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction (2012, background): “(Many of the applications and constructions are for a related notion called seeded extractors, which are two source extractor in which the second source is very short but assumed to be completely uniform, see [Sha02] for a survey of much of this work.”
Rainbow Connections of Graphs: A Survey (2011, background): “See [54] for a good but somewhat outdated survey on extractors.”
Differential Privacy (2006, neutral): “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”
Lossy trapdoor functions and their applications (2008, background): “In general, this can be done using any strong randomness extractor (see Shaltiel’s survey for details [42]).”
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes (2007, neutral): “(See the survey of Shaltiel [26].”
Quantum random number generators (2016, background): “In this Section, we discuss only the few concepts about extractors most relevant to QRNGs and refer the interested reader to the extensive literature on the subject, ranging from introductory tutorials (Shaltiel, 2011) to detailed surveys (Nisan, 1996; Nisan and Ta-Shma, 1999; Shaltiel, 2002).”
Our Data, Ourselves: Privacy Via Distributed Noise Generation (2006, neutral): “Optimal extractors can extract n = δ − 2 log(1/ ) + O(1) nearly-random bits with the seed length O(log |X |) (see [23] for many constructions matching the bound).”