Presampling for sources that read the oracle independently

Does a random oracle decompose into bit-fixing mixtures when the advice is produced by two parties who never communicate?

Presampling is the standard route to non-uniform security in idealized models. A random oracle together with \(S\) bits of oracle-dependent advice is close to a mixture of oracles fixed on \(P\) points and uniform elsewhere, at a cost of roughly \(ST/P\) against \(T\)-query adversaries. The technique assumes one preprocessing stage, and it is not known how to run it when the advice comes from several parties who read the oracle independently.

That is the setting of multi-source randomness extraction in the random-oracle model, and the reason to want a decomposition route is concrete: the compression argument that gets the bounds instead stalls for non-monolithic constructions such as Merkle-Damgård and sponge.

The lattice

The open cell is the observer’s query budget. Everything else in the statement is fixed by the setting.

Query budget \(q\) Status
\(q = 0\) Proved, and tight.
\(q = 1\) Proved, under an extra hypothesis.
\(q \geq 2\) Open.

Two features of the statement are load-bearing rather than incidental, and a proposed proof that does not use them is wrong.

  • Two sources, not one. The conjecture is false with a single source, and the counterexample is explicit: a source that queries \(H\) at its own output point and leaks one bit of the answer defeats every admissible family. So a proof cannot draw its use of independence solely from a bound on the probability that the fixed set contains the challenge, because such bounds hold for one source too.
  • The quantifier order. The family is chosen after \(P\) and \(\gamma\) but before \(q\), so no part of it may be tuned to the observer’s budget. Relaxing this makes the statement easier in a way the intended applications cannot use.

Why it is worth stating separately

A decomposition would give extraction bounds for split unpredictable sources as a corollary, of the shape \(\kappa(q) = O(\sqrt{\sigma' q^{+} \delta})\), without going through compression. The conditional theorem is proved: what is missing is its hypothesis.

Sources