PIRSA:20090023

Non-interactive zero-knowledge arguments for QMA, with preprocessing

Coladangelo, A. (2020). Non-interactive zero-knowledge arguments for QMA, with preprocessing. Perimeter Institute. https://pirsa.org/20090023

Coladangelo, Andrea. Non-interactive zero-knowledge arguments for QMA, with preprocessing. Perimeter Institute, Sep. 30, 2020, https://pirsa.org/20090023 

          @misc{ pirsa_PIRSA:20090023,
            doi = {10.48660/20090023},
            url = {https://pirsa.org/20090023},
            author = {Coladangelo, Andrea},
            keywords = {Quantum Information},
            language = {en},
            title = {Non-interactive zero-knowledge arguments for QMA, with preprocessing},
            publisher = {Perimeter Institute},
            year = {2020},
            month = {sep},
            note = {PIRSA:20090023 see, \url{https://pirsa.org}}
          }

Andrea Coladangelo

University of California, Berkeley

Talk number
PIRSA:20090023
Collection
Talk Type
Subject
Abstract

Zero-knowledge proofs are one of the cornerstones of modern cryptography. It is well known that any language in NP admits a zero-knowledge proof. In the quantum setting, it is possible to go beyond NP. Zero-knowledge proofs for QMA have first been studied in a work of Broadbent et al (FOCS'16). There, the authors show that any language in QMA has an (interactive) zero-knowledge proof. In this talk, I will describe an idea, based on quantum teleportation, to remove interaction at the cost of adding an instance-independent preprocessing step. Assuming the Learning With Errors problem is hard for quantum computers, the resulting protocol is a non-interactive zero-knowledge argument for QMA, with a preprocessing step that consists of (i) the generation of a Common Reference String and (ii) a single (instance-independent) quantum message from the verifier to the prover.

This is joint work with Thomas Vidick and Tina Zhang