Zero-Knowledge Proof Systems for QMA

Publication Type:
Conference Proceeding
Citation:
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2016, 2016-December pp. 31 - 40
Issue Date:
2016-12-14
Metrics:
Full metadata record
Files in This Item:
Filename Description Size
OCC-126074_AM.pdfAccepted Manuscript version331.33 kB
Adobe PDF
© 2016 IEEE. 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. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-knowledge proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive proof system that is zero-knowledge with respect to efficient quantum computations. 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.
Please use this identifier to cite or link to this item: