Extractors enable randomness from weak samplable sources with lower assumptions
Multiplicative and Additive Extractors for Low Entropy Samplable Sources Under Reduced Assumptions
Computational Complexity
Summary
Randomness is important for computers, especially for secure communication, but sometimes the available data isn’t very random. The authors found better ways to extract randomness from certain weak data sources that are generated by computer programs, using fewer or weaker assumptions than before. They offer three methods to turn these imperfect sources into nearly perfect random bits, even when the original data is very limited in randomness. This helps make cryptographic keys more secure when starting from weaker or more complex sources.
What this means in practice
- •For cryptographic engineers: Generate reliable cryptographic keys from weak or complex random sources using extractors with reduced hardness assumptions.
- •For security software developers: Improve randomness extraction modules in security protocols by implementing multiplicative extractors that work under weaker assumptions.
A theory result. No direct application yet.
Authors
Marshall Ball, Eshan Chattopadhyay, Mohit Gurumukhani, Ronen Shaltiel, Yunya Zhao
Abstract
Trevisan and Vadhan [TV, FOCS'00] constructed (seedless) extractors for distributions samplable by poly-size circuits that have very high min-entropy, under the very strong complexity theoretic hardness assumption that $\mathsf{E}=\mathsf{DTIME}(2^{O(n)})$ requires size $2^{Ω(n)}$ circuits that have oracle access to $Σ_6^{\text{P}}$. In this paper we give three new explicit constructions of extractors for samplable distributions. First, we construct an extractor that extracts one bit, with constant error, for min-entropy $k=O(\log n)$, which matches the non-constructive probabilistic argument. This result uses hardness for nondeterministic circuits, and achieves the same parameters as the recent extractor of Oh and Shaltiel [OS, STOC'26] under an incomparable hardness assumption. In contrast to the extractor of [OS26], our extractor (and, similarly, the constructions below) also works for the more general class of distributions samplable with postselection (a model introduced by [BGDM, FOCS'23] that generalizes samplable and recognizable sources). Second, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=n^α$, where $α>0$ is an arbitrary constant. This result also uses hardness for nondeterministic circuits, and significantly improves upon the recent extractor of [Shaltiel, FOCS'25] which required a much stronger assumption. This extractor is also \textit{multiplicative}: a stronger notion suggested in [AASY, Comp. Complexity'16; Shaltiel, CCC'25] to make extractors for samplable distributions suitable for selecting keys for cryptographic protocols. Third, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=\mathrm{polylog}(n)$. This result uses hardness for circuits that have oracle access to $Σ_2^{\text{P}}$.