Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

An Efficient Parallel Repetition Theorem

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 5978))

Included in the following conference series:

  • 2062Accesses

Abstract

We present a general parallel-repetition theorem with an efficient reduction. As a corollary of this theorem we establish that parallel repetition reduces the soundness error at an exponential rate in any public-coin argument, and more generally, any argument where the verifier’s messages, but not necessarily its decision to accept or reject, can be efficiently simulated with noticeable probability.

The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI:10.1007/978-3-642-11799-2_36

Similar content being viewed by others

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. Babai, L.: Trading group theory for randomness. In: 17th ACM Symposium on the Theory of Computing (STOC), pp. 421–429. ACM Press, New York (1985)

    Google Scholar 

  2. Bellare, M., Impagliazzo, R., Naor, M.: Does parallel repetition lower the error in computationally sound protocols? In: 38th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 374–383. IEEE Computer Society Press, Los Alamitos (1997)

    Google Scholar 

  3. Brassard, G., Chaum, D., Crépeau, C.: Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences 37(2), 156–189 (1988)

    Article MathSciNet MATH  Google Scholar 

  4. Canetti, R., Halevi, S., Steiner, M.: Hardness amplification of weakly verifiable puzzles. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 17–33. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  5. Chung, K.-M., Liu, F.-H.: Parallel repetition theorems for interactive arguments. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 19–36. Springer, Heidelberg (2010)

    Google Scholar 

  6. Goldreich, O.: Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Algorithms and Combinatorics. Springer, Heidelberg (1998)

    Google Scholar 

  7. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1), 186–208 (1989)

    Article MathSciNet MATH  Google Scholar 

  8. Haitner, I.: A parallel repetition theorem for any interactive argument. In: 50th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos (2009)

    Google Scholar 

  9. Håstad, J., Pass, R., Pietrzak, Wikström, D.: An efficient parallel repetition theorem (April 2008) (manuscript)

    Google Scholar 

  10. Holenstein, T.: Parallel repetition: simplifications and the no-signaling case. In: 39th ACM Symposium on the Theory of Computing (STOC), pp. 411–419. ACM, New York (2007)

    Google Scholar 

  11. Impagliazzo, R., Jaiswal, R., Kabanets, V.: Chernoff-type direct product theorems. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 500–516. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  12. Pass, R., Tseng, D., Wikström, D.: On the composition of public-coin zero-knowledge protocols. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 160–176. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  13. Pass, R., Venkitasubramaniam, M.: An efficient parallel repetition theorem for arthur-merlin games. In: 39th ACM Symposium on the Theory of Computing (STOC), pp. 420–429. ACM, New York (2007)

    Google Scholar 

  14. Pietrzak, K., Wikström, D.: Parallel repetition of computationally sound protocols revisited. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 86–102. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  15. Raz, R.: A parallel repetition theorem. SIAM Journal on Computing 27(3), 763–803 (1998)

    Article MathSciNet MATH  Google Scholar 

  16. Wikström, D.: An efficient concurrent repetition theorem (2009),http://eprint.iacr.org/

  17. Yao, A.C.: Theory and application of trapdoor functions. In: 23rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 80–91. IEEE Computer Society Press, Los Alamitos (1982)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. KTH, Stockholm, supported by ERC grant 226-203, Sweden

    Johan Håstad

  2. Cornell University, Ithaca, supported in part by a Microsoft New Faculty Fellowship, NSF CAREER Award CCF-0746990, AFOSR Award FA9550-08-1-0197, and BSF Grant 2006317, USA

    Rafael Pass

  3. KTH, Stockholm

    Douglas Wikström

  4. CWI, Amsterdam

    Krzysztof Pietrzak

Authors
  1. Johan Håstad

    You can also search for this author inPubMed Google Scholar

  2. Rafael Pass

    You can also search for this author inPubMed Google Scholar

  3. Douglas Wikström

    You can also search for this author inPubMed Google Scholar

  4. Krzysztof Pietrzak

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Computer Science & Engineering Department, University of California,, 9500 Gilman Drive, La Jolla, 92093-5004, San Diego, CA, USA

    Daniele Micciancio

Rights and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Håstad, J., Pass, R., Wikström, D., Pietrzak, K. (2010). An Efficient Parallel Repetition Theorem. In: Micciancio, D. (eds) Theory of Cryptography. TCC 2010. Lecture Notes in Computer Science, vol 5978. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11799-2_1

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp