Efficient Certifiable Randomness
Brakerski et al. [BCM+18] introduced the model of cryptographic testing
of a single untrusted quantum device and gave a protocol for certifiable
randomness generation. We use the leakage resilience properties of
learning with errors to address two key issues left open in previous
work — the rate of generation of randomness, and the complexity of the
mathematical proof that the protocol does generate randomness. Our new
protocol can certify roughly n fresh bits of randomness in a single
round, thus achieving a nearly optimal rate. The proof that the output
is statistically random is conceptually simple and technically elementary.
Urmila Mahadev is an assistant professor in the Computing and
Mathematical Sciences department at the California Institute of
Technology. She received her Ph.D. from UC Berkeley in 2018, and spent
two years as a postdoctoral researcher at UC Berkeley, Microsoft
Research New England, and the Simons Institute for the Theory of
Computing. She is interested in quantum computation, complexity theory
and cryptography.