ACM SIGACT news distributed computing column 24

ABSTRACT

The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases, distributed shared memory, multiprocessor architectures, operating systems, verification, Internet, and the Web. This issue consists of:• "Security and Composition of Cryptographic Protocols: A Tutorial (Part II)" by Ran Canetti.The first part appeared in the previous SIGACT News, the September 2006 issue. Many thanks to Ran for his contributions to this column.

REFERENCES

• 1: Michael Backes , Birgit Pfitzmann , Michael Waidner, A composable cryptographic library with nested operations, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948140]
• 2: {BPW04} M. Backes, B. Pfitzmann, and M. Waidner. A general composition theorem for secure reactive systems. In 1st Theory of Cryptography Conference (TCC), LNCS 2951 pp. 336--354, Feb. 2004.
• 3: {B+05} B. Barak, R. Canetti, Y. Lindell, R. Pass and T. Rabin. Secure Computation Without Authentication. In Crypto'05, 2005.
• 4: Boaz Barak , Ran Canetti , Jesper Buus Nielsen , Rafael Pass, Universally Composable Protocols with Relaxed Set-Up Assumptions, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.186-195, October 17-19, 2004 [doi>10.1109/FOCS.2004.71]
• 5: Boaz Barak , Amit Sahai, How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.542-552, October 23-25, 2005 [doi>10.1109/SFCS.2005.43]
• 6: {B91} D. Beaver. Secure Multi-party Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority. J. Cryptology, (1991) 4: 75--122.
• 7: Mihir Bellare , Phillip Rogaway, Entity Authentication and Key Distribution, Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology, p.232-249, August 22-26, 1993
• 8: 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]
• 9: 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]
• 10: Michael Ben-Or , Boaz Kelmer , Tal Rabin, Asynchronous secure computations with optimal resilience (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.183-192, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198088]
• 11: 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]
• 12: {C95} R. Canetti. Studies in Secure Multi-party Computation and Applications. Ph.D. Thesis, Weizmann Institute, Israel, 1995.
• 13: {C00} R. Canetti. Security and composition of multi-party cryptographic protocols. J. Cryptology, Vol. 13, No. 1, winter 2000.
• 14: 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
• 15: Ran Canetti, Security and composition of cryptographic protocols: a tutorial (part I), ACM SIGACT News, v.37 n.3, September 2006 [doi>10.1145/1165555.1165570]
• 16: {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.
• 17: {C+06a} R. Canetti, L. Cheung, D. Kaynar, M. Liskov, N. Lynch, O. Pereira, and R. Segala. Time-Bounded Task-PIOAs: A Framework for Analyzing Security Protocols. In 20th symposium on distributed computing (DISC), 2006.
• 18: {CDPW07} R. Canetti, Y. Dodis, R. Pass and S. Walfish. Universally Composable Security with Pre-Existing Setup. 4th theory of Cryptology Conference (TCC), 2007.
• 19: Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238015]
• 20: {CF01} R. Canetti and M. Fischlin. Universally Composable Commitments. Crypto '01, 2001.
• 21: {CH04} R. Canetti and J. Herzog. Universally Composable Symbolic Analysis of Cryptographic Protocols (The case of encryption-based mutual authentication and key-exchange). Eprint archive, http://eprint.iacr.org/2004/334. Extended Abstract at 3rd TCC, 2006.
• 22: Ran Canetti , Hugo Krawczyk, Universally Composable Notions of Key Exchange and Secure Channels, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.337-351, May 02, 2002
• 23: Ran Canetti , Hugo Krawczyk, Security Analysis of IKE's Signature-Based Key-Exchange Protocol, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.143-161, August 18-22, 2002
• 24: {CKL03} R. Canetti, E. Kushilevitz, Y. Lindell. On the Limitations of Universally Composable Two-Party Computation without Set-up Assumptions. EUROCRYPT 2003, pp. 68--86, 2003. Extended version at the eprint archive, eprint.iacr.org/2004/116.
• 25: 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]
• 26: {CR03} R. Canetti and T. Rabin. Universal Composition with Joint State. Crypto'03, 2003.
• 27: {CKLP06} L. Cheung, D. Kaynar, N. Lynch, O. Pereira. Compositional Security for Task-PIOAs. Manuscript, 2006.
• 28: {DDMRS06} A. Datta, A. Derek, J. C. Mitchell, A. Ramanathan and A. Scedrov. Games and the Impossibility of Realizable Ideal Functionality. 3rd theory of Cryptology Conference (TCC), 2006.
• 29: {DKMR05} A. Datta, R. Küsters, J. C. Mitchell and A. Ramanathan. On the Relationships between Notions of Simulation-based Security. 2nd theory of Cryptology Conference (TCC), 2005.
• 30: {DM00} Y. Dodis and S. Micali. Secure Computation. CRYPTO '00, 2000.
• 31: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 32: {DY83} D. Dolev and A. Yao. On the security of public-key protocols. IEEE Transactions on Information Theory, 2(29), 1983.
• 33: {DLMS99} N. A. Durgin, P. D. Lincoln, J. C. Mitchell and A. Scedrov. Undecidability of bounded security protocols. Workshop on Formal Methods and Security Protocols (FMSP), 1999.:w
• 34: Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.409-418, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276853]
• 35: {EG82} S. Even and Oded Goldreich. On the Security of Multi-Party Ping-Pong Protocols. 24th FOCS, 1983.
• 36: {F91} U. Feige. Ph.D. thesis, Weizmann Institute of Science, 1991.
• 37: Rosario Gennaro , Michael O. Rabin , Tal Rabin, Simplified VSS and fast-track multiparty computations with applications to threshold cryptography, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.101-111, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277716]
• 38: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 39: Oded Goldreich , Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM Journal on Computing, v.25 n.1, p.169-192, Feb. 1996 [doi>10.1137/S0097539791220688]
• 40: 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]
• 41: {GO94} O. Goldreich and Y. Oren. Definitions and properties of Zero-Knowledge proof systems. J. Cryptology, Vol. 7, No. 1, 1994, pp. 1--32.
• 42: {GL90} S. Goldwasser, and L. Levin. Fair Computation of General Functions in Presence of Immoral Majority. CRYPTO '90, LNCS 537, 1990.
• 43: {GM84} S. Goldwasser and S. Micali. Probabilistic encryption. JCSS, Vol. 28, No 2, April 1984, pp. 270--299.
• 44: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 45: 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]
• 46: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 47: {HU05} D. Hofheinz and D. Unruh. Comparing Two Notions of Simulatability. 2nd theory of Cryptology Conference (TCC), pp. 86--103, 2005.
• 48: {IPSEC} The IPSec working group of the IETF. See http://www.ietf.org/html.charters/ipsec-charter.html
• 49: Eyal Kushilevitz , Yehuda Lindell , Tal Rabin, Information-theoretically secure protocols and security under composition, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132532]
• 50: Ralf Kusters, Simulation-Based Security with Inexhaustible Interactive Turing Machines, Proceedings of the 19th IEEE Workshop on Computer Security Foundations, p.309-320, July 05-07, 2006 [doi>10.1109/CSFW.2006.30]
• 51: Yehuda Lindell, General Composition and Universal Composability in Secure Multi-Party Computation, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.394, October 11-14, 2003
• 52: {L04} Y. Lindell. Lower Bounds for Concurrent Self Composition. 1st Theory of Cryptology Conference (TCC), pp. 203--222. 2004.
• 53: Yehuda Lindell , Anna Lysyanskaya , Tal Rabin, On the composition of authenticated byzantine agreement, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509982]
• 54: {LPT04} Y. Lindell, M. Prabhakaran, Y. Tauman. Concurrent General Composition of Secure Protocols in the Timing Model. Manuscript, 2004.
• 55: 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]
• 56: {LT89} N. Lynch and M. R. Tuttle. An introduction to input/output automata. CWIQuarterly, 2(3):219--246, September 1989.
• 57: {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 MIT-LCS-TR-907.
• 58: {MMY06} T. Malkin, R. Moriarty and N. Yakovenko. Generalized Environmental Secrity from Number Theoretic Assumptions. 3rd Theory of Cryptology Conference (TCC), 2006, pp. 343--359.
• 59: {MMS03} P. Mateus, J. C. Mitchell and A. Scedrov. Composition of Cryptographic Protocols in a Probabilistic Polynomial-Time Process Calculus. 14th CONCUR, pp. 323--345. 2003.
• 60: {MR91} S. Micali and P. Rogaway. Secure Computation. unpublished manuscript, 1992. Preliminary version in CRYPTO '91, LNCS 576, 1991.
• 61: R. Milner, Communication and Concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 62: Robin Milner, Communicating and mobile systems: the &pgr;-calculus, Cambridge University Press, New York, NY, 1999
• 63: J. Mitchell , M. Mitchell , A. Scedrov, A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.725, November 08-11, 1998
• 64: John C. Mitchell , Ajith Ramanathan , Andre Scedrov , Vanessa Teague, A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols, Theoretical Computer Science, v.353 n.1, p.118-164, 14 March 2006 [doi>10.1016/j.tcs.2005.10.044]
• 65: Rafael Pass, Bounded-concurrent secure multi-party computation with a dishonest majority, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007393]
• 66: Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
• 67: {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.
• 68: {PSW00} B. Pfitzmann, M. Schunter and M. Waidner. Secure Reactive Systems. IBM Research Report RZ 3206 (#93252), IBM Research, Zurich, May 2000.
• 69: {PSW00a} B. Pfitzmann, M. Schunter and M. Waidner. Provably Secure Certified Mail. IBM Research Report RZ 3207 (#93253), IBM Research, Zurich, August 2000.
• 70: 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]
• 71: 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
• 72: Manoj Prabhakaran , Alon Rosen , Amit Sahai, Concurrent Zero Knowledge with Logarithmic Round-Complexity, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.366-375, November 16-19, 2002
• 73: Manoj Prabhakaran , Amit Sahai, New notions of security: achieving universal composability without trusted setup, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007394]
• 74: {PS05} M. Prabhakaran, A. Sahai. Relaxing Environmental Security: Monitored Functionalities and Client-Server Computation. 2nd Theory of Cryptology Conference (TCC), 2005.
• 75: 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]
• 76: {RS91} C. Rackoff and D. Simon. Non-interactive zero-knowledge proof of knowledge and chosen cipher-text attack. CRYPTO '91, 1991.
• 77: {RK99} R. Richardson and J. Kilian. On the Concurrent Composition of Zero-Knowledge Proofs. In Eurocrypt99, LNCS 1592, pages 415--413.
• 78: Christoph Sprenger , Michael Backes , David Basin , Birgit Pfitzmann , Michael Waidner, Cryptographically Sound Theorem Proving, Proceedings of the 19th IEEE Workshop on Computer Security Foundations, p.153-166, July 05-07, 2006 [doi>10.1109/CSFW.2006.10]
• 79: {Y82A} A. Yao. Protocols for Secure Computation. In 23rd Annual Symp. on Foundations of Computer Science (FOCS), pages 160--164. 1982.
• 80: {Y86} A. Yao, How to generate and exchange secrets, In 27th Annual Symp. on Foundations of Computer Science (FOCS), pages 162--167. 1986.