首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:Perfect zero knowledge for quantum multiprover interactive proofs
  • 本地全文:下载
  • 作者:Alex Bredariol Grilo ; William Slofstra ; Henry Yuen
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-52
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this work we consider the interplay between multiprover interactive proofs, quantum entanglement, and zero knowledge proofs — notions that are central pillars of complexity theory, quantum information and cryptography. In particular, we study the relationship between the complexity class MIP , the set of languages decidable by multiprover interactive proofs with quantumly entangled provers, and the class PZK-MIP , which is the set of languages decidable by MIP protocols that furthermore possess the perfect zero knowledge property.Our main result is that the two classes are equal, i.e., MIP = PZK-MIP . This result provides a quantum analogue of the celebrated result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC 1988) who show that MIP = PZK-MIP (in other words, all classical multiprover interactive protocols can be made zero knowledge). We prove our result by showing that every MIP protocol can be efficiently transformed into an equivalent zero knowledge MIP protocol in a manner that preserves the completeness-soundness gap. Combining our transformation with previous results by Slofstra (Forum of Mathematics, Pi 2019) and Fitzsimons, Ji, Vidick and Yuen (STOC 2019), we obtain the corollary that all co-recursively enumerable languages (which include undecidable problems as well as all decidable problems) have zero knowledge MIP protocols with vanishing promise gap.

  • 关键词:multi-prover interactive proofs ; Quantum complexity classes ; zero knowledge
国家哲学社会科学文献中心版权所有