In a previous talk we saw that Brakerski et al. [1] used the hardness of the Learning with Errors (LWE) problem to not only construct an interactive Proof of Quantumness but also certifiably generate a random bit.
For this talk, I will review Mahdadev et al. [2] — an improvement on the former that generates Ω(n) random bits using only O(n) bits of communication. My main goal is to walk through why they first design for a quantum verifier and how they eliminate that dependency. After explaining their intuition, I will dive deeper and prove leakage resilience using a smaller instance of the LWE problem.
References:
[1] Brakerski, Z., Christiano, P., Mahadev, U., Vazirani, U., & Vidick, T. (2018). A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. https://doi.org/10.48550/arXiv.1804.00640
[2] Mahadev, U., Vazirani, U., & Vidick, T. (2022). Efficient Certifiable Randomness from a Single Quantum Device. https://doi.org/10.48550/arXiv.2204.11353
