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 second term that vanishes as \(1/\sqrt{K}\) in the number of seeds \(K\). The shape is the leftover hash lemma’s, but the second term is not a collision probability – it is the union-bound cost of letting the source choose its support after seeing \(H\), and that difference is what the section below turns on.

Provenance and history

Both conjectures were stated together as a single self-contained write-up (statement by Pooya Farshim), duplicated byte-for-byte into both folders. 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 took a longer route out. It was tracked as its own statement, transcribed from the same PDF, with no proof recorded; it was withdrawn at the author’s request on 17 August 2026, and on 28 August 2026 the shared note was split so that each page stated one conjecture, after which the secret-seed page and its note were removed from the site altogether. The conjecture is not retracted as mathematics, and it is still on the site: the solution note reproduces it verbatim in its opening section, and has to, because the counterexample it proves is about an expression derived from it and one of its remarks compares against it. What is gone is the page. A bound for the secret-seed game was referenced only informally, via an unincluded and unverified “companion note,” in the public-seed resolution’s write-up, and that note was never on the site.

Two numberings are therefore in circulation, and both appear in text written before 28 August 2026: in the shared note the secret-seed conjecture was Conjecture 1 and the public-seed one Conjecture 2, while the solution note numbers them the same way for its own reasons and each split note numbered its single conjecture as Conjecture 1.

Relation to the extractor literature

Recorded 28 August 2026, in answer to the question “why doesn’t this already follow from known results?”. It largely does, and neither statement page said so.

Both conjectures are, after a change of variables, classical theorems about randomness extractors. Write \(n := \log_2 D\), \(k := \log_2(1/\epsilon)\), \(m := \log_2 R\), \(d := \log_2 K\), and balance each summand against a target error \(\delta\):

conjecture summand in extractor parameters
public seed \(\sqrt{\epsilon R} = \delta\) \(m = k - 2\log(1/\delta)\)
public seed \(\sqrt{\log_2 D / K} = \delta\) \(d = \log n + 2\log(1/\delta)\)
secret seed \(\sqrt{\epsilon R / K} = \delta\) \(m = k + d - 2\log(1/\delta)\)

These are Theorems 6.17 and 6.14 of Vadhan’s Pseudorandomness: a random function is, with high probability, a strong extractor with \(m = k - 2\log(1/\epsilon) - O(1)\) and \(d = \log(n-k) + 2\log(1/\epsilon) + O(1)\), and an ordinary (non-strong) one with \(m = k + d - 2\log(1/\epsilon) - O(1)\). The public-seed conjecture is the strong case; the secret-seed conjecture is the ordinary one. Radhakrishnan and Ta-Shma proved both sets of parameters optimal, giving \(d \ge \log(n-k) + 2\log(1/\epsilon) - O(1)\) and an entropy loss of \(d + k - m \ge 2\log(1/\epsilon) - O(1)\) for every extractor.

The correspondence is exact rather than merely of shape. The sharper of the two bounds proved in c/0004 carries \(\ln(2eD\epsilon) \approx (n-k)\ln 2\), so it delivers \(d = \log(n-k) + 2\log(1/\delta) + O(1)\) – the \(\log(n-k)\), not the cruder \(\log n\) – and the quantity \(b_t := \tfrac{1}{t}\ln\binom{D}{t}\) it introduces to get there is the textbook count of flat \(k\)-sources, \(\binom{2^n}{2^k}\).

Why the leftover hash lemma is the wrong precedent

The LHL needs the family \(\{H(k,\cdot)\}_{k \in \mathcal{K}}\) to be 2-universal. Universal families need a seed of \(\Omega(n)\) bits, that is \(K \ge D^{\Omega(1)}\), and pairwise independence needs \(K \ge D\). The regime these conjectures live in is \(K \approx \log_2 D\), where no universal family exists at all – so this is not a lossy application of the LHL, it is an inapplicable one.

The obvious repair fails too, and it fails in a way worth being precise about, because the two routes agree on more than one might expect. Condition on \(H\) and apply the collision bound \[\Delta \;\le\; \tfrac12\sqrt{R\cdot\mathrm{CP}(p) + \gamma},\qquad \gamma \;:=\; R\bar\beta - 1,\] where \(\bar\beta\) is the family’s mean collision probability on the source’s support and \(\gamma \le 0\) exactly when the family is universal there.

On the deficiency term the two routes give the identical estimate. At a flat source on \(t = 1/\epsilon\) inputs, \(\mathrm{CP} = \epsilon\) and a universal family gives \(\tfrac12\sqrt{\epsilon R}\); Lemma 3.2 of the c/0004 proof gives \(\tfrac12\sqrt{R/t}\), the same quantity. The \(1/\sqrt2\) in the theorem is only the floor step \(\lfloor 1/\epsilon_{H,z}\rfloor \ge 1/(2\epsilon_{H,z})\) in its assembly. So the leftover hash lemma loses nothing here.

The whole difference is the selection term, and the obstruction there is structural rather than statistical. The source reads the whole table before the seed exists, so it can pick a support on which \(\gamma\) is large – and one row suffices, with no probability needed anywhere.

Put \(W := \min\{R,\ \lfloor D\epsilon\rfloor\}\) and \(t := \lfloor 1/\epsilon\rfloor\). Fix a seed \(k_1\) and let \(\mathcal{S}\) be the \(R/W\) symbols occurring most often in the row \(H(k_1,\cdot)\). Those carry at least \(D/W \ge t\) inputs, so the source can be taken uniform on a \(t\)-subset \(T\) of them, which is \(\epsilon\)-unpredictable. On \(T\) the law of \(H(k_1,X)\) lives on \(R/W\) symbols, so Cauchy–Schwarz gives \(c_{k_1} \ge W/R\); the same inequality gives \(c_k \ge 1/R\) for every \(k\). Hence \[R\bar c - 1 \;\ge\; R\Bigl[\tfrac1K\tfrac{W}{R} + \tfrac{K-1}{K}\tfrac1R\Bigr] - 1 \;=\; \frac{W-1}{K}, \qquad\text{so the lemma returns at least}\quad \tfrac12\sqrt{\tfrac{W-1}{K}}.\] This holds for every table, not just a typical one. Pinning \(j\) rows instead of one replaces \(W-1\) by roughly \(j(W-1)\), buying a further \(\log_2 j\) bits – usually one or two, so the one-row form is essentially the whole effect.

The rate in \(K\) is the same square root the conjecture asks for, and what separates them is what sits under it: the lemma pays \(\sqrt{W}\), a set size, where the conjecture pays \(\sqrt{\log_2 D}\), a number of bits. Two conditions have to hold before that comparison means anything, and both are easy to lose. The floor is a bound on \(R\bar c - 1 = R\cdot\mathrm{CP} + \gamma\), so it says something about the second summand only when \((W-1)/K > R/t\); and the conjectured bound can only certify an error \(\delta\) at all when its own first summand \(c\sqrt{\epsilon R}\) is below \(\delta\). Where both hold:

\(D\) \(R\) min-entropy \(\delta\) \(W\) \(\log_2 K\) conjectured \(\log_2 K\) needed by the lemma
\(2^{256}\) \(2^{64}\) 160 \(2^{-32}\) \(2^{64}\) 74 at least 126

a gap of 52 bits.

What that gap is, cryptographically. The game is key derivation: \(x\) is a secret with entropy but no uniformity, \(\mathit{sd}\) is a public salt, \(H\) a public hash, and \(H(\mathit{sd},x)\) the derived key. So \(\log_2 K\) is the salt length. Whenever the derived key is no longer than the source’s entropy gap one has \(W = R\), and the two salt lengths read

\[\underbrace{\log_2 n + 2\log_2(1/\delta) + 2}_{\text{conjectured}} \qquad\text{against}\qquad \underbrace{m + 2\log_2(1/\delta) - 2}_{\text{collision route}},\]

with \(n = \log_2 D\) the secret’s length and \(m = \log_2 R\) the key’s. They differ in kind, not just in size: the conjectured salt grows with the logarithm of the secret’s length; the collision route’s salt grows with the length of the key being derived. Deriving a 256-bit key instead of a 128-bit one from the same secret costs no extra salt under the conjecture and 128 further bits under the route.

\(\log_2 D\) min-entropy key \(\delta\) conjectured route universal RO †
DH element in a 2048-bit group 2048 256 128 \(2^{-32}\) 77 190 1920 0
the same, 256-bit key 2048 512 256 \(2^{-64}\) 141 382 1792 0
a 512-bit source 512 300 128 \(2^{-64}\) 139 254 384 0

† The unsalted random-oracle heuristic, \(\epsilon_{\mathrm{RO}} \approx T/2^\mu\): no salt at all. That zero is the most informative entry in the row, and it is bought rather than free — the bound holds only against a distinguisher of running time \(T \le \delta 2^\mu\), which is \(2^{224}\), \(2^{448}\) and \(2^{236}\) in the three rows, and only for a source independent of \(H\). Those ceilings are enormous, which is why the heuristic is attractive in practice; but they are ceilings, and this problem lives above them, where every party reads the whole table and \(T/2^\mu\) says nothing. The independence hypothesis is the one that matters here, and that zero does not survive dropping it — not approximately. With no salt, a source that reads \(H\) and is uniform on the largest fibre of the single row has min-entropy \(\log_2 D - \log_2 R\) and is distinguished with advantage \(1 - 2^{-m}\) by an adversary making no query at all. That source is admissible in every row above (min-entropy \(1920\), \(1792\) and \(384\) against the \(256\), \(512\) and \(300\) the rows ask for), and the heuristic predicts \(2^{-1792}\), \(2^{-1536}\) and \(2^{-256}\) where the truth is \(1 - 2^{-128}\), \(1 - 2^{-256}\) and \(1 - 2^{-128}\). So the first and last salt columns are the same primitive under two different assumptions about the source — nothing if it cannot look at \(H\), \(77\) bits if it can — and the gap between them is the whole subject here.

The three columns scale in three different ways, which is the comparison in one line: \(\log_2 n + 2\log_2(1/\delta)\) conjectured, \(m + 2\log_2(1/\delta)\) for the collision route, and \(n - m\) for universal hashing. The first grows with the logarithm of the secret’s length; the second with the length of the derived key; the third with the secret’s length outright, shrinking as the key grows (1920 bits for a 128-bit key against 1792 for a 256-bit one, since a larger \(R\) weakens \(K \ge D/R\)) and not depending on \(\delta\) at all, being a structural requirement rather than an accuracy one. The last column is the salt needed for such a family to exist; at it the error is already \(2^{-65}\), \(2^{-129}\), \(2^{-87}\) in the three rows.

Read at a fixed salt instead, the route certifies an error larger than \(\delta\) by about \(\sqrt{W/\log_2 D}/(2c)\) — roughly \((m - \log_2 n)/2\) bits of security, over half the derived key’s length. At the 77-bit salt of the first row it certifies \(2^{24.5}\), which is greater than \(1\) and so nothing at all; at the 139-bit salt of the third it certifies \(2^{-6.5}\), six bits where sixty-four were wanted. None of which says a 77-bit salt is unsafe — only that this technique cannot be what establishes it.

Doesn’t that make the random oracle worse than universal hashing? No — the two are being priced at different seed lengths. A universal family gets \(\gamma \le 0\) and no second summand, but needs \(K \ge D/R\), a salt of \(n - m\) bits. Give the random table that same salt and its second summand becomes \(\sqrt{R\log_2 D/D}\), which at \(D = 2^{2048}\), \(R = 2^{128}\) is \(2^{-954.5}\) — absent. The two then tie. At the salt the problem is actually posed at, universal hashing simply does not exist: for the Diffie–Hellman row above, the conjectured bound needs 77 bits of salt and a universal family needs at least 1920, twenty-five times as long, to do the same job no better. Measured as extractors normally are — error per bit of seed — universal hashing is the seed-suboptimal one and the random oracle sits at the optimum.

The reason is worth keeping: universality survives a source that reads the whole table because it constrains every pair \(x \neq x'\) separately, so an adversary choosing pairs last gains nothing — and a worst-case-over-all-pairs hypothesis is exactly what costs \(D/R\) seeds. The immunity and the price are the same property seen twice. A random table satisfies only the average-case version, which is why support selection can hurt it at all, and why \(\log_2 n\) bits of salt suffice to stop it rather than \(n - m\).

Outside that regime the construction shows nothing: at min-entropy 254 over the same \(D\) and \(R\) one gets \(W = 4\) and no loss at all, and at \(\epsilon = 1/D\) one gets \(W = 1\) and a trivial bound – correctly, since a maximal-entropy source is uniform on all of \(\mathcal{D}\) and has nothing to select. That is the same boundary the c/0004 proof records when its own selection term vanishes at \(t = D\).

The loss is the Cauchy–Schwarz step \(\|v\|_1 \le \sqrt{KR}\,\|v\|_2\) inside the lemma, which is tight only when \(v\) is spread evenly over all \(KR\) cells; support selection puts a concentrated lump on one row instead. It is worth being careful about what that does not say: the true advantage against the constructed source is not \(O(1/K)\), because the \(K-1\) unpinned rows are not uniform either and contribute \(\Theta(\sqrt{R/t})\), which dominates. The floor is a statement about what the technique can certify, not about how weak the source is. That is why the optimal-extractor proofs work in \(L_1\) instead, by concentration plus a union bound over flat sources; the c/0004 proof takes that route, arriving at it independently. This seed-length bound is not new. It is the leftover hash lemma’s second known limitation: Barak, Dodis, Krawczyk, Pereira, Pietrzak, Standaert and Yu, Leftover Hash Lemma, Revisited (CRYPTO 2011), open by stating that an almost-universal family good enough for the LHL needs seed length at least \(\min(u-v,\ v+2\log(1/\varepsilon)) - O(1)\) — in the notation here, \(\min(\log_2 D - m,\ m + 2\log_2(1/\delta))\), which is both salt columns above as one bound — and attribute it to Stinson (1994). What that literature does not cover is this setting — though not for the reason one might guess. Its Definition 2.1 quantifies over all distributions \(X\) with the seed drawn independently of them, the extractor being a public function fixed beforehand; so a source there may already depend on the family, and need only be independent of the seed. This setting asks no more: \(\mathit{sd}\) is drawn after the source terminates. The independence hypothesis is not weakened here at all — what differs is the family, a uniformly random table in place of a universal one, and the point is that this substitution alone already costs the seed length. Separately, its random-oracle comparison bounds only one of the two parties. That comparison is unsalted — the derived key is \(H(X)\), no seed — and runs: \(H(X)\) is distinguishable only if the attacker queries at \(X\), which for min-entropy \(\mu\) and running time \(T\) has probability \(\le T/2^\mu\); calibrating \(T \approx \epsilon 2^v\) against the keyed application’s own security gives \(\epsilon_{\mathrm{RO}} \approx \epsilon 2^{-L}\), \(L = \mu - v\). The distinguisher is bounded, by \(T\). The source is not — because it is not a query-making object there at all: \(X\) is a distribution fixed independently of \(H\), and no source algorithm with oracle access appears in the model. That asymmetry is load-bearing: “distinguishable only if the attacker queried at \(X\)” is false the moment \(X\) may depend on \(H\). It is also why that comparison needs no salt and this setting does — with the distinguisher unbounded, \(T/2^\mu\) is vacuous, and indeed at \(K = 1\) the conjectured bound reads \(c(\sqrt{\epsilon R} + \sqrt{\log_2 D})\), vacuous for every \(D \ge 2\). (One-sided throughout: the lemma cannot do better than this. Whether it does this well is not claimed — the certified ceiling is some \(2^{21}\) above the floor.)

What is not classical

Three things, of which only the first is mathematics.

  1. The unpredictability hypothesis is an average over \(H\). It asks for \(\mathbb{E}_{(H,Z)}[\max_x \Pr[X = x \mid H, Z]] \le \epsilon\), so the source may have zero entropy on an \(\epsilon\)-fraction of oracles. Classical extractor statements quantify per source (“for every \(k\)-source”) and conclude with high probability over the extractor, which cannot be applied here. That is what forces the deviation to be bounded in expectation, uniformly over all support sizes at once, and then averaged. The Dodis–Ostrovsky–Reyzin–Smith average-min-entropy leftover hash lemma does not patch it either: there the side information must be independent of the hash key, and here the side information \(z\) may be \(H\) itself.
  2. A single universal constant over the whole parameter range, degenerate corners included. Textbook statements hide an \(O(1)\) in the exponents; the conjectures ask for one \(c\) valid for all \(K, D, R, \epsilon\).
  3. No query bound anywhere. Every random-oracle extraction result – compression arguments, presampling, bit-fixing, and the multi-source work in ePrint 2025/1258 – bounds the distinguisher’s query complexity. Here all three parties hold the entire function table, so there is no query budget to compress against. That paper in fact names statistical multi-source extraction against unbounded distinguishers as an open direction; these two conjectures are its seeded single-source instance. Imposing the budgets anyway is instructive, and is worked out in What the Leftover Hash Lemma Gives: the collision route turns out to be governed by how many rows of the table the source touches rather than by how many queries it makes, giving \(\tfrac12\sqrt{\epsilon R + 2R\,r_S/K}\) and closing that note’s open window to a factor of two; while the distinguisher’s budget cannot enter that route at all, since it passes through a statistical distance, which is by definition the supremum over all distinguishers. Pricing \(q_D\) means abandoning the lemma for an identical-until-bad argument on the single challenge cell, worth \(s_S/K + q_D\epsilon\), and that is the better of the two for every \(q_D \le \tfrac12\sqrt{R/\epsilon}\) — which is to say, for every query budget anyone would deploy. The unbounded distinguisher is not an incidental feature of these conjectures; it is what their second summand is about.

Read together: what looked like the hard feature of this problem – the source sees the whole oracle – is free, since the probabilistic-method union bound runs over flat sources before the source is fixed and so already covers supports chosen with \(H\) in hand. The genuinely new hypothesis is the unglamorous one in item 1.

Sources

Parameter lattice

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

single source \(k\)-source
public seed c/0004 – proven unstated
secret seed stated, untracked unstated

The one tracked cell is cited research. The single-source secret-seed cell is stated but no longer tracked: it was a page here until 28 August 2026, and the statement survives verbatim in the opening section of c/0004’s proof note, so the cell is filled as mathematics without being a statement of record. Neither \(k\)-source cell is stated at all. 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 – which is a different thing from the secret-seed cell, where the question is posed and simply not carried.

Statements in this hub

The secret-seed statement is no longer a page in this hub: withdrawn 17 August 2026 with no proof attempt recorded, removed from the site 28 August 2026. It is stated in full in the opening section of that page’s proof note.