Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Parallel Repetition Theorems for Interactive Arguments

  • Conference paper

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

Included in the following conference series:

  • 2003Accesses

Abstract

We study efficient parallel repetition theorems for several classes of interactive arguments and obtain the following results:

  1. 1

    We show atight parallel repetition theorem for public-coin interactive arguments by giving a tight analysis for a reduction algorithm of Håstad et al. [HPPW08]. That is,n-fold parallel repetition decreases the soundness error fromδ toδn. The crux of our improvement is a new analysis that avoid using Raz’s Sampling Lemma, which is the key ingredient to the previous results.

  2. 1

    We give a new security analysis to strengthen a parallel repetition theorem of Håstad et al. for a more general class of arguments. We show thatn-fold parallel repetition decreases the soundness error fromδ toδn/2, which is almost tight. In particular, we remove the dependency on the number of rounds in the bound, and as a consequence, extend the “concurrent” repetition theorem of Wikström [Wik09] to this model.

  3. 1

    We obtain a way to turnany interactive argument to one in the class above using fully homomorphic encryption schemes. This gives a way to amplify the soundness of any interactive argument without increasing the round complexity.

  4. 1

    We give a simple and generic transformation which shows that tight direct product theorems imply almost-tight Chernoff-type theorems. This extends our results to Chernoff-type theorems, and gives an alternative proof to the Chernoff-type theorem of Impagliazzo et al. [IJK09] for weakly-verifiable puzzles.

A full version of this paper can be found on [CL09].

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

References

  1. Bellare, M., Impagliazzo, R., Naor, M.: Does parallel repetition lower the error in computationally sound protocols? In: FOCS, pp. 374–383 (1997)

    Google Scholar 

  2. 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 

  3. Chung, K.-M., Liu, F.-H.: Parallel repetition theorems for interactive arguments. Electronic Colloquium on Computational Complexity (ECCC) (109) (2009),http://eccc.uni-trier.de/report/2009/109/

  4. Chung, K.-M., Liu, F.-H., Lu, C.-J., Yang, B.-Y.: Efficient string-commitment from weak bit-commitment and full-spectrum theorem for puzzles (2009) (unpublished manuscript)

    Google Scholar 

  5. Durrett, R.: Probability: Theorey and Examples, 3rd edn. Duxbury (2004)

    Google Scholar 

  6. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169–178 (2009)

    Google Scholar 

  7. Haitner, I.: A parallel repetition theorem for any interactive argument. In: FOCS (2009)

    Google Scholar 

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

    Google Scholar 

  9. Håstad, J., Pass, R., Wikström, D., Pietrzak, K.: An efficient parallel repetition theorem. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 1–18. Springer, Heidelberg (2010)

    Google Scholar 

  10. Holenstein, T., Schoenebeck, G.: General hardness amplification of predicates and puzzles (2009) (unpublished manuscript)

    Google Scholar 

  11. Impagliazzo, R., Jaiswal, R., Kabanets, V.: Chernoff-type direct product theorems. J. Cryptology 22(1), 75–92 (2009)

    Article MathSciNet MATH  Google Scholar 

  12. Pass, R., Venkitasubramaniam, M.: An efficient parallel repetition theorem for arthur-merlin games. In: STOC, pp. 420–429 (2007)

    Google Scholar 

  13. 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 

  14. Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763–803 (1998)

    Article MathSciNet MATH  Google Scholar 

  15. Wikström, D.: An efficient concurrent repetition theorem. Cryptology ePrint Archive, Report 2009/347 (2009)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Engineering & Applied Sciences, Harvard University, Cambridge, MA, USA

    Kai-Min Chung

  2. Department of Computer Science, Brown University, Providence RI, USA

    Feng-Hao Liu

Authors
  1. Kai-Min Chung

    You can also search for this author inPubMed Google Scholar

  2. Feng-Hao Liu

    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

Chung, KM., Liu, FH. (2010). Parallel Repetition Theorems for Interactive Arguments. 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_2

Download citation

Publish with us

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