Henry Yuen: Perfect zero knowledge for quantum multiprover interactive proofs

Abstract: In a seminal 1988 paper, Ben-Or, Goldwasser, Kilian, and Wigderson (BGKW) introduced the model of multiprover interactive proofs (MIPs), and furthermore showed that zero knowledge can always be attained in this model without computational assumptions. Their paper has been enormously influential across cryptography and complexity theory, inspiring much research into zero knowledge, interactive proofs, PCPs, delegated computation, and more. 

 

In 2004, Cleve, Hoyer, Toner, and Watrous introduced the model of quantum multiprover interactive proofs (QMIPs), which are MIPs where the provers are allowed to share quantum entanglement (but still cannot communicate). The study of QMIPs has similarly been extremely fruitful in both quantum complexity theory and quantum cryptography. In this work, we prove the quantum analogue of BGKW's result: we show every quantum multiprover interactive proof can be transformed into an equivalent protocol that has the zero knowledge property. Since recent work has shown that QMIPs are capable of deciding extremely complex languages (such as nondeterministic *doubly-exponential* time), our result implies that such languages also have (quantum) zero knowledge proofs. 

 

The main techniques used in this paper is a procedure to compress quantum interactive protocols, and quantum error correcting codes. I will keep this talk self-contained and accessible; in particular I will not assume any background in quantum information.