Leftover Hash Lemma extraction from unpredictable random-oracle sources

How well does H(sd, x) look uniform, when x comes from an unbounded-but-unpredictable source?

Motivation

Randomness extraction results usually assume the source is independent of the extractor’s key. Here the extractor is itself a random oracle \(H\), and the source \(S\) is allowed to see the entire function table of \(H\) before choosing its input \(x\) (together with side information \(z\)) – it’s only assumed unpredictable, not independent. Two natural games ask how close \(H(\mathit{sd}, x)\) then looks to uniform, differing in whether the extraction seed \(\mathit{sd}\) is handed to the distinguisher (public seed) or kept hidden (secret seed). Both conjectured bounds take the classical leftover-hash-lemma shape: an entropy-deficiency term plus a seed-collision term that vanishes as \(1/\sqrt{K}\) in the number of seeds \(K\).

Provenance and history

Both conjectures were stated together as a single self-contained write-up (statement by Pooya Farshim; see the shared PDF linked from c/0004). The public-seed case was resolved shortly after: an AI-written proof (Claude Opus 5, prompted by Pooya Farshim, 14 August 2026) shows the naive guess – transposing the secret-seed expression directly to the public-seed game – is false, and proves a corrected bound instead, with an explicit near-optimal constant. That proof has not yet been independently reviewed by a human, nor formalized. The secret-seed case (Conjecture 1 of the shared write-up) was tracked as c/0005, transcribed from the same PDF; no proof of it is recorded, and it was withdrawn on 17 August 2026, so it no longer appears in the listings. A bound for it was referenced only informally, via an unincluded and unverified “companion note,” in the public-seed resolution’s write-up, and that note is still not on the site.

Parameter lattice

Two independent axes: whether the seed is public or secret, and whether extraction draws from one source or from \(k\) sources jointly. Two of the four cells are tracked as their own statement on the site; the \(k\)-source column is empty.

single source \(k\)-source
public seed c/0004 – proven unstated
secret seed c/0005 – withdrawn unstated

Both tracked cells are real: the single-source public-seed cell is cited research, and the single-source secret-seed cell (c/0005) is Conjecture 1 of the same shared write-up. Neither \(k\)-source cell is stated. Nobody has posed either one, here or elsewhere that this archive knows of, and an empty cell is a research prompt rather than an omission.

Statements in this hub