Efficient Certifiable Randomness from a Single Quantum Device
arXiv:2204.11353
Abstract
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 the Learning With Errors problem to address a key issue left open in previous work - the rate of generation of randomness. Our new protocol can certify fresh bits of randomness in constant rounds, where is a parameter of the protocol and the total communication is , thus achieving a nearly optimal rate. The proof that the output is statistically random is conceptually simple and technically elementary.