--- _id: '3222' abstract: - lang: eng text: |- Parallel repetition is well known to reduce the error probability at an exponential rate for single- and multi-prover interactive proofs. Bellare, Impagliazzo and Naor (1997) show that this is also true for protocols where the soundness only holds against computationally bounded provers (e.g. interactive arguments) if the protocol has at most three rounds. On the other hand, for four rounds they give a protocol where this is no longer the case: the error probability does not decrease below some constant even if the protocol is repeated a polynomial number of times. Unfortunately, this protocol is not very convincing as the communication complexity of each instance of the protocol grows linearly with the number of repetitions, and for such protocols the error does not even decrease for some types of interactive proofs. Noticing this, Bellare et al. construct (a quite artificial) oracle relative to which a four round protocol exists whose communication complexity does not depend on the number of parallel repetitions. This shows that there is no “black-box” error reduction theorem for four round protocols. In this paper we give the first computationally sound protocol where k-fold parallel repetition does not decrease the error probability below some constant for any polynomial k (and where the communication complexity does not depend on k). The protocol has eight rounds and uses the universal arguments of Barak and Goldreich (2001). We also give another four round protocol relative to an oracle, unlike the artificial oracle of Bellare et al., we just need a generic group. This group can then potentially be instantiated with some real group satisfying some well defined hardness assumptions (we do not know of any candidate for such a group at the moment). alternative_title: - LNCS 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. In: Vol 4392. Springer; 2007:86-102. doi:10.1007/978-3-540-70936-7_5' apa: 'Pietrzak, K. Z., & Wikström, D. (2007). Parallel repetition of computationally sound protocols revisited (Vol. 4392, pp. 86–102). Presented at the TCC: Theory of Cryptography Conference, Springer. https://doi.org/10.1007/978-3-540-70936-7_5' chicago: Pietrzak, Krzysztof Z, and Douglas Wikström. “Parallel Repetition of Computationally Sound Protocols Revisited,” 4392:86–102. Springer, 2007. https://doi.org/10.1007/978-3-540-70936-7_5. ieee: 'K. Z. Pietrzak and D. Wikström, “Parallel repetition of computationally sound protocols revisited,” presented at the TCC: Theory of Cryptography Conference, 2007, vol. 4392, pp. 86–102.' ista: 'Pietrzak KZ, Wikström D. 2007. Parallel repetition of computationally sound protocols revisited. TCC: Theory of Cryptography Conference, LNCS, vol. 4392, 86–102.' mla: Pietrzak, Krzysztof Z., and Douglas Wikström. Parallel Repetition of Computationally Sound Protocols Revisited. Vol. 4392, Springer, 2007, pp. 86–102, doi:10.1007/978-3-540-70936-7_5. short: K.Z. Pietrzak, D. Wikström, in:, Springer, 2007, pp. 86–102. conference: name: 'TCC: Theory of Cryptography Conference' date_created: 2018-12-11T12:02:06Z date_published: 2007-03-22T00:00:00Z date_updated: 2021-01-12T07:41:54Z day: '22' doi: 10.1007/978-3-540-70936-7_5 extern: 1 intvolume: ' 4392' month: '03' page: 86 - 102 publication_status: published publisher: Springer publist_id: '3457' quality_controlled: 0 status: public title: Parallel repetition of computationally sound protocols revisited type: conference volume: 4392 year: '2007' ...