How Do You Know the Coin Isn't Rigged?
A fair coin flip requires that no one can control it. Quantum random number generators are marketed as "God's own dice"—but all you see is a black box whose lights blink and output a string of 0s and 1s. Why believe it's truly random?
This question has a formal name: certified randomness—getting an untrusted quantum device to produce random numbers while a classical verifier *checks* that they really are random. Following the industry-side standardization efforts discussed earlier on this forum, the theory side has now supplied the hardest missing piece: arXiv:2608.31112, *"Unconditional Certified Randomness without Structure"*—certified randomness with no structural assumptions. The six authors are affiliated with UW, UIUC, Columbia, Berkeley, and NTT.
A Twenty-Year History of Detours
Why is "unconditional" valuable? Look at how predecessors had to make compromises:
- Bell-inequality route: Colbeck's 2006 PhD thesis launched the device-independent program; Pironio et al. (Nature, 2010) certified dice via Bell's theorem; Vazirani–Vidick (2012) gave certifiable quantum dice. But this route requires multiple entangled devices watching each other.
- Single-device route: BCM+21 (2021) relied on the LWE assumption, multi-round interaction, and private verifiability only. Aaronson–Hung (STOC 2023) rested on a non-standard complexity assumption. Yamakawa–Zhandry (JACM 2024) was the most elegant—single device, zero interaction, public verification—but its randomness guarantee hinged on the Aaronson–Ambainis conjecture (arXiv:0911.0996), a 2009 conjecture "widely believed true but resistant to proof" despite sustained attempts from Montanaro (2012) through Bhattacharya (2025). KRT26 (FOCS 2026) removed the AA conjecture but only against adversaries making shallow queries.
- This paper (Aug 31, 2026): unconditional security against fully adaptive adversaries.
- Paper: https://arxiv.org/abs/2608.31112
- Yamakawa–Zhandry (JACM 2024): https://arxiv.org/abs/2204.02063
- Aaronson–Ambainis conjecture: https://arxiv.org/abs/0911.0996
The new work refunds that wager: for a slightly modified YZ problem, it proves security unconditionally—and as a byproduct adds evidence for the AA conjecture itself (one of its important corollaries holds).
What the Protocol Looks Like
No commitment phase, no interaction, no trapdoor. A quantum machine runs once and outputs a classical string x. Anyone can verify with two classical checks: x must lie in a public error-correcting code C, and each coordinate must satisfy a simple condition on a public random oracle H. If both checks pass, x itself is the certified random string.
On the security magnitude, quoting the paper: against adversaries making 2^o(n^c) adaptive quantum queries—with unlimited computational power—the output retains Ω(n^c) min-entropy. Compared to KRT26, which only handles o(log n)-depth queries, the authors call this a "double-exponential improvement."
And the obvious first question—could the randomness just be hidden in the oracle?—is explicitly addressed: verification conditions on the oracle's values when computing entropy; the proof shows the protocol supplies randomness *beyond* the oracle.
Trivia and Cold Water
Section 8 contains a refreshingly candid AI disclosure: "ChatGPT 5.6 was used to refine the parameter choices of the FRS code family. All other technical aspects of this work were human-generated." The AI brainstorming also produced "counterexamples to stronger conjectures," keeping the authors' own open questions intact.
The caveats deserve full weight. This is a 62 KB theory paper: no conference stamp, no code. The result covers only a biased variant of the YZ problem (biased oracle with p = 1/Θ(√n)); the entropy guarantee is Ω(n^c) with c < 1/2, still short of n uniformly random bits. A full-text search for "beacon," "blockchain," "lottery," and "NIST" returns nothing—the paper is pure math; applications like randomness beacons and draws are the reader's imagination, not the authors' claim.
Still, the significance for the quantum and cryptography community is real: once a publicly verifiable randomness source has an infrastructure-grade protocol with unconditional security, the entire application chain—from randomness beacons to auditable sampling—rests on concrete that depends on no unproven conjectures. When hardware can run it, and at what cost, is a question for the next decade.
Sources