⚛️ quantum physics

Tight Parallel Repetition for Private-Coin Arguments

Assuming the existence of homomorphic encryption, this paper establishes that parallel repetition of interactive arguments achieves tight exponential soundness error reduction in the post-quantum setting for both standard and threshold verifiers, enabling the construction of the first constant-round succinct argument for QMA with negligible errors.

Original authors: Zvika Brakerski, Andrew Huang, Yael Tauman Kalai, Nicholas Spooner

Published 2026-10-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zvika Brakerski, Andrew Huang, Yael Tauman Kalai, Nicholas Spooner

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

In the world of cryptography, there is a constant tension between security and efficiency. Imagine a system where a user wants to prove they know a secret—like a password or a private key—without actually revealing the secret itself. This is the realm of interactive proofs. In these systems, a prover tries to convince a verifier of their knowledge through a series of questions and answers. If the prover is honest, they succeed easily. If they are attempting to deceive, the system is designed so that they have only a small chance of fooling the verifier. To make this chance vanishingly small, cryptographers often use a technique called parallel repetition. Instead of running the test once, they run many copies of the test at the same time. The logic is simple: if a cheater has a one-in-a-hundred chance of lying successfully in a single round, running a hundred rounds in parallel should make their chance of lying successfully in all of them astronomically low.

However, this logic holds perfectly only when the verifier's questions are random and public. When the verifier keeps their questions secret until the moment they are asked—a setup known as a private-coin protocol—the situation becomes much more complicated. A clever prover can correlate their answers across the different parallel rounds, using information from one round to help them deceive in another, effectively neutralizing the security boost that repetition is supposed to provide. For decades, researchers struggled to prove that repeating these secret-coin tests in parallel actually makes them safer, especially when the prover might be using the strange, counterintuitive laws of quantum mechanics.

A team of researchers has now solved this long-standing problem for a specific and powerful class of cryptographic tools. They demonstrated that by wrapping these secret-coin tests inside a special type of encryption called homomorphic encryption, parallel repetition works exactly as intended, even against quantum adversaries. Homomorphic encryption is a method that allows a computer to perform calculations on encrypted data without ever decrypting it. In this new approach, the verifier sends their secret questions in an encrypted form. The prover, who cannot read the questions, must compute their answers while the data remains locked inside the encryption. The researchers proved that this specific setup forces any deceptive strategy to fail at a rate that is mathematically tight and predictable. Their work shows that the security error drops at the optimal rate, meaning the system becomes exponentially harder to break with each additional parallel copy, regardless of whether the attacker is a classical computer or a quantum one.

The significance of this finding extends beyond just improving a single protocol. It provides a robust foundation for building constant-round succinct arguments for QMA. QMA is the quantum equivalent of a famous complexity class called NP, which deals with problems where a solution can be verified quickly but might be incredibly hard to find. Previously, creating efficient, secure proofs for these quantum problems required extremely strong and unproven assumptions about the nature of cryptography. The new method relies only on the existence of quantum homomorphic encryption, a concept that is already supported by other well-studied mathematical problems. This means that secure, efficient verification of quantum computations is now within reach using assumptions that are much more reasonable and widely accepted.

The researchers achieved this by developing a new way to analyze how a deceptive prover behaves when faced with these encrypted challenges. In classical computing, a common trick to analyze such systems involves "rewinding" the prover: running the test, seeing if the prover succeeded, and then rewinding time to try a different path. This trick does not work in the quantum world because measuring a quantum system changes it, and you cannot simply rewind a quantum state without destroying the information it holds. The team bypassed this obstacle by using a technique called quantum singular value transformation. Instead of rewinding, they manipulated the quantum state in a way that effectively rotated the prover's strategy back to a starting point, allowing them to test different scenarios without breaking the quantum coherence. This allowed them to prove that the encryption scheme successfully prevents the prover from correlating their answers across the parallel rounds.

The result is a system where the verifier can be confident that if a prover passes a threshold of successful rounds, they are almost certainly telling the truth. The researchers showed that this holds true even if the prover is allowed to use a threshold strategy, where they only need to succeed in a certain number of the parallel copies rather than all of them. This flexibility is crucial for real-world applications where perfect success in every single instance might be too demanding. The proof is rigorous and applies to any protocol with a polynomial number of rounds, ensuring that the security does not degrade as the complexity of the interaction increases.

By establishing these tight bounds, the paper closes a gap in our understanding of quantum cryptography. It confirms that the combination of homomorphic encryption and parallel repetition is a powerful tool for amplifying security. This is not just a theoretical curiosity; it paves the way for practical systems where users can verify complex quantum computations with high confidence and low overhead. The work suggests that the future of secure quantum communication does not require magic or unproven miracles, but rather the careful application of known cryptographic principles to the quantum realm. The researchers have provided a clear path forward, showing that with the right tools, we can build systems that remain secure even in the face of the most advanced quantum attacks.

Technical Summary: Tight Parallel Repetition for Private-Coin Arguments

1. Problem Statement

Parallel repetition is a fundamental technique for amplifying the soundness of proof systems by executing multiple independent copies of a protocol. While sequential repetition straightforwardly reduces soundness error, parallel repetition is significantly more subtle because a dishonest prover can correlate its strategies across all executions, potentially preventing the acceptance events from being independent.

For public-coin interactive arguments (where verifier messages are uniformly random), parallel repetition is well-understood: it reduces soundness error exponentially against both classical and quantum polynomial-time provers. However, for private-coin arguments (where verifier messages depend on secret randomness), the situation is fundamentally different. Prior work by Bellare, Impagliazzo, and Naor [BIN97] demonstrated that general private-coin arguments do not necessarily see their soundness reduced under parallel repetition, even against classical adversaries.

To circumvent this negative result in the classical setting, two generic approaches were developed: the random-termination approach [Hai09] and the homomorphic encryption (HE) approach [CL10]. The HE approach transforms a private-coin protocol into a "computationally simulatable" one by having the verifier encrypt its messages and the prover compute responses homomorphically.

The Gap: While the HE approach was known to work for classical provers, it was unknown whether tight parallel repetition bounds could be achieved in the post-quantum setting (where the dishonest prover is a quantum polynomial-time algorithm). Extending prior classical reductions to the quantum setting is difficult because:

Classical reductions often rely on rewinding (running a prover, checking an outcome, and rewinding to a previous state with modified inputs), which is not generally possible for quantum states due to the no-cloning theorem and potential entanglement across repetitions.
Standard semantic security of HE ensures indistinguishability of ciphertexts, but classical proofs often condition the prover's state on a "favorable" event using a dummy ciphertext and then switch to a real ciphertext. It was unclear if the resulting quantum state remains suitable for the real-ciphertext continuation.

2. Methodology and Technical Approach

The authors propose a novel reduction strategy that avoids standard rewinding by utilizing Quantum Singular Value Transformation (QSVT) and a coherent state-switching technique.

2.1 The Homomorphic Encryption (HE) Transformation

The authors follow the transformation of Chung and Liu [CL10]. Given a private-coin interactive argument $(P, V)$ , they construct an encrypted protocol $(\hat{P}, \hat{V})$ :

The verifier $\hat{V}$ simulates $V$ , encrypting its messages under a fresh HE key in each round.
The prover $\hat{P}$ homomorphically evaluates the strategy of $P$ on the encrypted messages.
Crucially, for the post-quantum setting, the authors utilize Quantum Homomorphic Encryption (QHE) that is "classically friendly" (decryption of classical messages remains classical) to ensure the verifier remains efficient.

2.2 The Reduction Strategy

The core of the paper is a reduction that converts a dishonest prover $B$ against the $k$ -fold parallel repetition of the encrypted protocol into a dishonest prover $A$ against the single-copy original protocol.

Classical Analysis (The Baseline):
The authors first establish a new, tighter analysis for the classical setting. The reduction embeds an external verifier in one coordinate (say, index $i$ ) and simulates the other $k-1$ coordinates internally.

Correlation Removal: Following [CHS05, CL10], the reduction includes a preprocessing step to ensure the prover's success in the embedded coordinate is not negatively correlated with the others.
Dummy vs. Real Messages: The reduction initially uses encryptions of a dummy message (0) for the embedded coordinate. It samples randomness for the internal verifiers until the prover accepts the other $k-1$ copies. It then attempts to "swap" the dummy encryption for the real verifier message.

Quantum Analysis (The Innovation):
Extending this to quantum provers requires overcoming the inability to rewind.

Coherent Post-Selection: Instead of classically sampling randomness and discarding failures, the reduction prepares the encryption randomness for the embedded coordinate in a superposition. It coherently measures whether the internal verifiers accept, effectively "post-selecting" on the event where the prover succeeds on the $k-1$ internal copies.
QSVT for State Rotation: The challenge is that after post-selection, the prover's state is entangled with the encryption registers. To switch the ciphertext from $|Enc(0)\rangle$ $∣ E n c (0)⟩$ to $|Enc(q)\rangle$ $∣ E n c (q)⟩$ (where $q$ $q$ is the real message), the authors employ Quantum Singular Value Transformation (QSVT).
- They define two subspaces: $\mathcal{A}$ (states where the internal verifiers accept) and $\mathcal{B}$ (states where the encryption registers hold $|Enc(0)\rangle$ ).
- QSVT allows the reduction to rotate the state from the acceptance subspace $\mathcal{A}$ back to the clean encryption subspace $\mathcal{B}$ , effectively "undoing" the entanglement caused by the post-selection.
Ciphertext Swapping: Once the state is rotated back to $\mathcal{B}$ , the reduction swaps $|Enc(0)\rangle$ with $|Enc(q)\rangle$ . It then applies the inverse QSVT to rotate the state back to the acceptance subspace $\mathcal{A}$ , now conditioned on the real message.
Indistinguishability: The authors prove that this process preserves the prover's state up to negligible error. They leverage the semantic security of HE to argue that the prover cannot distinguish the swap, even though the reduction performs coherent operations. A key technical lemma (Lemma 4.3) shows that if a distinguisher cannot tell apart the distributions of the encryption randomness, it cannot distinguish the final quantum states after the QSVT-based swapping procedure.

2.3 Threshold Verifiers

The results are generalized to threshold verifiers, where the verifier accepts if at least $t$ out of $k$ executions accept. The reduction adapts the "correlation reduction" strategy to handle cases where the prover succeeds on a subset of executions, ensuring the bounds hold for any threshold $t$ .

3. Key Contributions and Results

3.1 Tight Parallel Repetition Theorem

The main result (Theorem 1.1) establishes that for any private-coin interactive argument with soundness error $\epsilon$ , the $k$ -fold parallel repetition of the HE-transformed protocol reduces the soundness error to:

Direct Product ( $t=k$ ): $\epsilon^k + \text{negl}(\lambda)$ .
Threshold ( $t$ ): $\Pr[\sum_{i=1}^k X_i \ge t] + \text{negl}(\lambda)$ , where $X_i$ are i.i.d. Bernoulli( $\epsilon$ ) variables.

These bounds are information-theoretically tight (up to negligible factors) and hold against quantum polynomial-time (QPT) provers.

3.2 Improvements Over Prior Work

Post-Quantum Security: Unlike previous results which were limited to classical provers, this work achieves tight bounds for quantum provers.
Tighter Bounds: The new analysis improves upon the bounds known even in the classical setting (e.g., [CL10, HS11]), particularly for threshold verifiers where previous bounds degraded with the number of rounds.
Round Independence: The threshold result provides a bound independent of the protocol's round complexity, provided the rounds are polynomial.

3.3 Application to QMA

As a direct corollary (Corollary 1.2), the authors construct the first constant-round succinct argument for QMA (Quantum Merlin-Arthur) with negligible completeness and soundness errors.

Assumption: This construction relies solely on the existence of Quantum Homomorphic Encryption (QHE), which is implied by the post-quantum hardness of the Learning With Errors (LWE) problem.
Significance: Previous constructions of such arguments required the much stronger assumption of post-quantum indistinguishability obfuscation (iO) in addition to LWE.

4. Significance and Claims

The paper claims to resolve a long-standing open problem regarding the parallel repetition of private-coin arguments in the quantum setting. By developing a coherent substitute for classical rewinding using QSVT, the authors demonstrate that homomorphic encryption can effectively "break" the correlations a dishonest prover might exploit across parallel executions.

The significance lies in:

Foundational Cryptography: Establishing that parallel repetition works tightly for private-coin protocols even against quantum adversaries, a result previously thought to be out of reach due to the lack of quantum rewinding techniques.
Efficiency: Providing constant-round succinct arguments for QMA under standard cryptographic assumptions (LWE via QHE), removing the need for the exotic iO assumption.
Methodological Advance: Introducing a technique (coherent ciphertext swapping via QSVT) that may have broader applications in quantum cryptography, particularly in scenarios requiring state manipulation without full rewinding.

The authors remain modest regarding the necessity of the "negligible" additive error, noting that information-theoretic lower bounds suggest such factors are likely necessary [DJMW12]. They also note that their reduction for non-uniform adversaries requires multiple copies of the prover's initial state, which they argue is likely necessary for increasing the success probability in the quantum setting.