An efficient parallel repetition theorem for Arthur-Merlin games

ABSTRACT

We show a parallel-repetition theorem for constant-round Arthur-Merlin Games, using an efficient reduction. As a consequence, we show that parallel repetition reduces the soundness-error at an optimal rate (up to a negligible factor) in constant-round public-coin argument systems, and constant-round public-coinproofs of knowledge. The former of these results resolves an open questionposed by Bellare, Impagliazzo and Naor (FOCS '97).

REFERENCES

• 1: László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
• 2: Mihir Bellare , Russell Impagliazzo , Moni Naor, Does Parallel Repetition Lower the Error in Computationally Sound Protocols?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.374, October 19-22, 1997
• 3: Mihir Bellare , Oded Goldreich, On Defining Proofs of Knowledge, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.390-420, August 16-20, 1992
• 4: [4] M. Blum. How to prove a Theorem So No One Else Can Claim It. Proc. of the International Congress of Mathematicians, Berkeley, California, USA, pages 1444-1451, 1986.
• 5: Gilles Brassard , David Chaum , Claude Crépeau, Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences, v.37 n.2, p.156-189, October 1988 [doi>10.1016/0022-0000(88)90005-0]
• 6: [6] R. Canetti and S. Halevi and M. Steiner. Hardness Amplification of Weakly Verifiable Puzzles. In 2nd TCC, Springer LNCS 3876, pages 17-33, 2005.
• 7: [7] O. Goldreich and R. Impagliazzo and L. A. Levin and R. Venkatesan and D. Zuckerman. Security Preserving Amplification of Hardness. In 31th FOCS, pages 318-326, 1990.
• 8: Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62223]
• 9: U. Feige , A. Fiat , A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, v.1 n.2, p.77-94, Aug. 1988 [doi>10.1007/BF02351717]
• 10: Uri Feige , Joe Kilian, Two prover protocols: low error at affordable rates, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.172-183, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195128]
• 11: Lance Fortnow , John Rompel , Michael Sipser, On the power of multi-prover interactive protocols, Theoretical Computer Science, v.134 n.2, p.545-557, Nov. 21, 1994 [doi>10.1016/0304-3975(94)90251-8]
• 12: Uriel Feige , Adi Shamir, Zero Knowledge Proofs of Knowledge in Two Rounds, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.526-544, August 20-24, 1989
• 13: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 14: Oded Goldreich , Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM Journal on Computing, v.25 n.1, p.169-192, Feb. 1996 [doi>10.1137/S0097539791220688]
• 15: [15] S. Goldwasser and S. Micali. Probabilistic Encryption. JCSS, Vol. 28, No 2, pages 270-299, 1984.
• 16: S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
• 17: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 18: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 19: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 20: [20] K. Pietrzak and D. Wikström. Parallel Repetition of Computationally Sound Protocols Revisited. To appear in TCC 2007.
• 21: [21] R. Richardson and J. Kilian. On the Concurrent Composition of Zero-Knowledge Proofs. Eurocrypt 99, Springer LNCS 1592, pages 415-431, 1999.
• 22: Ran Raz, A parallel repetition theorem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.447-456, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225181]
• 23: [23] M. Tompa, H. Woll. Random Self-Reducibility and Zero Knowledge Interactive Proofs of Possession of Information. In 28th FOCS, pages 472-482, 1987.
• 24: [24] A. Yao. Theory and Applications of Trapdoor Functions. In 23th FOCS, pages 80-91, 1982.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

General Terms:
Theory

Keywords:
Arthur-Merlin games, computationally-sound arguments, parallel repetition, proofs of knowledge, public-coin protocols