RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

Zero-knowledge proof systems for QMA

October 12, 2016 - 11:00am
Speaker: 
Fang Song
Institution: 
Portland State University

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. Link here.

CSS 3100A