Tight Post-Quantum Parallel Repetition for Private-Coin Arguments
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 QMA with negligible completeness and soundness errors assuming only the existence of quantum homomorphic encryption.
Related
- Quantum interaction can superactivate cheating under parallel repetition
- Parallel Repetition for Entangled Games via Conditional Relative Entropy
- Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation
- Succinct Arguments for QMA in the Quantum Random Oracle Model
- Thermal lifetime of the centralized repetition code: From quantum annealing to social dynamics
BibTeX
@misc{brakerski2026tight,
title = {{Tight Post-Quantum Parallel Repetition for Private-Coin Arguments}},
author = {Zvika Brakerski and Andrew Huang and Yael Tauman Kalai and Nicholas Spooner},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.38941},
eprint = {2609.38941},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38941},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Tight Post-Quantum Parallel Repetition for Private-Coin Arguments
AU - Zvika Brakerski
AU - Andrew Huang
AU - Yael Tauman Kalai
AU - Nicholas Spooner
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2609.38941
UR - https://arxiv.org/abs/2609.38941
AB - 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 QMA with negligible completeness and soundness errors assuming only the existence of quantum homomorphic encryption.
ER -