Certified Randomness without Structure Against Shallow-Query Adversaries
2026-08-25 • Cryptography and Security
Cryptography and Security
AI summaryⓘ
Yamakawa and Zhandry designed a way to prove that a quantum computer can generate randomness by sampling certain outputs from a public function. They guessed that any successful quantum prover must pick these outputs from a very unpredictable set, which would confirm the presence of true randomness. Previously, their proof depended on an unproven assumption called the Aaronson-Ambainis conjecture. The authors of this work showed that the system is secure even without relying on that assumption, but only against quantum adversaries that make a limited number of queries.
quantum random oracle modelproof of quantumnesscertifiable randomnessquantum proverAaronson-Ambainis conjecturequantum query complexityadaptive quantum querieshigh-entropy distributionrandom oracle
Authors
Dakshita Khurana, Bhaskar Roberts, Avishay Tal
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.