Randomness Extraction

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

Status	Problem	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 \(\mathrm{poly}(n,\log k)\) for \(k\) up to \(2^{n^{0.01}}\). A \(\mathrm{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)