⚛️ quantum physics

Certified Randomness without Structure Against Shallow-Query Adversaries

This paper unconditionally proves the security of the Yamakawa-Zhandry certifiable randomness protocol against shallow-query quantum adversaries, thereby establishing certified randomness without relying on the unproven Aaronson-Ambainis conjecture.

Original authors: Dakshita Khurana, Bhaskar Roberts, Avishay Tal

Published 2026-08-26

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Dakshita Khurana, Bhaskar Roberts, Avishay Tal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Randomness is the hidden engine of modern security, the unpredictable spark that keeps digital locks from being picked and secrets from being stolen. In the classical world, true randomness is a luxury; computers are deterministic machines that follow strict rules, meaning any number they generate is, in principle, predictable if you know the starting point. Quantum mechanics offers a different path. Because the act of measuring a quantum system is inherently probabilistic, a quantum device can produce outputs that are fundamentally unpredictable, even to an observer with perfect knowledge of the device's setup. But this creates a trust problem: how can a classical observer, who cannot see the quantum state, be sure the device is actually using this quantum randomness and not just pretending to? The observer needs a way to certify that the output is genuinely random, not a pre-determined answer disguised as chance.

For years, researchers have tried to solve this by relying on complex mathematical assumptions about how hard certain problems are to solve, or by demanding that quantum devices be physically separated to prevent them from simulating the expected behavior. A recent breakthrough by Yamakawa and Zhandry offered a new approach using a "random oracle," a theoretical tool that acts like a perfectly random black box. They designed a protocol where a quantum prover must find a specific pattern hidden within this black box. They showed that a quantum computer could do this easily, while a classical computer could not. Crucially, they suspected that any quantum computer that succeeds in this task must be producing a truly random output, rather than a lucky guess. However, their proof that the output was random relied on a deep, unproven hypothesis about the structure of quantum speedups. If that hypothesis were wrong, the guarantee of randomness would vanish.

A new paper by Dakshita Khurana, Bhaskar Roberts, and Avishay Tal removes that uncertainty for a specific class of attackers. The authors prove that the Yamakawa-Zhandry protocol guarantees certifiable randomness without needing any unproven assumptions, provided the attacker is limited in how many times they can ask the black box for information in a sequence. Specifically, they show that if an adversary can only make a very small number of sequential rounds of questions—roughly the logarithm of the security parameter—they cannot trick the system. Even if the adversary is infinitely powerful in terms of computing speed, they cannot force the system to output a predictable answer if they are restricted to this shallow depth of interaction.

The researchers achieved this by analyzing how an adversary interacts with the random oracle. They introduced the concept of "query weight," which measures how much attention the adversary pays to specific parts of the black box. They demonstrated that for an adversary to output a correct answer with high probability, they must have concentrated a significant amount of this attention on almost every part of the answer they eventually give. In other words, they cannot just guess; they must have checked the answer thoroughly. The authors then proved that an adversary with only a few sequential rounds of questions simply cannot gather enough attention on a specific correct answer to make this happen. The limited number of rounds forces the adversary to spread their attention too thin to ever lock onto a single, predictable solution.

This result is significant because it establishes the security of the protocol from first principles, rather than leaning on a broad conjecture about how quantum computers work. The authors show that the randomness is not an accident of their specific algorithm but a necessary feature of the problem itself, as long as the attacker is not allowed to ask too many questions in a row. While their proof currently applies to adversaries with a very limited number of sequential rounds, it provides a solid, unconditional foundation for certifiable randomness in the quantum random oracle model. It confirms that for these restricted attackers, the quantum prover is genuinely rolling the dice, and the classical verifier can trust the result.

Technical Summary: Certified Randomness without Structure Against Shallow-Query Adversaries

Problem Statement
The paper addresses the challenge of generating certifiable randomness in the Quantum Random Oracle Model (QROM). While quantum mechanics offers inherent probabilism, a classical verifier must be able to trust that a quantum prover is genuinely exploiting this randomness rather than outputting a biased or pre-determined answer.

A recent protocol by Yamakawa and Zhandry (YZ24) proposed a proof of quantumness where a prover finds a codeword $\mathbf{x}$ from a list-recoverable code $C$ such that $H_i(x_i) = 0$ for all coordinates $i$ , where $H$ is a random oracle. A key feature of the honest YZ algorithm is that its output is inherently random (a uniform sample from valid codewords). YZ conjectured that any successful prover must sample from a high-entropy distribution, thereby transforming the protocol into a source of certifiable randomness.

Previously, YZ proved this conjecture only under the Aaronson-Ambainis (AA) conjecture, a structural hypothesis asserting that quantum speedups require underlying structure in the input domain. The AA conjecture remains unproven in general. The authors ask: Can the certifiable randomness guarantee of the YZ protocol be established unconditionally, without relying on the AA conjecture?

Methodology and Technical Approach
The authors provide an unconditional security proof against a specific class of adversaries: those making at most $o(\log \lambda)$ adaptive query rounds to the random oracle (though they may make polynomially many parallel queries within each round). The proof strategy relies on a "query weight" analysis and a counting argument involving oracle reprogramming.

Query Weight and the Swapping Lemma:
The central analytic tool is query weight, defined as the cumulative probability that a quantum adversary's query register measures a specific symbol $(i, x_i)$ across query layers. The authors utilize the Swapping Lemma, which bounds the change in an adversary's quantum state when the oracle is reprogrammed on a set of inputs, as a function of the total query weight on those inputs. If an adversary gives small weight to a set of inputs, reprogramming those inputs barely affects the adversary's output distribution.
Step 1: Low-Entropy Adversaries Must "Heavily Query" Their Answer:
The authors prove that if an adversary outputs a correct codeword $\mathbf{x}$ with high probability, it must allocate non-negligible query weight to almost all symbols of $\mathbf{x}$ .
- Argument: If an adversary outputs $\mathbf{x}$ with high probability but gives small weight to many of its symbols, one can construct a set of "bad" oracles by flipping the hash values of those low-weight symbols from 0 to 1. By the Swapping Lemma, the adversary's behavior remains largely unchanged on these bad oracles, meaning it would still output $\mathbf{x}$ even though $\mathbf{x}$ is no longer a valid solution. A counting argument shows that the number of such "bad" oracles vastly outnumbers the "good" ones, leading to a contradiction unless the adversary heavily queries the answer.
Step 2: Low-Depth Adversaries Cannot Heavily Query a Correct Answer:
The core contribution is showing that an adversary with limited adaptive depth ( $D = o(\log \lambda)$ ) cannot concentrate sufficient query weight on a specific correct codeword before learning enough about the oracle.
- Bootstrapping Argument: Unlike the single-query case where weights are fixed, adaptive queries allow weights to depend on previous oracle responses. The authors introduce a sequence of growing thresholds $t_0 < t_1 < \dots < t_D$ . They identify a critical layer $q^*$ where the adversary first accumulates substantial weight on $(1-\zeta)n$ symbols of a codeword.
- Reprogramming Strategy: Just before layer $q^*$ , the adversary has not yet reached the threshold on at least $\zeta n$ symbols. The authors reprogram these low-weight symbols. Using the recurrence relation of the thresholds, they show that the perturbation caused by reprogramming is small enough that the adversary still "heavily queries" the codeword under the new oracle, even though the codeword is now invalid.
- Counting: By combining the list-recoverability of the code (which limits the number of codewords consistent with any set of lists) with the disjointness of the bad oracle sets generated by different good pairs, they show that the probability of an adversary successfully heavily querying a correct codeword is negligible.

Key Contributions and Results

Unconditional Security: The paper proves the certifiable min-entropy property of the Yamakawa-Zhandry protocol unconditionally, removing the reliance on the unproven Aaronson-Ambainis conjecture.
Theorem 1.1 (Informal): The protocol satisfies $(D, h_\infty)$ -certifiable min-entropy for any query depth $D(\lambda) = o(\log \lambda)$ and min-entropy bound $h_\infty(\lambda) = o(\lambda^{c/2})$ . This means any adversary making $o(\log \lambda)$ rounds of adaptive queries that causes the verifier to accept with noticeable probability must be sampling from a distribution with $\Omega(\lambda^{c/2})$ bits of min-entropy.
Technical Limitation: The proof is currently limited to $o(\log \lambda)$ adaptive rounds. The authors note that their threshold bootstrapping technique requires thresholds that grow doubly exponentially with the number of rounds; beyond $O(\log \lambda)$ , the thresholds exceed the bounds necessary for the counting argument.

Significance
The paper establishes that the randomness of the Yamakawa-Zhandry protocol is not merely an artifact of their specific algorithm but a necessary feature of any successful strategy against shallow-query adversaries. This provides a stronger foundation for certified randomness in the QROM, relying only on the hardness of the underlying search problem and the structural properties of list-recoverable codes, rather than broad, unproven conjectures about the nature of quantum speedups. The work narrows the gap between what is known about quantum query complexity and the security of practical cryptographic protocols, specifically for adversaries with limited adaptive depth.

More like this