Zero-knowledge proof systems for QMA

Zero-knowledge (ZK) proof systems are fundamental in modern cryptography. Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks.

In this talk, I will present our recent work that further generalizes these results in a quantum setting. We show that every problem in QMA admits a zero-knowledge proof system under a mild intractable assumption. Our QMA proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration. I'll describe the main tools we develop to build the ZK proof systems: 1) a new variant of the QMA-complete local Hamiltonian problem in which the local terms are described by Clifford operations and standard basis measurements; and 2) a new quantum encoding scheme that provides authentication and transversal Clifford operations. 

Joint work with Anne Broadbent, Zhengfeng Ji, and John Watrous. https://arxiv.org/abs/1604.02804