---
_id: '3241'
abstract:
- lang: eng
  text: '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. '
author:
- first_name: Krzysztof Z
  full_name: Krzysztof Pietrzak
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Douglas
  full_name: Wikström, Douglas
  last_name: Wikström
citation:
  ama: Pietrzak KZ, Wikström D. Parallel repetition of computationally sound protocols
    revisited. <i>Journal of Cryptology</i>. 2012;25(1):116-135. doi:<a href="https://doi.org/10.1007/s00145-010-9090-x">10.1007/s00145-010-9090-x</a>
  apa: Pietrzak, K. Z., &#38; Wikström, D. (2012). Parallel repetition of computationally
    sound protocols revisited. <i>Journal of Cryptology</i>. Springer. <a href="https://doi.org/10.1007/s00145-010-9090-x">https://doi.org/10.1007/s00145-010-9090-x</a>
  chicago: Pietrzak, Krzysztof Z, and Douglas Wikström. “Parallel Repetition of Computationally
    Sound Protocols Revisited.” <i>Journal of Cryptology</i>. Springer, 2012. <a href="https://doi.org/10.1007/s00145-010-9090-x">https://doi.org/10.1007/s00145-010-9090-x</a>.
  ieee: K. Z. Pietrzak and D. Wikström, “Parallel repetition of computationally sound
    protocols revisited,” <i>Journal of Cryptology</i>, vol. 25, no. 1. Springer,
    pp. 116–135, 2012.
  ista: Pietrzak KZ, Wikström D. 2012. Parallel repetition of computationally sound
    protocols revisited. Journal of Cryptology. 25(1), 116–135.
  mla: Pietrzak, Krzysztof Z., and Douglas Wikström. “Parallel Repetition of Computationally
    Sound Protocols Revisited.” <i>Journal of Cryptology</i>, vol. 25, no. 1, Springer,
    2012, pp. 116–35, doi:<a href="https://doi.org/10.1007/s00145-010-9090-x">10.1007/s00145-010-9090-x</a>.
  short: K.Z. Pietrzak, D. Wikström, Journal of Cryptology 25 (2012) 116–135.
date_created: 2018-12-11T12:02:12Z
date_published: 2012-11-01T00:00:00Z
date_updated: 2021-01-12T07:42:03Z
day: '01'
doi: 10.1007/s00145-010-9090-x
extern: 1
fulldoi: https://doi.org/10.1007/s00145-010-9090-x
intvolume: '        25'
issue: '1'
month: '11'
page: 116 - 135
publication: Journal of Cryptology
publication_status: published
publisher: Springer
publist_id: '3439'
quality_controlled: 0
status: public
title: Parallel repetition of computationally sound protocols revisited
type: journal_article
volume: 25
year: '2012'
...