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

DOI10.1007/978-3-030-56877-1_28MaRDI QIDQ2104244zbMATH OpenOpenAlexFDO

Authors Andrea Coladangelo, Thomas Vidick, Tina Zhang

Publication date 7 December 2022

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

zbMATH Keywords

zero-knowledgeargument systemsQMAnon-interactive proof

Mathematics Subject Classification ID

Cryptography (94A60)

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.

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

Cites work

• scientific article; zbMATH DE number 4191103 (Why is no real title available?)
• scientific article; zbMATH DE number 708820 (Why is no real title available?)
• scientific article; zbMATH DE number 2009983 (Why is no real title available?)
• Definitions and properties of zero-knowledge proof systems
• Fiat-Shamir: from practice to theory
• Non-interactive zero-knowledge proofs in the quantum random oracle model
• Noninteractive Zero-Knowledge
• Noninteractive zero knowledge for NP from (Plain) Learning With Errors
• Quadratic span programs and succinct NIZKs without PCPs
• Quantum proofs of knowledge
• The knowledge complexity of interactive proof-systems

Cited in

(15)

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

Describes a project that uses

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)