Ran Canetti
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.
- {BPW04} M. Backes, B. Pfitzmann, and M. Waidner. Secure Asynchronous Reactive Systems. Eprint archive, http://eprint.iacr.org/2004/082, March 2004.Google Scholar
- {B+05} B. Barak, R. Canetti, Y. Lindell, R. Pass and T. Rabin. Secure Computation Without Authentication. In Crypto'05, 2005. Google ScholarDigital Library
- {B91} D. Beaver. Secure Multi-party Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority. J. Cryptology, (1991) 4: 75--122.Google Scholar
- {BCG93} M. Ben-Or, R. Canetti and O. Goldreich. Asynchronous Secure Computations. 25th Symposium on Theory of Computing (STOC), ACM, 1993, pp. 52--61. Google ScholarDigital Library
- {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 ScholarDigital Library
- {B82} M. Blum. Coin flipping by telephone. IEEE Spring COMPCOM, pp. 133--137, Feb. 1982.Google Scholar
- {BCC88} G. Brassard, D. Chaum and C. Crépeau. Minimum Disclosure Proofs of Knowledge. JCSS, Vol. 37, No. 2, pages 156--189, 1988. Google ScholarDigital Library
- {C00} R. Canetti. Security and composition of multi-party cryptographic protocols. Journal of Cryptology, Vol. 13, No. 1, winter 2000.Google Scholar
- {C01} R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. (Earlier version of the present work.) Available at http://eccc.uni-trier.de/eccc-reports/2001/TR01-016/revision01.ps. Extended abstract in 42nd FOCS, 2001. Google ScholarDigital Library
- {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.Google ScholarCross Ref
- {CF01} R. Canetti and M. Fischlin. Universally Composable Commitments. Crypto '01, 2001.Google Scholar
- {CLOS02} R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai. Universally composable two-party and multi-party secure computation. 34th STOC, pp. 494--503, 2002. Google ScholarDigital Library
- {CGKS95} B. Chor, O. Goldreich, E. Kushilevitz, M. Sudan. Private Information Retrieval. 36th FOCS, 1995, pp. 41--50. Google ScholarDigital Library
- {DM00} Y. Dodis and S. Micali. Secure Computation. CRYPTO '00, 2000.Google Scholar
- {G01} O. Goldreich. Foundations of Cryptography. Cambridge Press, Vol 1 (2001) and Vol 2 (2004). NP. Google ScholarDigital Library
- {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 ScholarDigital Library
- {GL90} S. Goldwasser, and L. Levin. Fair Computation of General Functions in Presence of Immoral Majority. CRYPTO '90, LNCS 537, 1990.Google ScholarDigital Library
- {GM84} S. Goldwasser and S. Micali. Probabilistic encryption. JCSS, Vol. 28, No 2, April 1984, pp. 270--299.Google ScholarCross Ref
- {GMRa89} S. Goldwasser, S. Micali and C. Rackoff. The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Comput., Vol. 18, No. 1, 1989, pp. 186--208. Google ScholarDigital Library
- {HM00} M. Hirt and U. Maurer. Complete characterization of adversaries tolerable in secure multi-party computation. Journal of Cryptology, Vol 13, No. 1, 2000, pp. 31--60. Preliminary version in 16th Symp. on Principles of Distributed Computing (PODC), ACM, 1997, pp. 25--34. Google ScholarDigital Library
- {H85} C. A. R. Hoare. Communicating Sequential Processes. International Series in Computer Science, Prentice Hall, 1985. Google ScholarDigital Library
- {LMMS98} P. Lincoln, J. Mitchell, M. Mitchell, A. Scedrov. A Probabilistic Poly-time Framework for Protocol Analysis. 5th ACM Conf. on Computer and Communication Security, 1998, pp. 112--121. Google ScholarDigital Library
- {LY96} N. Lynch. Distributed Algorithms. Morgan Kaufman, San Francisco, 1996. Google ScholarDigital Library
- {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.Google Scholar
- {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.Google ScholarCross Ref
- {MR91} S. Micali and P. Rogaway. Secure Computation. unpublished manuscript, 1992. Preliminary version in CRYPTO '91. LNCS 576, 1991.Google Scholar
- {M89} R. Milner. Communication and Concurrency. Prentice Hall, 1989. Google ScholarDigital Library
- {M99} R. Milner. Communicating and Mobile Systems: the Pi-Calculus. Cambridge University Press, 1999. Google ScholarDigital Library
- {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).Google Scholar
- {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.Google Scholar
- {PW00} B. Pfitzmann and M. Waidner. Composition and integrity preservation of secure reactive systems. 7th ACM Conf. on Computer and Communication Security, 2000, pp. 245--254. Google ScholarDigital Library
- {PW01} B. Pfitzmann and M. Waidner. A model for asynchronous reactive systems and its application to secure message transmission. IEEE Symposium on Security and Privacy, May 2001. Preliminary version in http://eprint.iacr.org/2000/066 and IBM Research Report RZ 3304 (#93350), IBM Research, Zurich, December 2000. Google ScholarDigital Library
- {RB89} T. Rabin and M. Ben-Or. Verifiable Secret Sharing and Multi-party Protocols with Honest Majority. 21st Symposium on Theory of Computing (STOC), ACM, 1989, pp. 73--85. Google ScholarDigital Library
- {Y82A} A. Yao. Protocols for Secure Computation. In Proc. 23rd Annual Symp. on Foundations of Computer Science (FOCS), pages 160--164. IEEE, 1982.Google Scholar
- {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
Index Terms
- Security and composition of cryptographic protocols: a tutorial (part I)
Recommendations
Security and Composition of Multiparty Cryptographic Protocols
We present general definitions of security for multiparty cryptographic protocols, with focus on the task of evaluating a probabilistic function of the parties' inputs. We show that, with respect to these definitions, security is preserved under a ...
Stateless Cryptographic Protocols
FOCS '11: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer ScienceSecure computation protocols inherently involve multiple rounds of interaction among the parties where, typically a party has to keep a state about what has happened in the protocol so far and then \emph{wait} for the other party to respond. We study if ...
Resource Fairness and Composability of Cryptographic Protocols
We introduce the notion of resource-fair protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to ...
Comments