In a previous talk we saw that Brakerski et al.  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.  — 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.
 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
 Mahadev, U., Vazirani, U., & Vidick, T. (2022). Efficient Certifiable Randomness from a Single Quantum Device. https://doi.org/10.48550/arXiv.2204.11353