Randomness Extraction

Extracting near-uniform randomness from a weak or structured source.

Status	Statement	Tags
	SZK Batch Verification Named by the source as the most pressing open question its work leaves. Its Theorem 1.1 gives the NISZK analogue: communication and CRS length poly(n, log k) for k up to 2⁽ⁿ0.01). A poly(n) dependence is unavoidable even at k = 1 under a sub-exponential hardness assumption, so log k is the aggressive part of the bound. The source also offers a weaker fallback target: any sub-linear dependence on k. 5 open	Batch Verification Direct Product Theorems Limited Independence Randomness Extractioncharacterization
	Split-source decomposition Open for a query budget of two or more: whether a random oracle decomposes into bit-fixing mixtures when the advice is produced by two sources that never communicate. Proved and tight at q = 0, and proved at q = 1 under an extra hypothesis. 4 open	Multi Source Extractors Random Oracle Model Randomness Extractionromtight-bound
	Seeded Extractors Are Multi-Instance Posed by the source with both answers live. It proves the property for two code-based extractors via a hinting property it isolates; concurrent independent work of Dinur, Stemmer, Woodruff and Zhou proves it for universal hash functions by a different argument. No extractor is known to fail it and no general proof is known. 4 open	Incompressible Encryption Randomness Extractioncharacterization
	LHL extraction, public seed Proven, and the statement is now formalized in Lean with an AI match check: the public-seed bound holds with a concrete constant, but the proof itself is still only informal (PDF), unreviewed, and unformalized. 6 open	Leftover Hash Lemma Random Oracle Model Randomness Extractionromtight-boundresearch-solvedadaptation (ai)