arXiv:2609.38941
Tight Post-Quantum Parallel Repetition for Private-Coin Arguments
Zvika Brakerski, Andrew Huang, Yael Tauman Kalai, Nicholas Spooner
Abstract
We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness error at a tight exponential rate even in the post-quantum setting. Moreover, we generalize this result to hold for threshold verifiers, where the parallel repeated verifier accepts if and only if at least $t$ of the executions are accepted (for some threshold $t$). Prior to this work, these results were known only when the cheating prover was assumed to be classical, and it was not known how to achieve tight bounds. As a corollary, we construct the first constant-round succinct argument for $\mathsf{QMA}$ with negligible completeness and soundness errors assuming only the existence of quantum homomorphic encryption.
AI Summary
Parallel repetition is a standard way to reduce the soundness error of interactive arguments without increasing their round complexity, but obtaining tight guarantees against quantum cheating provers is the question addressed here. The paper considers private-coin arguments transformed so that they run under homomorphic encryption, rather than claiming a repetition theorem for arbitrary unmodified arguments. Assuming homomorphic encryption secure in the post-quantum setting, the stated main result is that parallel repetition of these transformed arguments reduces soundness error at a tight exponential rate. The result also covers threshold repetition: the repeated verifier accepts exactly when at least $t$ of the component executions accept. The abstract distinguishes this from earlier guarantees restricted to classical cheating provers and states that tight bounds were not previously known. As an application, the paper states a construction of a constant-round succinct argument for $\mathsf{QMA}$ with both negligible completeness error and negligible soundness error, assuming only quantum homomorphic encryption. This connects the repetition theorem to amplification for succinct verification of quantum witnesses. The guarantees are conditional on encryption assumptions and apply after the encryption-based transformation. The supplied text contains only the abstract and LaTeX setup, so it does not provide explicit repetition bounds, parameter dependence, the proof technique beyond the encryption-based framework, or further stated limitations. Those details cannot be assessed from this excerpt.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.