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

DOI10.1007/978-3-030-56877-1_28zbMATH Open1504.94125arXiv1911.07546OpenAlexW3081357568MaRDI QIDQ2104244FDOQ2104244

Authors: Andrea Coladangelo, Thomas Vidick, Tina Zhang 

Publication date: 7 December 2022

Abstract: We initiate the study of non-interactive zero-knowledge (NIZK) arguments for languages in QMA. Our first main result is the following: if Learning With Errors (LWE) is hard for quantum computers, then any language in QMA has an NIZK argument with preprocessing. The preprocessing in our argument system consists of (i) the generation of a CRS and (ii) a single (instance-independent) quantum message from verifier to prover. The instance-dependent phase of our argument system involves only a single classical message from prover to verifier. Importantly, verification in our protocol is entirely classical, and the verifier needs not have quantum memory; its only quantum actions are in the preprocessing phase. Our second contribution is to extend the notion of a classical proof of knowledge to the quantum setting. We introduce the notions of arguments and proofs of quantum knowledge (AoQK/PoQK), and we show that our non-interactive argument system satisfies the definition of an AoQK. In particular, we explicitly construct an extractor which can recover a quantum witness from any prover which is successful in our protocol. Finally, we show that any language in QMA has an (interactive) proof of quantum knowledge.

Full work available at URL: https://arxiv.org/abs/1911.07546

Recommendations

• Classically verifiable NIZK for QMA with preprocessing
• Non-interactive classical verification of quantum computation
• Multi-theorem designated-verifier NIZK for QMA
• The round complexity of quantum zero-knowledge
• Quantum proofs of knowledge

zbMATH Keywords

zero-knowledgeargument systemsQMAnon-interactive proof

Mathematics Subject Classification ID

Cryptography (94A60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The knowledge complexity of interactive proof-systems
• Title not available (Why is that?)
• Definitions and properties of zero-knowledge proof systems
• Noninteractive Zero-Knowledge
• Quadratic span programs and succinct NIZKs without PCPs
• Noninteractive zero knowledge for NP from (Plain) Learning With Errors
• Quantum proofs of knowledge
• Non-interactive zero-knowledge proofs in the quantum random oracle model
• Fiat-Shamir: from practice to theory

Cited In (15)

• Secure quantum extraction protocols
• A black-box approach to post-quantum zero-knowledge in constant rounds
• On the concurrent composition of quantum zero-knowledge
• Algorithms and Computation
• The round complexity of quantum zero-knowledge
• Non-interactive classical verification of quantum computation
• Title not available (Why is that?)
• A new framework for quantum oblivious transfer
• Classical proofs of quantum knowledge
• Certified everlasting zero-knowledge proof for QMA
• Interactive oracle arguments in the QROM and applications to succinct verification of quantum computation
• Multi-theorem designated-verifier NIZK for QMA
• QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
• Commitments to quantum states
• Classically verifiable NIZK for QMA with preprocessing

Uses Software

• Pinocchio

This page was built for publication: Non-interactive zero-knowledge arguments for QMA, with preprocessing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104244)