pipette
ESEspañol

Tight Parallel Repetition for Private-Coin Arguments

Zvika Brakerski, Andrew Huang, Yael Tauman Kalai, Nicholas Spooner

PreprintClaims a big step

In the authors' words

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 of the executions are accepted (for some threshold ). 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 with negligible completeness and soundness errors assuming only the existence of quantum homomorphic encryption.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.