An efficient parallel repetition theorem Conference Paper


Author(s): Håstad, Johan; Pass, Rafael; Wikström, Douglas; Pietrzak, Krzysztof
Title: An efficient parallel repetition theorem
Title Series: LNCS
Affiliation
Abstract: We present a general parallel-repetition theorem with an efficient reduction. As a corollary of this theorem we establish that parallel repetition reduces the soundness error at an exponential rate in any public-coin argument, and more generally, any argument where the verifier's messages, but not necessarily its decision to accept or reject, can be efficiently simulated with noticeable probability.
Keywords: Parallel repetition; Exponential rates
Conference Title: TCC: Theory of Cryptography Conference
Volume: 5978
Conference Dates: February 9-11, 2010
Conference Location: Zurich, Switzerland
Publisher: Springer  
Date Published: 2010-03-26
Start Page: 1
End Page: 18
Copyright Statement: © International Association for Cryptologic Research 2010
DOI: 10.1007/978-3-642-11799-2_1
Open access: no
IST Austria Authors
Related IST Austria Work