⚛️ quantum physics

Unconditional Certified Randomness without Structure

This paper presents a non-interactive, publicly verifiable protocol for unconditional certified randomness in the quantum random oracle model, achieving security against subexponentially-many adaptive quantum queries without relying on the Aaronson–Ambainis conjecture or restricting query depth.

Original authors: Andrea Coladangelo, Dakshita Khurana, Saachi Mutreja, Bhaskar Roberts, Joseph Slote, Avishay Tal

Published 2026-09-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrea Coladangelo, Dakshita Khurana, Saachi Mutreja, Bhaskar Roberts, Joseph Slote, 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

In the quantum world, randomness is not just a lack of information; it is a fundamental feature of reality. Even if you know everything possible about a quantum system, you still cannot predict the outcome of a measurement with certainty. This inherent unpredictability is the engine behind quantum computing, but it also presents a unique challenge for security. How can a person using a standard, classical computer be sure that a distant, untrusted quantum device is actually producing true randomness, rather than just faking it with a clever trick? This question lies at the heart of "certified randomness," a field where researchers try to build protocols that let a classical user verify the quality of quantum noise. For years, the most promising solutions relied on complex assumptions about the limits of computation or required the quantum device to be physically isolated from others, conditions that are difficult to enforce in the real world.

A team of researchers has now demonstrated a new way to certify randomness that removes these heavy constraints. They have designed a protocol that works in a theoretical setting known as the quantum random oracle model, a framework where a computer can query a massive, unpredictable database. Their breakthrough is a method that is non-interactive, meaning the quantum device simply produces an answer without needing to chat back and forth with the verifier, and it is publicly verifiable, allowing anyone to check the result. Most importantly, they proved that this protocol works unconditionally against any adversary, provided that adversary cannot make an impossibly large number of queries to the database. This result settles a long-standing question about whether true randomness can be certified without relying on unproven mathematical guesses, offering a robust foundation for future cryptographic systems.

The story of this discovery begins with a specific puzzle proposed by earlier researchers, which involved finding a hidden solution within a vast space of possibilities. Imagine a giant grid where every cell contains a secret code. A quantum computer can find a specific pattern in this grid much faster than a classical computer can, but the original version of this puzzle had a flaw: to prove the solution was truly random, the researchers had to assume a complex mathematical conjecture was true. This conjecture, while widely believed, had never been proven. The new work by Coladangelo, Khurana, and their colleagues shows that by slightly tweaking the rules of the puzzle, the need for this unproven assumption disappears entirely.

The researchers achieved this by changing two key ingredients of the original puzzle. First, they altered the "code" used to define the valid solutions. In the original setup, the code was rigid, but the team introduced a more flexible structure that could still be checked efficiently but was harder for an attacker to predict. Second, and perhaps more crucially, they changed the nature of the database itself. Instead of every entry in the database being equally likely to be a zero or a one, they made the database "biased." In this biased version, zeros are far more common than ones. This subtle shift turns out to be the key to the proof. It ensures that when a quantum computer solves the puzzle, it is forced to explore the database in a way that leaves a distinct, random signature, while simultaneously making it impossible for a classical computer to fake the result without an astronomical amount of effort.

The core of their argument relies on a clever counting technique. They reasoned that if a quantum computer were trying to produce a non-random, predictable answer, it would have to focus its attention on specific parts of the database. However, because of the way the database is biased and the code is structured, any attempt to focus on a specific answer would require the computer to make so many queries that it would exceed the limits of what is physically possible within the protocol's constraints. The researchers proved that if an adversary tries to output a predictable solution, they are forced to "query" the database so heavily that the protocol would detect the anomaly. Conversely, if the adversary stays within the allowed limits, the only way to succeed is to produce an output that is genuinely random.

This result is significant because it removes the last major hurdle for a specific type of quantum advantage. For some time, the only known examples of quantum computers outperforming classical ones in a "structure-less" environment—one that doesn't rely on special mathematical properties like factoring large numbers—were tied to unproven conjectures. By proving that randomness can be certified without these conjectures, the team has shown that this new source of quantum advantage is real and robust. Their protocol is also practical in its design: it requires only a single quantum device, involves no back-and-forth communication, and allows anyone with access to the database to verify the result.

The team's proof is rigorous and covers a wide range of potential attackers. They showed that even an adversary with unlimited computing power, who is only limited by the number of times they can ask questions to the database, cannot break the system. The security holds as long as the number of queries remains below a certain threshold, which is exponentially large but still finite. This means that for any realistic scenario, the randomness generated is guaranteed to be of high quality. The researchers also addressed a subtle technical issue: while their protocol was designed using a biased database, they demonstrated how to simulate this bias using a standard, uniform database, ensuring the method can be implemented in the real world without needing a special oracle.

In the broader landscape of quantum information, this work provides a clean, unconditional example of how quantum mechanics can be harnessed to generate and verify randomness. It bridges the gap between theoretical possibility and practical security, offering a protocol that is both simple to describe and mathematically airtight. By showing that the randomness is inherent to the process and not an artifact of an unproven assumption, the researchers have strengthened the foundation for future applications in cryptography and secure communication. The work stands as a testament to the power of careful mathematical reasoning, turning a complex theoretical problem into a clear, verifiable reality.

Technical Summary: Unconditional Certified Randomness without Structure

Problem Statement

The paper addresses the challenge of generating certified randomness in the Quantum Random Oracle Model (QROM). Specifically, it seeks a protocol that is:

Non-interactive: The quantum prover sends a single message to the verifier.
Publicly verifiable: Any party with access to the random oracle can verify the output.
Single-prover: It does not rely on non-communication assumptions between multiple devices.
Unconditionally secure: Security should not rely on unproven complexity-theoretic conjectures.

Prior work by Yamakawa and Zhandry (YZ) [YZ24] demonstrated a quantum advantage for an NP-search problem in the QROM, which implied a certified randomness protocol. However, their protocol relied on the Aaronson–Ambainis conjecture to guarantee that the quantum algorithm's output possessed high min-entropy. Without this conjecture, it was unclear if the output was truly random or if a classical adversary could predict it. Previous unconditional results (e.g., [KRT26]) were limited to adversaries making queries in very few adaptive layers ( $o(\log n)$ ), failing to cover general adaptive adversaries.

Methodology and Core Techniques

The authors propose a variant of the Yamakawa–Zhandry problem, termed the biased YZ problem, and prove it unconditionally certifies min-entropy against adversaries making up to $2^{o(n^c)}$ adaptive queries. The proof strategy relies on hybrid arguments and oracle reprogramming, utilizing three main technical innovations:

1. Query Norm and the Query-Norm Polytope

Instead of analyzing "query weight" (the probability of querying a specific input), the authors analyze the query norm (the square root of the query weight). They define a geometric structure called the query-norm polytope, which represents the linear constraints on how query norms can change when an oracle is reprogrammed.

Local Stability: They establish that if an oracle is reprogrammed on inputs with small query norms, the query norms on other inputs change only slightly.
Heavy-Coordinate Reprogramming: A key lemma (Lemma 4.3) shows that even if an adversary heavily queries a large set of coordinates ( $M$ ), there exist exponentially many ways to reprogram the oracle on a subset of $M$ such that the adversary still places significant query norm on a smaller, but still substantial, subset of $M$ (specifically $\Omega(\sqrt{n})$ coordinates). This overcomes the difficulty of reprogramming "heavy" coordinates where the adversary might detect changes.

2. Modified Error-Correcting Codes

The original YZ construction used a code with specific list-recovery properties that were insufficient for the new reprogramming bounds (which only preserved $\Omega(\sqrt{n})$ known symbols rather than a linear number).

The authors construct a family of Folded Reed–Solomon (FRS) codes with a lower rate ( $R \approx 1/\sqrt{n}$ ).
These codes are $(\zeta, \ell, L)$ -list recoverable, meaning that if a codeword agrees with short lists on a vanishing fraction ( $\approx 1/\sqrt{n}$ ) of coordinates, the number of such codewords is small. This matches the $\Omega(\sqrt{n})$ surviving heavy coordinates guaranteed by the polytope argument.

3. Biased Random Oracle

To maintain the completeness of the protocol (ensuring the honest quantum prover succeeds) with the new low-rate code, the authors introduce a biased random oracle.

The oracle $H$ outputs 1 with a small probability $p \approx 1/\sqrt{n}$ and 0 with probability $1-p$ .
This bias ensures that the "error" vector in the dual basis (after Fourier transform) has a Hamming weight of $O(\sqrt{n})$ with high probability. This falls within the unique-decoding radius of the dual code $C^\perp$ , allowing the honest prover to successfully decode and output a valid solution.
The paper demonstrates that this biased oracle can be efficiently simulated in the standard QROM using a uniform random oracle.

Key Contributions and Results

The paper presents a Certifiable Min-Entropy Protocol with the following guarantees (Theorem 1.1):

Unconditional Security: The protocol is secure against any adversary making at most $2^{o(n^c)}$ adaptive quantum queries, for any constant $c \in (0, 1/2)$ . This removes the need for the Aaronson–Ambainis conjecture.
Min-Entropy Guarantee: If an adversary causes the verifier to accept with noticeable probability, the output distribution has min-entropy at least $\Omega(n^c)$ .
Protocol Properties:
- Non-interactive: The prover outputs a candidate solution $x$ .
- Publicly Verifiable: The verifier checks if $x \in C$ and $H_i(x_i) = 0$ for all $i$ .
- Single-Prover: No communication assumptions between devices are required.

The proof proceeds by contradiction:

Claim A (Low-entropy implies heavy queries): If an adversary outputs a specific correct answer with high probability (low entropy), it must have heavily queried most symbols of that answer.
Claim B (Query-bounded cannot heavily query): Using the heavy-coordinate reprogramming lemma and the list-recovery property of the modified code, the authors show that for almost all oracles, no correct answer can be heavily queried by an adversary with the given query bound.
Conclusion: These two claims are incompatible, implying that an adversary cannot output a low-entropy distribution with noticeable probability.

Significance and Claims

The paper claims to provide the first unconditional certified randomness protocol in the QROM that is non-interactive, publicly verifiable, and secure against general adaptive adversaries (up to subexponential query bounds).

Structural Insight: The authors highlight that the Yamakawa–Zhandry problem is a "structure-less" source of quantum advantage. By proving the inherent randomness of its solution without relying on conjectures, the work provides evidence for the veracity of the Aaronson–Ambainis conjecture (as the result implies a consequence of that conjecture holds unconditionally for this variant).
Technical Advancement: The work introduces the query-norm polytope framework, which offers a new geometric perspective on reprogramming arguments. This framework allows for tighter bounds on how query distributions change under oracle modifications, specifically handling "heavy" coordinates that were previously intractable in unconditional proofs.
Limitations and Open Questions: The authors note that their result applies to a variant of the YZ problem (biased oracle, modified code). They explicitly pose an open question (Question 1) regarding whether the heavy-coordinate reprogramming lemma can be improved to preserve a linear number of heavy inputs, which would potentially allow the use of the original YZ code and oracle without bias. They also acknowledge that their proof currently requires the adversary's query bound to be subexponential ( $2^{o(n^c)}$ ), leaving the fully polynomial-query case as an open area for future research.

The paper does not propose experimental implementations or specific real-world applications beyond the theoretical construction of the protocol. Its primary contribution is a theoretical breakthrough in the foundations of quantum randomness certification.