PIRSA Logo


PERIMETER INSTITUTE RECORDED SEMINAR ARCHIVE

PIRSA:20090023  ( MP4 Medium Res , MP3 , PDF ) Which Format?
Non-interactive zero-knowledge arguments for QMA, with preprocessing
Speaker(s): Andrea Coladangelo
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

 

Date: 30/09/2020 - 4:00 pm
Valid XHTML 1.0!