Advertisement

On Adaptive vs. Non-adaptive Security of Multiparty Protocols

  • Ran Canetti
  • Ivan Damgaard
  • Stefan Dziembowski
  • Yuval Ishai
  • Tal Malkin
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)

Abstract

Security analysis of multiparty cryptographic protocols distinguishes between two types of adversarialsettings: In the non-adaptive setting, the set of corrupted parties is chosen in advance, before the interaction begins. In the adaptive setting, the adversary chooses who to corrupt during the course of the computation. We study the relations between adaptive security (i.e., security in the adaptive setting) and non-adaptive security, according to two definitions and in several models of computation. While affirming some prevailing beliefs, we also obtain some unexpected results. Some highlights of our results are:
  • - According to the definition of Dodis-Micali-Rogaway (which is set in the information-theoretic model), adaptive and non-adaptive security are equivalent. This holds for both honest-but-curious and Byzantine adversaries, and for any number of parties.

  • - According to the definition of Canetti, for honest-but-curious adversaries, adaptive security is equivalent to non-adaptive security when the number of parties is logarithmic, and is strictly stronger than non-adaptive security when the number of parties is super-logarithmic. For Byzantine adversaries, adaptive security is strictly stronger than non-adaptive security, for any number of parties.

Keywords

Commitment Scheme Auxiliary Input Computational Security Adversary Structure Corrupted Party 
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. B91._D. Beaver, “Secure Multi-party Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority”, J. Cryptology, Springer-Verlag, (1991) 4: 75–122.zbMATHCrossRefGoogle Scholar
  2. B97._D. Beaver, “Plug and Play Encryption”, CRYPTO 97.Google Scholar
  3. BH92._D. Beaver and S. Haber, “Cryptographic Protocols Provably secure Against Dynamic Adversaries”, Eurocrypt, 1992.Google Scholar
  4. BGW88._M. Ben-Or, S. Goldwasser and A. Wigderson, “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation”, 20th Symposium on Theory of Computing (STOC), ACM, 1988, pp. 1–10.Google Scholar
  5. C00._R. Canetti, “Security and Composition of Multiparty Cryptographic Protocols”, Journal of Cryptology, Vol. 13, No. 1, Winter 2000. On-line version at http://philby.ucsd.edu/cryptolib/1998/98-18.html.
  6. C00a._R. Canetti, “A unified framework for analyzing security of Protocols”, manuscript, 2000. Available at http://eprint.iacr.org/2000/067.
  7. CDDIM01._R. Canetti, I. Damgaard, S. Dziembowski, Y. Ishai and T. Malkin, “On adaptive vs. non-adaptive security of multiparty protocols”, http://eprint.iacr.org/2001.
  8. CFGN96._R. Canetti, U. Feige, O. Goldreich and M. Naor, “Adaptively Secure Computation”, 28th Symposium on Theory of Computing (STOC), ACM, 1996. Fuller version in MIT-LCS-TR #682, 1996.Google Scholar
  9. CDM98._R. Cramer, I. Damgaard and U. Maurer: General Secure Multiparty Computation from Any Linear Secret-Sharing Scheme, EuroCrypt 2000.Google Scholar
  10. CCD88._D. Chaum, C. Crepeau, and I. Damgaard. Multi-party Unconditionally Secure Protocols. In Proc. 20th Annual Symp. on the Theory of Computing (STOC), pages 11–19, ACM, 1988.Google Scholar
  11. CS98._R. Cramer and V. Shoup, “A paractical public-key cryptosystem provably secure against adaptive chosen ciphertext attack”, CRYPTO '98, 1998.Google Scholar
  12. DN00._I. Damgaard and J. Nielsen, “Improved non-committing encryption schemes based on a generalcompl exity assumption”, CRYPTO 2000.Google Scholar
  13. DM00._Y. Dodis and S. Micali, “Parallel Reducibility for Information-Theoretically Secure Computation”, CRYPTO 2000.Google Scholar
  14. DDN91._D. Dolev, C. Dwork and M. Naor, “Non-malleable cryptography”, SICOMP, to appear. Preliminary version in STOC 91.Google Scholar
  15. GMW87._O. Goldreich, S. Micali and A. Wigderson, “How to Play any Mental Game”, 19th Symposium on Theory of Computing (STOC), ACM, 1987, pp. 218–229.Google Scholar
  16. GL90._S. Goldwasser, and L. Levin, “Fair Computation of General Functions in Presence of Immoral Majority”, CRYPTO '90, LNCS 537, Springer-Verlag, 1990.Google Scholar
  17. GM84._S. Goldwasser and S. Micali, “Probabilistic encryption”, JCSS, Vol. 28, No 2, April 1984, pp. 270–299.zbMATHMathSciNetGoogle Scholar
  18. MR91._S. Micali and P. Rogaway, “Secure Computation”, unpublished manuscript, 1992. Preliminary version in CRYPTO '91, LNCS 576, Springer-Verlag, 1991.Google Scholar
  19. PW94._B. Pfitzmann and M. Waidner, “A General Framework for Formal Notions of Secure Systems”, Hildesheimer Informatik-Berichte, ISSN 0941-3014, April 1994.Google Scholar
  20. PSW00._B. Pfitzmann, M. Schunter and M. Waidner, “Secure Reactive Systems”, IBM Technical report RZ 3206 (93252), May 2000.Google Scholar
  21. S99._A. Sahai, “Non malleable, non-interactive zero knowlege and adaptive chosen ciphertext security”, FOCS 99.Google Scholar
  22. Y82._A. Yao, “Protocols for Secure Computation”, In Proc. 23rd Annual Symp. on Foundations of Computer Science (FOCS), pages 160–164. IEEE, 1982.Google Scholar
  23. Y86._A. Yao, “How to generate and exchange secrets”, In Proc. 27th Annual Symp. on Foundations of Computer Science (FOCS), pages 162–167. IEEE, 1986.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Ran Canetti
    • 1
  • Ivan Damgaard
    • 2
  • Stefan Dziembowski
    • 2
  • Yuval Ishai
    • 3
  • Tal Malkin
    • 4
  1. 1.IBM WatsonUSA
  2. 2.BRICSAarhus UniversityAarhusDenmark
  3. 3.DIMACS and AT&T.USA
  4. 4.AT&T Labs - ResearchUSA

Personalised recommendations