Security and composition of cryptographic protocols: a tutorial (part I)

ABSTRACT

What does it mean for a cryptographic protocol to be "secure"? Capturing the security requirements of cryptographic tasks in a meaningful way is a slippery business: On the one hand, we want security criteria that prevent "all potential attacks" against a protocol; on the other hand, we want our criteria not to be overly restrictive and accept "reasonable protocols". One of the main reasons for flaws is the often unexpected interactions among different protocol instances that run alongside each other in a composite system.This tutorial studies a general methodology for defining security of cryptographic protocols. The methodology, often dubbed the "trusted party paradigm", allows for defining the security requirements of a large variety of cryptographic tasks in a unified and natural way. We first review more basic formulations that capture security in isolation from other protocol instances. Next we address the security problems associated with protocol composition, and review formulations that guarantee security even in composite systems.

REFERENCES

• 1: {BPW04} M. Backes, B. Pfitzmann, and M. Waidner. Secure Asynchronous Reactive Systems. Eprint archive, http://eprint.iacr.org/2004/082, March 2004.
• 2: {B+05} B. Barak, R. Canetti, Y. Lindell, R. Pass and T. Rabin. Secure Computation Without Authentication. In Crypto'05, 2005.
• 3: {B91} D. Beaver. Secure Multi-party Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority. J. Cryptology, (1991) 4: 75--122.
• 4: Michael Ben-Or , Ran Canetti , Oded Goldreich, Asynchronous secure computation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.52-61, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167109]
• 5: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 6: {B82} M. Blum. Coin flipping by telephone. IEEE Spring COMPCOM, pp. 133--137, Feb. 1982.
• 7: 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]
• 8: {C00} R. Canetti. Security and composition of multi-party cryptographic protocols. Journal of Cryptology, Vol. 13, No. 1, winter 2000.
• 9: R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001
• 10: {C+06} R. Canetti, L. Cheung, D. Kaynar, M. Liskov, N. Lynch, O. Pereira, and R. Segala. Task-Structured Probabilistic I/O Automata. In Workshop on discrete event systems (WODES), 2006.
• 11: {CF01} R. Canetti and M. Fischlin. Universally Composable Commitments. Crypto '01, 2001.
• 12: Ran Canetti , Yehuda Lindell , Rafail Ostrovsky , Amit Sahai, Universally composable two-party and multi-party secure computation, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509980]
• 13: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
• 14: {DM00} Y. Dodis and S. Micali. Secure Computation. CRYPTO '00, 2000.
• 15: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 16: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 17: {GL90} S. Goldwasser, and L. Levin. Fair Computation of General Functions in Presence of Immoral Majority. CRYPTO '90, LNCS 537, 1990.
• 18: {GM84} S. Goldwasser and S. Micali. Probabilistic encryption. JCSS, Vol. 28, No 2, April 1984, pp. 270--299.
• 19: 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]
• 20: Martin Hirt , Ueli Maurer, Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.25-34, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259412]
• 21: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 22: P. Lincoln , J. Mitchell , M. Mitchell , A. Scedrov, A probabilistic poly-time framework for protocol analysis, Proceedings of the 5th ACM conference on Computer and communications security, p.112-121, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288117]
• 23: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 24: {LSV03} N. Lynch, R. Segala and F. Vaandrager. Compositionality for Probabilistic Automata. 14th CONCUR, LNCS vol. 2761, pages 208--221, 2003. Fuller version appears in MIT Technical Report MITLCS-TR-907.
• 25: {MMS03} P. Mateus, J. C. Mitchell and A. Scedrov. Composition of Cryptographic Protocols in a Probabilistic Polynomial-Time Process Calculus. CONCUR, pp. 323--345, 2003.
• 26: {MR91} S. Micali and P. Rogaway. Secure Computation. unpublished manuscript, 1992. Preliminary version in CRYPTO '91. LNCS 576, 1991.
• 27: R. Milner, Communication and Concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 28: Robin Milner, Communicating and mobile systems: the &pgr;-calculus, Cambridge University Press, New York, NY, 1999
• 29: {MRST01} J. Mitchell, A. Ramanathan, A. Scedrov, V. Teague. A probabilistic polynomial-time calculus for analysis of cryptographic protocols (Preliminary report). 17-th Annual Conference on the Mathematical Foundations of Programming Semantics, Arhus, Denmark, May, 2001, ENTCS Vol. 45 (2001).
• 30: {PW94} B. Pfitzmann and M. Waidner. A general framework for formal notions of secure systems. Hildesheimer Informatik-Berichte 11/94, Universitat Hildesheim, 1994. Available at http://www.semper.org/sirene/lit.
• 31: Birgit Pfitzmann , Michael Waidner, Composition and integrity preservation of secure reactive systems, Proceedings of the 7th ACM conference on Computer and communications security, p.245-254, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352639]
• 32: Birgit Pfitzmann , Michael Waidner, A Model for Asynchronous Reactive Systems and its Application to Secure Message Transmission, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.184, May 14-16, 2001
• 33: T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
• 34: {Y82A} A. Yao. Protocols for Secure Computation. In Proc. 23rd Annual Symp. on Foundations of Computer Science (FOCS), pages 160--164. IEEE, 1982.
• 35: {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.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Design, Performance, Security