Leftover Hash Lemma Extraction Bound for Unpredictable Random-Oracle Sources, Secret Seed
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
Withdrawn on 17 August 2026, at the author’s request. This page is no longer tracked as an open problem and does not appear in the area, form or model listings. It stays here, and its URL keeps working, because nothing under c/ is ever deleted – see CONTRIBUTING.md.
The statement below is not retracted as mathematics. It remains Conjecture 1 of the shared write-up, whose LaTeX and PDF are still linked from this page, and no proof of it was ever recorded here.
View PDF · Download LaTeX source – states both the secret-seed and public-seed variants (Conjectures 1 and 2 respectively); the public-seed case is tracked separately as c/0004
Setting
Fix nonempty finite sets \(\mathcal{K}\) (seeds), \(\mathcal{D}\) (inputs), \(\mathcal{R}\) (outputs), and write \(K := |\mathcal{K}|\), \(D := |\mathcal{D}|\), \(R := |\mathcal{R}|\). Let \(\mathsf{Fun}(\mathcal{K}\times\mathcal{D},\mathcal{R})\) be the set of all functions \(\mathcal{K}\times\mathcal{D}\to\mathcal{R}\), let \(\mathrm{SD}(\cdot,\cdot)\) denote statistical distance, and \(U_\mathcal{R}\) the uniform distribution on \(\mathcal{R}\). The source \(S\), the predictor \(P\), and the distinguisher \(\mathsf{D}\) below are all computationally unbounded and receive the entire function table of \(H\) as an explicit input.
| Game \(\mathsf{Pred}^{S}_{P}\) | Game \(\mathsf{Ext}^{S}_{\mathsf{D}}\) (secret seed) |
|---|---|
| \(H \stackrel{\$}{\leftarrow} \mathsf{Fun}(\mathcal{K}\times\mathcal{D},\mathcal{R})\) \((x,z) \stackrel{\$}{\leftarrow} S(H)\) \(x' \stackrel{\$}{\leftarrow} P(H,z)\) return \((x = x')\) |
\(H \stackrel{\$}{\leftarrow} \mathsf{Fun}(\mathcal{K}\times\mathcal{D},\mathcal{R})\) \((x,z) \stackrel{\$}{\leftarrow} S(H)\); \(\mathit{sd} \stackrel{\$}{\leftarrow} \mathcal{K}\) \(y_0 \leftarrow H(\mathit{sd},x)\); \(y_1 \stackrel{\$}{\leftarrow} \mathcal{R}\) \(b \stackrel{\$}{\leftarrow} \{0,1\}\) \(b' \stackrel{\$}{\leftarrow} \mathsf{D}(H, y_b, z)\) return \((b = b')\) |
Prediction game (left) and the secret-seed extraction game (right). The seed \(\mathit{sd}\) is still drawn, and still selects the row of \(H\) that produces the real challenge, but \(\mathsf{D}\) never receives it. That single omission is the only difference from the public-seed game of c/0004.
Set \(\mathbf{Adv}^{\mathrm{pred}}_{\mathcal{K},\mathcal{D},\mathcal{R},S}(P) := \Pr[\mathsf{Pred}^{S}_{P} \Rightarrow 1]\) and \[ \mathbf{Adv}^{\mathrm{ext}}_{\mathcal{K},\mathcal{D},\mathcal{R}}(S,\mathsf{D}) := 2\Pr[\mathsf{Ext}^{S}_{\mathsf{D}} \Rightarrow 1] - 1 . \] A source \(S\) is \(\epsilon\)-unpredictable if \(\mathbf{Adv}^{\mathrm{pred}}_{\mathcal{K},\mathcal{D},\mathcal{R},S}(P) \le \epsilon\) for every unbounded predictor \(P\).
The Conjecture
There is a universal constant \(c > 0\), independent of \(\mathcal{K}\), \(\mathcal{D}\), \(\mathcal{R}\) and \(\epsilon\), such that for all nonempty finite \(\mathcal{K}, \mathcal{D}, \mathcal{R}\), all \(\epsilon \in (0,1]\), every \(\epsilon\)-unpredictable source \(S\), and every unbounded distinguisher \(\mathsf{D}\), \[ \mathbf{Adv}^{\mathrm{ext}}_{\mathcal{K},\mathcal{D},\mathcal{R}}(S,\mathsf{D}) \;\le\; \delta(\epsilon, K, D, R) \;:=\; c \cdot \sqrt{\frac{\epsilon R + \log_2 D}{K}} \; . \]
Why this is not c/0004
Both summands sit under one square root here, and the whole expression carries the \(1/K\). That is what a secret seed buys: the seed is \(\log_2 K\) bits of entropy the distinguisher does not have, so it can help against the entropy-deficiency term as well as against the adversarial-support term, and both decay as the seed space grows.
Publishing the seed breaks exactly that. The proof attached to c/0004 shows the transposed bound \(c\sqrt{(\epsilon R + \log_2 D)/K}\) is false once \(\mathsf{D}\) receives \(\mathit{sd}\): with the seed in hand \(\mathsf{D}\) can compute the whole row \(x \mapsto H(\mathit{sd},x)\) and test image membership, an attack that does not weaken as \(K\) grows. So the public-seed bound needs a \(\sqrt{\epsilon R}\) term standing outside the \(1/K\), and the two conjectures are genuinely different claims rather than restatements.
No proof attempt is recorded here.
The secret-seed case is the one the public-seed proof takes as its foil rather than its input: that note proves the public-seed bound and disproves the naive transposition of this one, but it does not prove this one. Whether the four-step argument there (flatten the source to a fixed-size support, compute the mean statistical distance, control the deviation uniformly by a bounded-differences inequality, average) adapts to the secret-seed game, and whether it gives the combined-square-root shape above, is untested.
Formal artifact.
Not yet formalized in Lean, neither the statement nor the proof.
The Lean statement for c/0004 is close to reusable: its Source, Predictor and games are the same objects, and the secret-seed game is that file’s extGame with the seed argument dropped from the distinguisher. Sharing those definitions across the two statements, rather than copying them, is the obvious first move and has not been made.
This statement is withdrawn and is kept only so its identifier does not 404 — nothing under c/ is ever deleted. It was the secret-seed half of a pair of conjectures stated in one write-up; the public-seed half is c/0004, which was resolved. No proof of the secret-seed case was ever recorded here, and the bound referred to informally in the public-seed write-up came from a companion note that is not on the site.
The problem page carries the parameter lattice for both, including the two \(k\)-source cells nobody has stated.