Certified Randomness with Optimal Rate

@misc{jain2026certified,
  title = {{Certified Randomness with Optimal Rate}},
  author = {Siddhartha Jain and Saachi Mutreja and Bhaskar Roberts},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.38945},
  eprint = {2609.38945},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38945},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Certified Randomness with Optimal Rate
AU  - Siddhartha Jain
AU  - Saachi Mutreja
AU  - Bhaskar Roberts
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.38945
UR  - https://arxiv.org/abs/2609.38945
AB  - 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.
ER  -