Quantum protocol generates fully certified random bits without trusted seeds
Certified Randomness with Optimal Rate
Cryptography and Security
Summary
Certified randomness is important for secure cryptography and various applications, but existing methods either produce weak random output or require a trusted starting point. The authors present a new quantum-based protocol that can create nearly perfect random bits without needing any trusted initial randomness. Their method is proven secure using a strong theoretical model that accounts for quantum attackers. Additionally, they introduce a way to verify randomness even when an adversary tries to influence the output history, useful for applications like randomness beacons ensuring fresh, unbiased pulses.
What this means in practice
- •For cryptography engineers: Create random number generators that produce near-perfect random bits without needing a trusted seed for secure cryptographic protocols.
- •For blockchain developers: Build randomness beacons with guaranteed fresh randomness at each pulse despite potential adversarial attempts to learn the history.
Authors
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.