Rafael Pass
Skip Abstract Section
Abstract
We show a parallel-repetition theorem for constant-round Arthur-Merlin Proofs, 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-coin proofs of knowledge. The first of these results resolves an open question posed by Bellare, Impagliazzo, and Naor (FOCS’97).
- Babai, L. and Moran, S. 1988. Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity class. J. Comput. Syst. Sci. 36, 2, 254--276. Google Scholar
Digital Library
- Bellare, M. and Goldreich, O. 1992. On defining proofs of knowledge. In Proceedings of CRYPTO. 390--420. Google ScholarDigital Library
- Bellare, M., Impagliazzo, R., and Naor, M. 1997. Does parallel repetition lower the error in computationally sound protocols? In Proceedings of Foundations of Computer Science. 374--383. Google ScholarDigital Library
- Ben-Or, M., Goldwasser, S., Kilian, J., and Wigderson, A. 1988. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of Symposium on Theory of Computing. 113--131. Google ScholarDigital Library
- Blum, M. 1986. How to prove a theorem so no one else can claim it. In Proceedings of the International Congress of Mathematicians.Google Scholar
- Brassard, G., Chaum, D., and Crépeau, C. 1988. Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37, 2, 156--189. Google ScholarDigital Library
- Canetti, R., Halevi, S., and Steiner, M. 2005. Hardness amplification of weakly verifiable puzzles. In Proceedings of Theory of Cryptography Conference. 17--33. Google ScholarDigital Library
- Chung, K.-M. and Liu, F.-H. 2010. Parallel repetition theorems for interactive arguments. In Proceedings of Theory of Cryptography Conference. 19--36. Google ScholarDigital Library
- Chung, K.-M., Liu, F.-H., Lu, C.-J., and Yang, B.-Y. 2010. Efficient string-commitment from weak bit-commitment. In Proceedings of ASIACRYPT. 268--282.Google Scholar
- Feige, U. and Kilian, J. 2000. Two-prover protocols - low error at affordable rates. SIAM J. Comput. 30, 1, 324--346. Google ScholarDigital Library
- Feige, U. and Shamir, A. 1989. Zero knowledge proofs of knowledge in two rounds. In Proceedings of CRYPTO. 526--544. Google ScholarDigital Library
- Feige, U., Fiat, A., and Shamir, A. 1988. Zero-knowledge proofs of identity. J. Cryptol. 1, 2, 77--94. Google ScholarDigital Library
- Fortnow, L., Rompel, J., and Sipser, M. 1994. On the power of multi-prover interactive protocols. Theoret. Comput. Sci. 134, 2, 545--557. Google ScholarDigital Library
- Goldreich, O. 1998. Modern Cryptography, Probabilistic Proofs, and Pseudorandomness. Springer-Verlag New York, Secaucus, NJ. Google ScholarDigital Library
- Goldreich, O. 2001. Foundations of Cryptography---Basic Tools. Cambridge University Press. Google ScholarDigital Library
- Goldreich, O. and Krawczyk, H. 1996. On the composition of zero-knowledge proof systems. SIAM J. Comput. 25, 1, 169--192. Google ScholarDigital Library
- Goldreich, O., Impagliazzo, R., Levin, L. A., Venkatesan, R., and Zuckerman, D. 1990. Security preserving amplification of hardness. In Proceedings of Foundations of Computer Science. 318--326. Google ScholarDigital Library
- Goldreich, O., Micali, S., and Wigderson, A. 1991. Proofs that yield nothing but their validity for all languages in np have zero-knowledge proof systems. J. ACM 38, 3, 691--729. Google ScholarDigital Library
- Goldwasser, S. and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2, 270--299.Google ScholarCross Ref
- Goldwasser, S., Micali, S., and Rivest, R. L. 1988. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17, 2, 281--308. Google ScholarDigital Library
- Goldwasser, S., Micali, S., and Rackoff, C. 1989. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 1, 186--208. Google ScholarDigital Library
- Haitner, I. 2009. A parallel repetition theorem for any interactive argument. In Proceedings of Foundations of Computer Science. 241--250. Google ScholarDigital Library
- Håstad, J., Pass, R., Wikström, D., and Pietrzak, K. 2010. An efficient parallel repetition theorem. In Proceedings of Theory of Cryptography Conference. 1--18. Google ScholarDigital Library
- Holenstein, T. and Schoenebeck, G. 2011. General hardness amplification of predicates and puzzles - (extended abstract). In Proceedings of TCC. 19--36. Google ScholarDigital Library
- Impagliazzo, R., Jaiswal, R., and Kabanets, V. 2007. Chernoff-type direct product theorems. In Proceedings of CRYPTO. 500--516. Google ScholarDigital Library
- Jutla, C. S. 2010. Almost optimal bounds for direct product threshold theorem. In Proceedings of TCC. 37--51. Google ScholarDigital Library
- Pandey, O., Pass, R., and Vaikuntanathan, V. 2008. Adaptive one-way functions and applications. In Proceedings of CRYPTO. 57--74. Google ScholarDigital Library
- Pass, R. and Venkitasubramaniam, M. 2007. An efficient parallel repetition theorem for Arthur-Merlin games. In Proceedings of Symposium on Theory of Computing. 420--429. Google ScholarDigital Library
- Pass, R., Tseng, W.-L. D., and Wikström, D. 2009. On the composition of public-coin zero-knowledge protocols. In Proceedings of CRYPTO. 160--176. Google ScholarDigital Library
- Pietrzak, K. and Wikström, D. 2007. Parallel repetition of computationally sound protocols revisited. In Proceedings of Theory of Cryptography Conference. 86--102. Google ScholarDigital Library
- Raz, R. 1998. A parallel repetition theorem. SIAM J. Comput. 27, 3, 763--803. Google ScholarDigital Library
- Richardson, R. and Kilian, J. 1999. On the concurrent composition of zero-knowledge proofs. In Proceedings of Eurocrypt. 415--432. Google ScholarDigital Library
- Tompa, M. and Woll, H. 1987. Random self-reducibility and zero knowledge interactive proofs of possession of information. In Proceedings of Foundations of Computer Science. 472--482. Google ScholarDigital Library
- Xiao, D. 2011. (Nearly) round-optimal black-box constructions of commitments secure against selective opening attacks. In Proceedings of 8th TCC. 541--558. Google ScholarDigital Library
- Yao, A. C.-C. 1982. Theory and applications of trapdoor functions (extended abstract). In Proceedings of Foundations of Computer Science. 80--91. Google ScholarCross Ref
Index Terms
- A Parallel Repetition Theorem for Constant-Round Arthur-Merlin Proofs
Recommendations
An efficient parallel repetition theorem for Arthur-Merlin games
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computingWe 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 ...
Constant-round adaptive zero-knowledge proofs for NP
Secure two-party computation allows two parties with private inputs to securely compute some function of their inputs, even in the presence of a malicious adversary. In this work, we revisit zero-knowledge proofs and focus on adaptive adversaries, which ...
Constant-round interactive proofs for delegating computation
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of ComputingThe celebrated IP=PSPACE Theorem of Lund et-al. (J.ACM 1992) and Shamir (J.ACM 1992), allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be ...
Comments