Tight Parallel Repetition for Private-Coin Arguments

1 Introduction

• Private-coin parallel repetition is difficult because a cheating prover can correlate executions, and prior work showed repetition need not reduce soundness even against classical adversaries.In contrast, parallel repetition for public-coin arguments is understood against quantum polynomial-time provers, using efficient simulation of verifier messages.Source: §1 · p. 3
• Earlier classical approaches used random termination or homomorphic encryption to enable parallel repetition against classical polynomial-time provers.The random-termination approach makes the verifier partially simulatable; the homomorphic-encryption approach encrypts verifier messages for homomorphic computation by the honest prover.Source: §1 · pp. 3–4

1.1 Our Results

• The paper applies the homomorphic-encryption approach to private-coin arguments, preserving round count and, up to negligible additive error, completeness and single-copy soundness.For a quantum honest prover, the scheme is classical friendly: encryption and decryption are classical on classical messages.Source: §1.1 · p. 4
• The results establish information-theoretically tight bounds for both direct-product and threshold repetition, improving on prior results even in the classical setting.For protocols with polynomially many rounds, the threshold bound is independent of round complexity.Source: §1.1 · p. 4
• The quantum setting complicates prior reductions because rewinding is unavailable for arbitrary quantum provers, whose states may be entangled across repetitions.The proof instead develops a coherent substitute for rewinding and a ciphertext-replacement argument valid under coherent conditioning.Source: §1.1 · pp. 4–5
• Assuming quantum homomorphic encryption, the paper obtains constant-round succinct arguments for QMA with negligible completeness and soundness errors.This improves on prior constructions that required post-quantum indistinguishability obfuscation as well as LWE.Source: §1.1 · p. 5

2.1 HE Transformation

• The HE transformation encrypts each verifier message for homomorphic evaluation by the prover, then decrypts the encrypted response and forwards it to the original verifier.The transformed argument retains the original round count and, subject to negligible additive error, its completeness and single-copy soundness.Source: §2.1 · p. 5
• Chung and Liu’s analysis gives exponential soundness reduction for repeated transformed protocols, while the new technique is more amenable to quantization and yields tighter bounds than prior classical results.The overview notes that transferring the earlier argument to the post-quantum setting is unknown.Source: §2.1 · p. 5

2.2 Classical analysis

• A reduction embeds the external verifier in one randomly chosen repetition, simulates the other instances internally, and forwards a response after checking whether it is a good response.The target is an adversary for the original verifier, using an adversary that succeeds against the repeated HE-transformed argument.Source: §2.2 · p. 6
• Because a prover’s success across coordinates may be correlated, the reduction preprocesses to remove bad correlations and uses their presence to reduce the repetition count when needed.The cited correlation-reduction approach also motivates simulating other coordinates when bad correlations arise.Source: §2.2 · p. 6

2.3 Quantum analysis

• In the quantum analysis, many copies of the adversary’s initial state replace rewinding, while encryption randomness for the external coordinate is kept in superposition and acceptance is measured coherently.The process post-selects on acceptance before interaction, when the adversary’s state can still be retried.Source: §2.3 · p. 7
• To preserve the adversary’s entanglement while swapping a dummy ciphertext for the real verifier message, the reduction uses QSVT to rotate between accepting and ciphertext subspaces.The construction applies QSVT around the ciphertext switch, replacing the projection for an encryption of zero with one for the real message.Source: §2.3 · p. 8
• Because the external verifier’s secret key is needed to assess success, computational indistinguishability alone is insufficient; a SWAP test lifts the argument to statistical indistinguishability.The overview also says preprocessing and a modified acceptance heuristic extend the reduction to threshold verifiers.Source: §2.3 · p. 8

3 Preliminaries

• The preliminaries use PPT and QPT for probabilistic and quantum polynomial time, and assume non-uniform quantum circuits have quantum advice unless stated otherwise.They also introduce trace-distance and computational-indistinguishability notation for quantum states.Source: §3 · pp. 8–9

3.1 Information Theory

• The threshold binomial function gives the probability that at least t of k independent Bernoulli variables with parameter ε equal one; the section also invokes Hoeffding’s inequality.The stated special case is B(k, k, ε) = ε^k.Source: §3.1 · p. 9

3.2 Interactive Protocols with Computational Soundness

• The protocols model a verifier that outputs accept or reject, and their k-fold threshold repetition accepts exactly when at least t of k independent subverifiers accept.An m-round protocol counts m verifier-to-prover message rounds, with the verifier sending first and prover last.Source: §3.2 · pp. 9–10

3.3 Homomorphic Encryption

• Classical homomorphic encryption uses four PPT algorithms and requires correctness, non-uniform post-quantum semantic security, and compact decryption.For leveled schemes, decryption time may depend polynomially on the level bound.Source: §3.3 · pp. 10–11
• Quantum homomorphic encryption uses QPT algorithms and is defined with correctness, non-uniform semantic security, compactness, and classically friendly decryption requirements.Classical friendliness requires efficient classical encryption and deterministic classical decryption.Source: §3.3 · pp. 11–12

3.3.1 The Homomorphic-Encryption Transformation

• The QHE-transformed protocol preserves completeness and soundness up to negligible additive error, but this does not transfer soundness to parallel repetitions with correlated cheating strategies.Fresh encryption keys in every round keep the current key independent of earlier interaction, enabling reliance on semantic security.Source: §3.3.1 · p. 13
• An adapted lemma [HS11, Chu11] reduces excess threshold-repetition success to a minimal subset of executions, yielding either a successful single-copy prover or structure for a quantum reduction.The subset’s success exceeds the corresponding threshold-binomial bound, and its minimality means no execution can be removed while preserving that guarantee.Source: §3.3.1 · p. 14

3.4 Singular Value Decomposition

• The section recalls Jordan’s lemma as characterizing the joint action of two projectors on a Hilbert space.Source: §3.4 · p. 14
• Two Hermitian projectors admit a common invariant decomposition into one- and two-dimensional subspaces, with associated singular vectors and overlap singular values.On two-dimensional subspaces the projectors are rank one; the stated singular values are the overlaps ⟨w_j|v_j⟩.Source: §3.4 · pp. 14–15

3.4.1 Quantum Singular Value Transformation (QSVT)

• For any Hermitian projectors ΠA and ΠB, states in either image with corresponding singular values not too small can be transformed into the other image while approximately preserving relative weights between singular vectors.Theorem 3.9 (modified from) specifies singular values in [1 − ε, 1] when ς_j ≥ δ, and in [−1, 1] otherwise.Source: §3.4.1 · p. 15

4 On Oracle Distinguishers

• Lemma 4.1 turns a quantum oracle distinguisher without direct access to R into a polynomial-size algorithm distinguishing classical samples from D0,λ and D1,λ.The lemma’s conclusion applies to a distinguisher meeting its stated advantage condition.Source: §4 · p. 17
• The technical target is that an adversary who returns RE to |Db,λ⟩ has an internal state statistically indistinguishable between b=0 and b=1.The adversary may apply arbitrary unitaries to E and its workspace and query an oracle that coherently tests whether RE remains in |Db,λ⟩.Source: §4 · p. 17
• A noticeable final-state gap must come from different success probabilities or distinguishable successful residual states, which the proof tests with oracle distinguishers and a SWAP test.The residual-state difference is weighted by the probability that the successful branch occurs.Source: §4 · p. 18

5 Parallel Repetition for Private-Coin Protocols

• The proof assumes quantum non-uniform adversaries for simplicity, while noting that the reduction preserves uniformity and requires more copies of the prover’s initial state in the non-uniform setting.The authors note that this larger copy requirement is likely necessary [BQSY24].Source: §5 · p. 21
• For polynomial k and threshold t ≤ k, the k-fold protocol has soundness B(k, t, ε) + negl(λ) against every QPT adversary.The corollary applies to the verifier that accepts when at least t executions accept.Source: §5 · pp. 21–22
• The reduction embeds the external verifier in one coordinate, post-selects on acceptance elsewhere, and uses QSVT to return the prover state before answering its queries.It prepares dummy encryptions as coherent purifications, enabling replacement with query encryptions after post-selection; the prover cannot access the purifying randomness.Source: §5 · p. 23
• The proof bounds the hybrids’ trace distance by reducing ciphertext replacement to QHE security and showing one execution’s states are negligibly close before repeating it polynomially many times.The hybrid argument establishes computational indistinguishability even for quantum adversaries with quantum advice; the polynomial number of executions is handled by data processing and a union bound.Source: §5 · p. 26

• The H0-to-H1,1 transition is negligibly close, while H1,1-to-H1,2 and H1,3-to-H1,4 have trace distance zero.Source: §5 · pp. 29–30
• The H1,2-to-H1,3 transition has trace distance at most µ + negl(λ), because checking that encryption registers are clean fails with very small probability after favorable continuation.The QSVT algorithm returns the remaining state essentially to the clean-encryption subspace, so conditioning on the check barely disturbs it.Source: §5 · p. 29
• Commuting verifier operations and register measurements transforms H1,4 into H1, where first-round encryption randomness is sampled explicitly before applying U1.Source: §5 · pp. 31–33
• The accumulated hybrid trace distance is bounded by ν 10km + negl(λ), and repeating the argument through round m yields hybrid Hm.Source: §5 · p. 34

5 Parallel Repetition for Private-Coin Protocols

• The reduction repeatedly runs B against bV k,t, returning a transcript where the other executions have exactly t′−1 accepts, or aborting if none is found.The first subverifier’s randomness is hardwired as rQuery,1.Source: §5 · p. 34
• The reduction’s success probability is lower-bounded by Hm’s probability of accepting execution 1, minus ν/(10k) and a negligible term.The bound is introduced across the consecutive passages “It therefore follows that” and the displayed inequality.Source: §5 · p. 34

AI Disclosure

• The first manuscript, containing the main proof ideas, was written without model assistance and drew inspiration from.The stated inspiration was its correlation-reduction strategy for simulatable arguments.Source: AI Disclosure · p. 35
• ChatGPT 6 Astra identified a minor, non-standard reduction modification that could tighten soundness.Source: AI Disclosure · p. 35
• The authors realized the same improvement could use a modified correlation-reduction strategy from classical three-message arguments [HS11].The changes materially affected the proofs of Lemmas 3.7 and 5.8.Source: AI Disclosure · p. 35

A.1 Proof of Lemma 3.7

• The transformation selects a coordinate subset S, a threshold t′, and verifier-query randomness for coordinates outside S.The reduction simulates the verifiers outside S internally and uses the external verifier for coordinates in S.Source: §A.1 · p. 37
• For each candidate coordinate, it estimates acceptance probabilities using M2 simulations with separate copies of the prover’s initial state.It estimates whether at least t′ or t′ − 1 of the remaining coordinates in S accept.Source: §A.1 · p. 38
• The selection procedure can reduce S and decrement t′ when its tests identify a suitable coordinate.It outputs the resulting S, t′, and query randomness for coordinates outside S.Source: §A.1 · p. 38
• The transformation runs in time polynomial in λ, k, and ν^-1.It terminates within k iterations, each using at most M1 · M2 executions of the repeated prover.Source: §A.1 · p. 38
• Hoeffding’s inequality and a union bound control inaccurate estimates, while a further union bound controls missed candidate sets across iterations.The stated total probability bound for these bad events is 2^-λ.Source: §A.1 · p. 38

A.2 Proof of Lemma 5.8

• The proof defines η(r) as the probability that the first subverifier accepts under Hm, conditioned on its query randomness being r.Source: §A.2 · p. 39
• Hm accepts at an iteration when earlier iterations avoid Y = t′ − 1 and that iteration has Y = t′ − 1 with A1 = 1.Source: §A.2 · p. 39
• For coins r in Good, the conditional acceptance probability is bounded by (1 − η(r)) B(k′ − 1, t′, ε) + η(r) B(k′ − 1, t′ − 1, ε) + (10k′ − 9)γ + γ.Source: §A.2 · p. 39
• Averaging over the first query randomness and applying the theorem’s hypothesis gives a second bound involving ε-weighted threshold terms.The resulting expression includes (10k′ − 1)γ.Source: §A.2 · p. 40
• Combining the inequalities yields a strict positive difference between the two threshold bounds, expressed as a binomial probability.Source: §A.2 · p. 40