Quantum protocols from LWE
Gorjan Alagic
Abstract
I will give a high-level overview of several breakthrough results of last year, due to Mahadev and coauthors. These results give a number of interesting new protocols, solving several open problems in quantum computation. The protocols include verification of quantum computations, quantum fully-homomorphic encryption, and certified randomness expansion from a single device. The core technique involves post-quantum cryptography, specifically trapdoor claw-free functions (TCFs) which can be constructed from LWE. These TCFs are cleverly used as a classical "leash" to constrain the behavior of the quantum prover. I will describe what the various protocols achieve at a high level, and describe one of them in some detail.
This talk is organized by Aria