Certified Randomness without Structure Against Shallow-Query Adversaries

AI summary

Overview

Research area: Quantum cryptography and quantum query complexity — specifically certified randomness (verifiable randomness generation) in the quantum random oracle model (QROM), building on the Yamakawa–Zhandry proof of quantumness.

Technical level: Advanced. The paper is a pure theory result; it assumes familiarity with quantum query algorithms, min-entropy, list-recoverable codes (folded Reed–Solomon), and the Aaronson–Ambainis conjecture.

Scope (one sentence): The paper proves, unconditionally, that the Yamakawa–Zhandry certifiable-randomness protocol yields genuine high min-entropy output against any computationally unbounded adversary that makes only o(log λ) adaptive layers of (arbitrarily wide) parallel quantum queries to the random oracle, removing the need for the unproven Aaronson–Ambainis conjecture in that regime.

What This Paper Is About

Yamakawa and Zhandry (J. ACM 2024) gave a proof of quantumness in the quantum random oracle model in which a quantum prover must output a codeword x ∈ C whose every symbol hashes to zero under a publicly computable random oracle H, and they conjectured that any successful prover must be sampling its answer from a high-entropy distribution — which would make the protocol a certifiable randomness protocol. They could only prove this conjecture by assuming the Aaronson–Ambainis conjecture, an unproven structural claim about quantum speedups. This paper removes that assumption for a restricted but meaningful class of adversaries: those limited to o(log λ) adaptive rounds of parallel quantum queries.

Key Contributions

1. Unconditional certifiable min-entropy for shallow-query adversaries. The authors prove that the Yamakawa–Zhandry protocol satisfies (D, h∞)-certifiable min-entropy for any query depth D(λ) = o(log λ) and any min-entropy bound h∞(λ) = o(λ^{c/2}), where c is a constant determined by the code parameters — with no appeal to the Aaronson–Ambainis conjecture or any other unproven assumption.

2. A "Heavy Query Lemma" (Lemma 4.1). Any adversary that outputs a correct codeword with non-negligible conditional probability must have assigned non-negligible query weight to all but a small fraction (the overview cites 1/100 as an example) of that codeword's symbols — i.e., a low-entropy adversary must have "checked" almost all of its answer before committing.

3. A "Hardness of Heavy Querying" lemma (Lemma 4.2). An adversary making o(log λ) query layers cannot concentrate such heavy query weight on the symbols of any correct codeword, because with so few adaptive rounds it must allocate its query weight before it has learned enough about the oracle.

4. A threshold-bootstrapping technique for adaptive query depth. The proof introduces a sequence of growing thresholds t_q = (2Qn/ℓ)^{4^{-q}} with the recurrence t_q ≥ Q/ℓ + 2Q√(Dn · t_{q−1}), which lets the authors find a "critical layer" at which oracle reprogramming perturbs the adversary's query weights by a controllable amount. This technique is explicitly identified as the bottleneck limiting the result to o(log λ) rounds.

Main Findings

• Main theorem (informal, Theorem 1.1): Any adversary making o(log λ) rounds of arbitrarily wide parallel queries that causes the verifier to accept with noticeable probability must be sampling its output from a distribution with Ω(λ^{c/2}) bits of min-entropy.

• Coverage relative to the honest algorithm: The honest Yamakawa–Zhandry algorithm uses just a single round of parallel queries, so the result covers all adversaries with sub-logarithmically many adaptive rounds beyond what the honest prover needs.

• Adversary strength: The proof holds against computationally unbounded adversaries, subject only to the query-depth constraint; query width per layer is polynomially bounded but otherwise unrestricted.

• Swapping lemma bound (Lemma 3.6): Reprogamming the oracle on a set X of inputs changes the adversary's state after j layers by at most ‖|ψ_j^H⟩ − |ψ_j^{H'}⟩‖₂ ≤ 2·√(j · Σ_{(i,x)∈X} w^{≤j}_{i,x}(H)), i.e., the change is controlled by the total query weight placed on the reprogrammed positions.

• Counting bound from Step 1: If s = ω(log λ) symbol positions of the answer receive small query weight, then the probability that a random oracle–output pair lies in the "good" set is at most 2^{−(s−1)}, which is negligible. The small-weight cutoff used is p²/(16Qn) for success probability p, total queries Q, and codeword length n.

• Counting bound from Step 2: Each bad oracle is consistent with at most L = 2^{Õ(λ^{c'})} good pairs, while each good pair generates at least 2^{⌊ζn⌋} bad oracles, giving |S|/|ℋ| ≤ 2^{Õ(λ^{c'})}/2^{Ω(λ)} = negl(λ) since c' < 1.

• Single-layer intuition: With one parallel query, query weights are oracle-independent because the state is fixed before the oracle is queried, so reprogramming on low-weight positions is "free" and the argument closes directly.

• Code parameters used: q = 2^{2⌊log λ⌋}, N = q − 1, m = 2^{⌊log λ⌋} + 1, n = N/m = 2^{⌊log λ⌋} − 1, k = α·N with α an arbitrary constant in (5/6, 1), Σ = 𝔽_q^m, and C a folded Reed–Solomon code; any two distinct codewords differ on at least (1−α)·n symbols.

• List-recovery parameters (Theorem 3.1, from [15] Lemma 4.2): 0 < c < c' < 1, ζ = Ω(1), ℓ = 2^{λ^c}, L = 2^{Õ(λ^{c'})}; for any lists S_1, …, S_n ⊂ Σ of size ≤ ℓ, at most L codewords agree with the lists on at least (1−ζ)n coordinates.

• Protocol details: The construction mirrors [15]'s protocol but queries H in parallel and searches for preimages of 0 rather than 1; the verifier parses π = x, checks x ∈ C and H_i(x_i) = 0 for all i ∈ [n], and outputs x or ⊥. Correctness follows from [15] Lemma 6.3. Complexity leveraging from [15] is deliberately omitted so the min-entropy properties of the basic protocol can be studied.

• Not reported: The paper contains no experiments, no benchmarks, no datasets, and no runtime or implementation measurements — it is a purely theoretical security proof.

Methodology in Plain English

The argument has two halves that are combined into a contradiction.

First half — a cheating prover must "check" its answer. If an adversary can output a specific valid codeword with non-negligible probability, then it must have spent a non-negligible amount of its quantum query "budget" on almost every symbol of that codeword. Formally, an adversary that succeeds with probability p but gives less than p²/(16Qn) query weight to at least s + 1 symbols of its answer is ruled out. The authors prove this by flipping the oracle's answer from 0 to 1 on subsets of those low-weight positions, producing at least 2^s "bad" oracles under which the output is wrong. The swapping lemma guarantees the adversary does not notice these flips (its output probability drops by at most a factor of two), because it barely queried those positions. Since bad sets generated by different good pairs are disjoint — the original oracle is recovered uniquely by flipping back — a counting argument gives that the good event has probability at most 2^{−(s−1)}, negligible for s = ω(log λ).

Second half — a shallow prover cannot do that checking. With only o(log λ) adaptive layers, the adversary must decide where to put its query weight before it knows which symbols hash to zero. The naive argument works for a single layer, where query weights are fixed in advance; with more layers, weights become oracle-dependent, so the authors instead look for the moment to reprogram. They define a growing sequence of thresholds and find the first layer at which at least (1−ζ)n symbols of the answer have accumulated weight above the current threshold (the "critical layer"). Just before that layer, at least ζn symbols still carry low weight, and those are the ones flipped. The threshold recurrence is chosen precisely so that the resulting perturbation, bounded by 2Q√(Dn · t_{q*−1}), is smaller than the margin the heavily-queried symbols have — so under the reprogrammed oracle the adversary still heavily queries x even though x is now incorrect.

Closing the loop. Fix any oracle. The adversary spreads at most Q = D·W total query weight, so for each coordinate the set of symbols receiving weight ≥ Q/ℓ has size at most ℓ, forming "short lists." List recoverability then says at most L = 2^{Õ(λ^{c'})} codewords are mostly consistent with those lists. Since each good pair spawns at least 2^{⌊ζn⌋} bad oracles and each bad oracle is claimed by at most L good pairs, the density of good pairs is at most 2^{Õ(λ^{c'})}/2^{Ω(λ)} = negl(λ). Combining the two halves gives a contradiction, so no shallow adversary can break the min-entropy guarantee.

The reason the technique stops at o(log λ) is that the threshold sequence grows doubly exponentially in the number of layers; beyond logarithmically many rounds the thresholds exceed the bounds the counting argument needs.

Why This Matters

Impact on research. The Yamakawa–Zhandry result was the leading candidate for non-interactive, publicly verifiable, efficiently checkable certified randomness from a single quantum device in the QROM, but its randomness guarantee rested on the Aaronson–Ambainis conjecture — a sweeping structural claim about all quantum speedups rather than a hardness assumption about a specific problem. This paper shows the guarantee can stand on its own against shallow-query adversaries, separating the protocol's soundness from that conjecture in a broad regime and supplying new query-weight and reprogramming machinery (a bootstrapping/threshold argument) that may be reusable for other QROM security proofs.

• Verifiable randomness beacons: a classical verifier could, in principle, check a single quantum device's output and treat acceptance as a certificate that the output was unpredictable.
• Randomness expansion and seeding: deriving fresh, certified unpredictable bits rather than trusting a hardware random number generator's manufacturer.
• Protocol design and parameter selection: the explicit codes, list-recovery parameters, and min-entropy bound Ω(λ^{c/2}) give concrete guidance for choosing code parameters if such a protocol were ever instantiated.
• Cryptographic key generation and lotteries/audits: settings where a party must prove its randomness was not chosen adversarially.

Industry relevance. Quantum computing vendors and national metrology/standards bodies interested in device-dependent certified randomness, and cryptographic engineering groups that need assumptions weaker than Bell-inequality violations but stronger than "trust the box." The result is a security proof, not an implementation, so its near-term industrial relevance is indirect: it tells protocol designers which adversarial models are actually ruled out.

Future Directions

• Extending beyond o(log λ) rounds. The authors state explicitly that extending the certifiable randomness guarantee to adversaries making ω(log λ) or polynomially many adaptive rounds remains an important open problem, and that for such adversaries the guarantee currently still relies on the Aaronson–Ambainis conjecture.
• Overcoming the doubly-exponential threshold barrier. The limitation is attributed directly to the threshold-bootstrapping technique; a fundamentally different way to control oracle-dependent query weights across many adaptive layers would be needed.
• Proving or refuting Aaronson–Ambainis, or finding an alternative structural route. The gap this paper leaves open is exactly the regime where the AA conjecture is still doing the work.
• Removing or better understanding the complexity leveraging omitted here. The authors deliberately drop the complexity leveraging used in [15] to study the min-entropy properties of the basic protocol, leaving open how the leveraged version behaves.

Target Audience

Quantum cryptography and quantum-complexity researchers, especially those working on the quantum random oracle model, proofs of quantumness, certified randomness, and query-complexity lower bounds. It is also relevant to theoreticians interested in the Aaronson–Ambainis conjecture and in coding theory applied to cryptography (list-recoverable and folded Reed–Solomon codes). Readers will need graduate-level familiarity with quantum query algorithms and min-entropy; the paper is not suitable as an introduction to the area.

Authors’ abstract

In a recent breakthrough, Yamakawa and Zhandry (J. ACM 2024) constructed a proof of quantumness in the quantum random oracle model (QROM) in which the quantum prover samples a codeword preimage of a publicly computable function H. They conjectured that given any H, a successful prover must sample their preimage from a high-entropy distribution over possible answers. If true, this would give a certifiable randomness protocol in the quantum random oracle model. As partial evidence for their conjecture, Yamakawa and Zhandry proved the security of their certifiable randomness protocol assuming the Aaronson-Ambainis conjecture. We prove the security of the certifiable randomness protocol of Yamakawa-Zhandry unconditionally, without relying on the unproven Aaronson-Ambainis conjecture, against low query-depth quantum adversaries: specifically, adversaries that make up to o(\log λ) adaptive quantum queries to the random oracle.