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.