⚛️ quantum physics

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

This paper generalizes the MPC-in-the-head paradigm to the quantum setting, enabling the construction of three-round zero-knowledge arguments for both NP and QMA in the common reference string model that remain secure against superposition attacks based on the standard Learning With Errors (LWE) assumption.

Original authors: Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner

Published 2026-07-08

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Proving You Know a Secret Without Showing It

Imagine you have a secret password (a "witness") that proves you are allowed to enter a secure building. You want to convince a guard (the "verifier") that you know the password without actually telling them what it is. This is called a Zero-Knowledge Proof.

In the classical world (the world of regular computers), there is a famous trick called "MPC-in-the-Head" to do this.

The Analogy: Imagine you are a single person, but you pretend to be a team of five friends sitting in a room. You split your secret password into five pieces (shares) and give one piece to each "friend" inside your head.
The Game: You run a conversation between these five friends to prove the password works. Then, the guard asks to see the notes of just two of the friends.
The Result: If the notes match up and make sense, the guard is convinced the whole team (and therefore you) knows the password. But because the guard only saw two friends, they can't figure out the full password.

The New Problem: The "Superposition" Thief

This paper tackles a scary new problem: What if the guard is a quantum computer?

In the quantum world, a "superposition" is like being in two places at once. A quantum adversary (the bad guy) doesn't just ask to see the notes of Friend A or Friend B. They can ask to see a superposition of both at the same time.

The Metaphor: Imagine the guard doesn't just look at the paper; they put the paper in a magical box that lets them peek at every possible combination of friends' notes simultaneously.
The Risk: In the old tricks, if you only showed two friends, the secret was safe. But if the guard can peek at a "superposition" of the notes, they might be able to mathematically reconstruct the whole password, breaking the security.

The authors ask: Can we build a Zero-Knowledge proof that stays safe even if the guard uses this "superposition" superpower?

The Solution: "MPC in the Quantum Head"

The authors say yes, and they do it by upgrading the "MPC-in-the-Head" trick for the quantum world. They call their new method "MPC in the Quantum Head."

Here is how they solve the two main challenges:

1. For Regular Secrets (NP Problems)

The Old Problem: Previous attempts to make this quantum-safe relied on a special type of "magic lock" (a commitment scheme) that was perfectly hidden. But nobody knows how to build these locks using standard math assumptions.
The New Trick: The authors use a different kind of lock called a "Dual-Mode Commitment."
- The Analogy: Imagine a safe that has two keys.
  - Key A (Binding): The safe is locked tight. Once you put a note inside, you can't change it. But if you have a super-powerful computer, you might be able to guess the note.
  - Key B (Hiding): The safe is so opaque that even a super-powerful computer can't see what's inside. But, if you have a special "backdoor" (which the prover has), you can open it to reveal anything you want.
- How it works: The prover uses the "Hiding" mode to send the notes. Because the notes are hidden, the quantum guard can't learn the secret even if they look at them in superposition. The authors prove that even with this slightly weaker lock, the math holds up.

2. For Quantum Secrets (QMA Problems)

This is the harder part. What if the secret itself is a quantum state (like a delicate, invisible cloud of probability) rather than a simple password?

The Challenge: In the classical version, the "friends" pass notes back and forth. In the quantum version, the "friends" pass quantum particles (qubits). You can't just "write down" the notes of a quantum particle without destroying the secret. There is no "transcript" to check.
The New Trick: The authors use a technique called "Circuit-to-Hamiltonian Reduction."
- The Analogy: Imagine the quantum conversation between the friends is a movie. Usually, you can't check the movie without watching the whole thing.
- Instead, they turn the movie into a frozen sculpture (a Hamiltonian). This sculpture has a specific shape. If the friends played the game correctly, the sculpture has a very low "energy" (it's smooth and perfect). If they cheated, the sculpture is bumpy and has high energy.
- The Check: The guard doesn't ask to see the whole movie. They just poke the sculpture at a few random spots to measure the energy.
  - If the energy is low, the game was played correctly.
  - Because the sculpture is made of many tiny parts, poking a few spots doesn't reveal the whole movie (the secret).
The "Quantum Head": The prover splits the quantum secret among the friends, encrypts it, and creates this "frozen sculpture" of the conversation. The guard checks the energy of the sculpture.

Why This Matters (According to the Paper)

The paper claims to have built two specific tools:

A proof for regular secrets (NP): It works based on a standard math problem called LWE (Learning With Errors), which is believed to be hard even for quantum computers.
A proof for quantum secrets (QMA): This is a major breakthrough. It is the first time a Zero-Knowledge proof for quantum problems has been built that is secure against these "superposition" attacks, also based on the LWE assumption.

Summary

The paper takes a classic trick for proving secrets ("MPC-in-the-Head"), upgrades it to handle quantum mechanics, and solves the problem of "superposition attacks." They do this by:

Using special "dual-mode" locks that are hard to crack even by quantum computers.
Turning quantum conversations into "frozen sculptures" (Hamiltonians) that can be checked without revealing the secret.

This ensures that even if a future quantum computer tries to peek at a proof in a "superposition" of all possibilities, the secret remains safe.

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

Problem Statement

The paper addresses the construction of Zero-Knowledge (ZK) protocols that remain secure even when a malicious verifier can issue challenges and receive responses in quantum superposition. This "superposition security" is a critical strengthening of classical security, motivated by scenarios where quantum adversaries might interact with classical cryptographic devices or where classical primitives are embedded within larger quantum protocols.

While Damgård et al. [19] pioneered this notion for NP, their construction relied on perfectly hiding and unconditionally binding dual-mode commitments, a primitive not known to exist under standard cryptographic assumptions. Furthermore, their techniques did not naturally extend to QMA (Quantum Merlin-Arthur), the quantum analogue of NP, due to the fundamental difficulty of verifying quantum computations without revealing the quantum witness.

Existing alternatives, such as Non-Interactive Zero-Knowledge (NIZK) proofs, are either unknown for QMA under standard assumptions or rely on heuristic models (e.g., quantum random oracles or obfuscation). Additionally, NIZKs are generally heavier than the three-round $\Sigma$ -protocols preferred for efficiency.

Methodology

The authors propose a generalization of the MPC-in-the-Head paradigm [30] to the quantum setting, termed "MPC in the Quantum Head." The core methodology involves two distinct but related constructions:

1. Superposition-Secure ZK for NP

The authors revisit the Damgård et al. [19] protocol but replace the requirement for perfectly hiding commitments with dual-mode commitments (statistically hiding, computationally binding in one mode; perfectly binding, computationally hiding in the other).

Technique: The proof strategy utilizes a hybrid argument. In the real world, commitments are to the MPC views. In a hybrid, commitments are switched to the statistically hiding mode. Crucially, the authors introduce a hybrid where the prover commits to 0 (instead of honest views) but can still open them to the honest views using the computational binding property (which is broken by an unbounded simulator).
Security Argument: Once the commitments are to 0, the opened views (a subset of shares) and the unopened commitments form a perfectly secure secret sharing scheme. The authors leverage a lemma from [19] stating that perfect secret sharing remains secure against superposition attacks if fewer than $2t$ shares are queried (where $t$ is the privacy threshold). This allows the security proof to proceed without requiring perfect hiding commitments.

2. MPC in the Quantum Head for QMA

Extending this to QMA requires handling quantum witnesses and quantum verification circuits.

The Obstacle: In classical MPC-in-the-Head, the prover reveals "views" (transcripts) of parties. In Multiparty Quantum Computation (MPQC), parties exchange quantum messages, meaning there is no classical transcript to reveal; a party only holds a final quantum state.
The Solution: The authors model the global MPQC protocol as a quantum circuit (replacing message passing with SWAP gates). They apply Kitaev's Circuit-to-Hamiltonian reduction [34] to this circuit.
- The "witness" becomes the history state of the Hamiltonian, which has low energy if and only if the MPQC accepts.
- The prover commits to this history state (qubit-by-qubit) using a Quantum One-Time Pad (QOTP) and commits to the QOTP keys using dual-mode commitments.
- The verifier challenges the prover to open specific qubits corresponding to local Hamiltonian terms.
Verification: The verifier measures the opened qubits to check the local Hamiltonian terms. If the energy is low, the history state corresponds to a valid execution.
Zero-Knowledge: The ZK property relies on the fact that opening a subset of qubits corresponding to a local Hamiltonian term reveals no more information than controlling a subset of parties in the underlying MPQC. The authors utilize a perfectly $2t$ -private MPQC protocol [17, 39] to ensure that the history state of the computation on a secret-shared witness remains indistinguishable from a history state on a dummy input, even under superposition queries.

Key Contributions

Generalization of MPC-in-the-Head: The paper presents the first instantiation of the MPC-in-the-Head paradigm for quantum functionalities (MPQC), effectively creating a "Quantum MPC-in-the-Head."
Superposition-Secure ZK for NP: The authors construct a three-round $\Sigma$ -protocol for NP secure against superposition attacks based on any post-quantum dual-mode commitment (e.g., from LWE). This improves upon [19] by removing the need for non-standard perfectly hiding commitments.
Superposition-Secure ZK for QMA: The paper constructs the first three-round $\Sigma$ -protocol for QMA secure against superposition attacks, based on the Learning With Errors (LWE) assumption. This fills a gap where no standard-assumption NIZKs for QMA exist.
New Proof Techniques:
- A novel hybrid argument for NP that switches commitments to 0 to leverage perfect secret sharing properties against superposition attacks.
- A technique for QMA that combines Circuit-to-Hamiltonian reduction with MPQC and QOTP, utilizing the indistinguishability of EPR pairs and one-time pads to simulate the protocol in the presence of superposition queries.

Results

The paper establishes the following theorems (informal):

Theorem 1.1: Assuming the post-quantum security of LWE, there exist three-round $\Sigma$ -protocols for QMA in the Common Reference String (CRS) model satisfying zero-knowledge against malicious verifiers making superposition queries.
Theorem 1.2: Assuming the existence of any post-quantum dual-mode commitments, there exist three-round $\Sigma$ -protocols for NP in the CRS model satisfying zero-knowledge against malicious verifiers making superposition queries.

The protocols achieve statistical soundness and computational zero-knowledge (even against quantum polynomial-time adversaries with superposition access).

Significance and Claims

The authors position this work as a natural and necessary extension of zero-knowledge cryptography into the quantum regime.

Theoretical Importance: It resolves the open problem of constructing superposition-secure ZK for QMA under standard assumptions, a task previously thought difficult due to the lack of suitable NIZKs or commitment schemes.
Practical Relevance: The three-round structure makes these protocols significantly more lightweight than NIZKs, offering a practical path for post-quantum signatures and secure multiparty computation compilers (e.g., GMW-style compilers) that must remain secure against quantum adversaries capable of superposition attacks.
Conceptual Advancement: The "MPC in the Quantum Head" framework is presented as a generalizable technique that could be applied to other commit-and-open or cut-and-choose protocols requiring partial verification of quantum computations.

The paper explicitly notes that while NIZKs for QMA exist in oracle models or with designated verifiers, their focus on three-round protocols with standard assumptions and public setup (CRS) provides a more direct and efficient solution for the specific threat model of superposition attacks.