arXiv:2609.38945
Certified Randomness with Optimal Rate
Siddhartha Jain, Saachi Mutreja, Bhaskar Roberts
Abstract
The generation of certified random bits is an emerging near-term application of quantum computers. Potential applications, such as randomness beacons and CRS generation, require nearly uniform randomness, whose rate (the ratio of min-entropy to bitlength) is ~ 1. However, existing protocols for certified randomness either produce weakly random strings with rate o(1), or they require a trusted random seed. We show how to certify randomness with the optimal rate ~ 1 without requiring any trusted randomness from the verifier. Our protocol is secure unconditionally in the quantum random oracle model (QROM). This improves the result of Coladangelo et al., who certified weakly random strings unconditionally in the QROM, and answers a question posed by Aaronson and Hung. We also define and construct a proof of conditional min-entropy, which certifies optimal min-entropy even conditioned on an adversarially chosen transcript. We show an application of this primitive to randomness beacons, where each pulse should have high min-entropy conditioned on all previous messages.
AI Summary
The paper asks how much randomness a deterministic classical verifier can certify from a single untrusted quantum prover without a trusted random seed. It works in the quantum random oracle model (QROM), with non-interactive, publicly verifiable proofs and polynomial-query adversaries, including adversaries with unbounded computation. The construction certifies an $n$-bit output with average conditional min-entropy greater than $n-\gamma(\lambda)$ for every $\gamma(\lambda)=\omega(\log\lambda)$, where $n=\omega(\log\lambda)$. The guarantee holds conditioned on an adversarially chosen classical label and the fixed random oracles: except for a negligible fraction of oracles, any prover accepted with inverse-polynomial probability produces accepted outputs satisfying this entropy bound. Polynomial-time rejection sampling can fix $O(\log\lambda)$ output bits, providing the corresponding obstruction to stronger universal guarantees. The protocol starts from an existing QROM proof of min-entropy, strengthens its soundness analysis, and hashes the verified source together with its label through a separate, domain-separated random oracle. The proof establishes quantum-secure seedless condensation using heavy/light query decompositions, oracle reprogramming, and concentration bounds. A block measure-and-reprogram argument handles labels selected after adaptive quantum oracle queries. An application binds successive randomness-beacon pulses to their preceding public history. The output is not guaranteed uniform, and the result is unconditional only within the QROM; replacing the oracle with a concrete hash function is heuristic. The beacon construction provides neither liveness nor an entropy guarantee when acceptance is overwhelmingly unlikely.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.