Efficient Certifiable Randomness from a Single Quantum Device

04/24/2022
by   Urmila Mahadev, et al.
0

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 Ω(n) fresh bits of randomness in constant rounds, where n is a parameter of the protocol and the total communication is O(n), thus achieving a nearly optimal rate. The proof that the output is statistically random is conceptually simple and technically elementary.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset