Definition
A randomness extractor is an algorithm or mathematical function that transforms a source of biased or partially random bits into a shorter string that is close to uniformly random, according to some statistical distance measure (typically total variation distance). Formally, an extractor is a family of functions
$$ \text{Ext} : {0,1}^n \times {0,1}^d \rightarrow {0,1}^m $$
such that for any source $X$ on ${0,1}^n$ with min‑entropy at least $k$, the output distribution $\text{Ext}(X,U_d)$ is $\varepsilon$-close to the uniform distribution on ${0,1}^m$. Here $U_d$ denotes a uniformly random seed of length $d$, $m$ is the output length, and $\varepsilon$ is the error parameter.
Key Parameters
| Parameter | Description |
|---|---|
| $n$ | Length of the raw source string |
| $k$ | Min‑entropy of the source (a lower bound on $-\log_2 \max_x \Pr[X=x]$) |
| $d$ | Length of the uniformly random seed (zero for seedless extractors) |
| $m$ | Length of the extracted output string |
| $\varepsilon$ | Statistical distance between the output distribution and uniform |
An extractor is considered strong if the pair $(U_d,\text{Ext}(X,U_d))$ is also $\varepsilon$-close to uniform, which is useful in cryptographic applications.
Types of Extractors
- Seeded Extractors – Require a short, truly random seed $U_d$. Most theoretical constructions are of this type because a small amount of true randomness can be amplified.
- Seedless Extractors – Do not use an external seed. They rely on structural assumptions about the source, such as independence between multiple correlated sources (e.g., two‑source extractors) or algebraic properties (e.g., affine extractors).
- Deterministic Extractors for Specific Sources – For particular classes of weak sources (e.g., Santha–Vazirani sources, affine sources), deterministic constructions exist without a seed.
Historical and Notable Constructions
- Von Neumann Extractor (1951) – The earliest method, which processes bits in pairs to eliminate bias but does not increase entropy.
- Trevisan’s Extractor (1999) – A construction based on error‑correcting codes that achieves logarithmic seed length for a wide range of parameters.
- Raz’s Two‑Source Extractor (2005) – Extracts randomness from two independent weak sources, each with relatively low min‑entropy.
- Guruswami–Umans–Vadhan (GUV) Extractor (2009) – Provides almost optimal seed length and output size for many regimes.
- Explicit Constructions for Affine Sources – E.g., Bourgain’s extractor (2005) for sources that are uniform over affine subspaces.
Applications
- Cryptography – Generation of cryptographic keys from noisy physical sources (e.g., hardware random number generators) while guaranteeing unpredictability.
- Derandomization – Replacing randomized algorithms with deterministic ones by feeding them the output of an extractor applied to a weak random source.
- Complexity Theory – Proving hardness amplification results, constructing pseudorandom generators, and studying the relationships between randomness and computational resources.
- Information Theory – Data compression and privacy amplification in quantum key distribution (QKD).
Performance Guarantees
A optimal seeded extractor satisfies the information‑theoretic lower bound $m \le k - 2\log(1/\varepsilon) + O(1)$ and uses seed length $d = O(\log n + \log(1/\varepsilon))$. Many explicit constructions approach these bounds up to polylogarithmic factors.
Related Concepts
- Randomness Condenser – Reduces the length of a source while preserving most of its entropy, often used as a preprocessing step for extractors.
- Disperser – Guarantees that the output covers the entire range for any source with sufficient min‑entropy, but does not require the output to be close to uniform.
- Pseudorandom Generator (PRG) – Expands a short uniform seed into a longer sequence indistinguishable from uniform for specific computational classes; PRGs can be built from strong extractors.
References (selected)
- R. Impagliazzo, L. A. Levin, and M. Luby, “Pseudo‑Random Generation from One‑Way Functions,” SIAM J. Comput., 1990.
- L. Trevisan, “Extractors and Pseudorandom Generators,” J. ACM, 2001.
- R. Raz, “Extractors with Weak Random Seeds,” Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005.
- M. Lu, Y. T. Fedchenko, and A. Garg, “A Survey of Randomness Extractors,” Foundations and Trends in Theoretical Computer Science, 2021.
See also
- Von Neumann extractor
- Min‑entropy
- Pseudorandomness
- Derandomization
This entry summarizes established knowledge about randomness extractors as documented in peer‑reviewed literature and standard textbooks on theoretical computer science and cryptography.
