Parallel repetition of computationally sound protocols revisited

K.Z. Pietrzak, D. Wikström, Journal of Cryptology 25 (2012) 116–135.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
;
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.
Publishing Year
Date Published
2012-11-01
Journal Title
Journal of Cryptology
Volume
25
Issue
1
Page
116 - 135
IST-REx-ID

Cite this

Pietrzak KZ, Wikström D. Parallel repetition of computationally sound protocols revisited. Journal of Cryptology. 2012;25(1):116-135. doi:10.1007/s00145-010-9090-x
Pietrzak, K. Z., & Wikström, D. (2012). Parallel repetition of computationally sound protocols revisited. Journal of Cryptology, 25(1), 116–135. https://doi.org/10.1007/s00145-010-9090-x
Pietrzak, Krzysztof Z, and Douglas Wikström. “Parallel Repetition of Computationally Sound Protocols Revisited.” Journal of Cryptology 25, no. 1 (2012): 116–35. https://doi.org/10.1007/s00145-010-9090-x.
K. Z. Pietrzak and D. Wikström, “Parallel repetition of computationally sound protocols revisited,” Journal of Cryptology, vol. 25, no. 1, pp. 116–135, 2012.
Pietrzak KZ, Wikström D. 2012. Parallel repetition of computationally sound protocols revisited. Journal of Cryptology. 25(1), 116–135.
Pietrzak, Krzysztof Z., and Douglas Wikström. “Parallel Repetition of Computationally Sound Protocols Revisited.” Journal of Cryptology, vol. 25, no. 1, Springer, 2012, pp. 116–35, doi:10.1007/s00145-010-9090-x.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar