How do you know the coin isn't rigged?
A coin flip is only fair if no one controls it. Quantum random number generators are marketed as "God's own dice" — but all you see is a black box that blinks and spits out a string of 0s and 1s. Why believe it's genuinely random?
This question has a formal name: certified randomness — getting an untrusted quantum machine to produce random numbers while letting a classical verifier *confirm* they truly are random. We recently covered the industry-side effort to standardize verification of quantum randomness. Now the theory side has filled in the hardest piece: on August 31, arXiv:2608.31112 appeared, titled *Unconditional Certified Randomness without Structure* — certified randomness with no structural assumptions and no security assumptions. The six authors are spread across the University of Washington, UIUC, Columbia, Berkeley, and NTT.
A twenty-year detour
Why is the word "unconditional" valuable? Just look at how prior work had to route around it.
- Bell-inequality route: Colbeck's 2006 PhD thesis started the device-independent program; Pironio et al. (Nature 2010) certified dice via Bell's theorem; Vazirani–Vidick (2012) gave certifiable quantum dice. Cost: multiple entangled devices watching each other.
- Single-device route: BCM+21 (2021) relied on the LWE assumption, required multiple rounds of interaction, and was only privately verifiable. Aaronson–Hung (STOC 2023) depended on a non-standard complexity assumption. Yamakawa–Zhandry (JACM 2024) was the most elegant — a single device, zero interaction, publicly verifiable by anyone — but its randomness guarantee rested on the Aaronson–Ambainis conjecture, posed in 2009 (arXiv:0911.0996). Per the paper: "widely believed true, yet resistant to proof despite sustained effort" — attempts from Montanaro 2012 through Bhattacharya 2025 all failed.
- KRT26 (FOCS 2026) removed the AA conjecture but only handled shallow adversaries making o(log n)-depth queries.
- Paper: https://arxiv.org/abs/2608.31112
- Yamakawa–Zhandry (JACM 2024): https://arxiv.org/abs/2204.02063
- Aaronson–Ambainis conjecture original: https://arxiv.org/abs/0911.0996
The new paper refunds that deposit: it proves security unconditionally for a slightly modified (biased) variant of the Yamakawa–Zhandry problem — and, as a byproduct, adds evidence for the AA conjecture itself (one of its important corollaries now holds).
What the protocol looks like
No commitment phase, no interaction, no trapdoor. A quantum machine computes once and outputs a classical string x. Anyone can verify with two classical checks: whether x lies in a public error-correcting code C, and whether every coordinate satisfies a simple condition against a public (biased) random oracle H. If both checks pass, x itself is the certified random string.
The security bound is worth quoting: against an adversary making 2^o(n^c) adaptive quantum queries — with otherwise unlimited computing power — the output still retains Ω(n^c) min-entropy. Compared to KRT26, which only handles shallow queries, the authors call this a "doubly exponential improvement."
And the obvious first objection — isn't the randomness just hiding inside the oracle? The paper handles this explicitly: entropy is computed conditioned on the oracle values, proving the protocol delivers randomness *beyond* the oracle.
Anecdotes and cold water
Section 8 contains a charmingly candid AI disclosure: "ChatGPT 5.6 was used to refine the parameter choices for the FRS code family. All other technical aspects of this work were generated by humans." Quantum cryptographers using a large model to tune parameters — and AI brainstorming even produced "counterexamples to stronger conjectures," keeping their own open problems safe.
Now the cold water. This is a 62 KB theory paper: no conference stamp, no code. The result only covers a biased variant of the YZ problem (a biased oracle with p = 1/Θ(√n)); the entropy guarantee is Ω(n^c) with c < 1/2, still far from n uniform bits. We also searched the full text: the words *beacon*, *blockchain*, *lottery*, and *NIST* appear nowhere. The paper handles only the math; applications like randomness beacons and auditable lotteries are the reader's imagination, not the authors' claims.
Still, the significance for the quantum and crypto community is real: with an infrastructure-grade, publicly verifiable randomness protocol built on unconditional security, the entire application chain from randomness beacons to audit lotteries now has a foundation that depends on no unproven conjecture. When hardware can run it, and at what cost, is a question for the next decade.
Sources