MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)

• URL: http://arxiv.org/abs/2506.22961v1
• Date: Sat, 28 Jun 2025 17:43:32 GMT
• Title: MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)
• Authors: Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner,
• Abstract summary: We present a generalization of the MPC-in-the-head paradigm to the quantum setting.<n>We propose a new approach to build zero-knowledge protocols where security holds even against a verifier that can obtain a superposition of transcripts.
• Score: 19.71357898702801
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The MPC-in-the-head technique (Ishai et al., STOC 2007) is a celebrated method to build zero-knowledge protocols with desirable theoretical properties and high practical efficiency. This technique has generated a large body of research and has influenced the design of real-world post-quantum cryptographic signatures. In this work, we present a generalization of the MPC-in-the-head paradigm to the quantum setting, where the MPC is running a quantum computation. As an application of our framework, we propose a new approach to build zero-knowledge protocols where security holds even against a verifier that can obtain a superposition of transcripts. This notion was pioneered by Damgard et al., who built a zero-knowledge protocol for NP (in the common reference string model) secure against superposition attacks, by relying on perfectly hiding and unconditionally binding dual-mode commitments. Unfortunately, no such commitments are known from standard cryptographic assumptions. In this work we revisit this problem, and present two new three-round protocols in the common reference string model: (i) A zero-knowledge argument for NP, whose security reduces to the standard learning with errors (LWE) problem. (ii) A zero-knowledge argument for QMA from the same assumption.

Related papers

• Public-Key Quantum Authentication and Digital Signature Schemes Based on the QMA-Complete Problem [0.0]
  We propose a quantum authentication and digital signature protocol whose security is founded on the Quantum Merlin Arthur(QMA)-completeness of the consistency of local density matrices.<n>We provide a rigorous security analysis, proving the scheme's unforgeability against adaptive chosen-message attacks by quantum adversaries.
  arXiv  Detail & Related papers  (2025-06-20T10:56:50Z)
• Quantum Homogenization as a Quantum Steady State Protocol on NISQ Hardware [42.52549987351643]
  Quantum homogenization is a reservoir-based quantum state approximation protocol.<n>We extend the standard quantum homogenization protocol to the dynamically-equivalent ($mathttSWAP$)$alpha$ formulation.<n>We show that our proposed protocol yields a completely positive, trace preserving (CPTP) map under which the code subspace is correctable.
  arXiv  Detail & Related papers  (2024-12-19T05:50:54Z)
• Practical hybrid PQC-QKD protocols with enhanced security and performance [44.8840598334124]
  We develop hybrid protocols by which QKD and PQC inter-operate within a joint quantum-classical network. In particular, we consider different hybrid designs that may offer enhanced speed and/or security over the individual performance of either approach.
  arXiv  Detail & Related papers  (2024-11-02T00:02:01Z)
• On the Equivalence between Classical Position Verification and Certified Randomness [1.5391321019692432]
  Gate-based quantum computers hold enormous potential to accelerate classically intractable computational tasks.<n>For a long time, it remained challenging to demonstrate the quantum utility of Random circuit sampling on practical problems.<n>Recently, leveraging RCS, an interactive protocol generating certified randomness was demonstrated using a trapped ion quantum computer.
  arXiv  Detail & Related papers  (2024-10-04T23:49:38Z)
• Single-Round Proofs of Quantumness from Knowledge Assumptions [41.94295877935867]
  A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass. Existing single-round protocols require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. We construct efficient single-round proofs of quantumness based on existing knowledge assumptions.
  arXiv  Detail & Related papers  (2024-05-24T17:33:10Z)
• Protocols for counterfactual and twin-field quantum digital signature [0.0]
  Quantum digital signature (QDS) is the quantum version of its classical counterpart. We propose a QDS scheme based on quantum counterfactuality. We show how this two-way protocol can be turned into an equivalent non-counterfactual, one-way protocol.
  arXiv  Detail & Related papers  (2023-10-17T14:33:51Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  We construct the first fully homomorphic encryption scheme with certified deletion. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
  arXiv  Detail & Related papers  (2022-03-03T10:07:32Z)
• Relativistic zero-knowledge protocol for NP over the internet unconditionally secure against quantum adversaries [0.0]
  We present a new relativistic protocol for NP which is secure against quantum adversaries. We use Stern's zero-knowledge scheme for the Syndrome Decoding problem, which was used before in post-quantum cryptography.
  arXiv  Detail & Related papers  (2021-12-02T16:18:09Z)
• Device-Independent-Quantum-Randomness-Enhanced Zero-Knowledge Proof [25.758352536166502]
  Zero-knowledge proof (ZKP) is a fundamental cryptographic primitive that allows a prover to convince a verifier of the validity of a statement. As an efficient variant of ZKP, non-interactive zero-knowledge proof (NIZKP) adopting the Fiat-Shamir is essential to a wide spectrum of applications.
  arXiv  Detail & Related papers  (2021-11-12T13:36:43Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Multi-theorem (Malicious) Designated-Verifier NIZK for QMA [4.264192013842096]
  We present the first non-interactive zero-knowledge argument system for QMA with multi-theorem security. Our technique is classical but works for quantum protocols and allows the construction of a reusable MDV-NIZK for QMA.
  arXiv  Detail & Related papers  (2020-07-25T13:14:49Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.