Parallel repetition of computationally sound protocols revisited Journal Article


Author(s): Pietrzak, Krzysztof; Wikström, Douglas
Article Title: Parallel repetition of computationally sound protocols revisited
Affiliation
Abstract: We prove a negative result concerning error reduction by parallel repetition for computationally sound protocols, e.g., interactive arguments. Our main result is a complete and computationally sound eight round interactive argument for which k-fold parallel repetition does not reduce the error below a constant for any polynomial k. The starting point for our construction is the work of Bellare, Impagliazzo and Naor (FOCS'97). For any fixed k, they construct a four round protocol for which k-fold parallel repetition does not lower the soundness error. The communication complexity of this protocol is linear in k. By using universal arguments due to Barak and Goldreich (CCC 2002), we turn this protocol into an eight-round protocol whose complexity is basically independent of k.
Keywords: Communication complexity; Error reduction; Parallel repetition; Sound protocol
Journal Title: Journal of Cryptology
Volume: 25
Issue 1
ISSN: 1432-1378
Publisher: Springer  
Date Published: 2012-11-01
Start Page: 116
End Page: 135
Copyright Statement: © International Association for Cryptologic Research 2010
DOI: 10.1007/s00145-010-9090-x
Open access: no
IST Austria Authors
Related IST Austria Work