skip to main content
article

ACM SIGACT news distributed computing column 24

Published: 01 December 2006 Publication History

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]
{BPW03} M. Backes, B. Pfitzmann, and M. Waidner. A composable cryptographic library with nested operations. In 10th ACM conference on computer and communications security (CCS), 2003. Extended version at the eprint archive, http://eprint.iacr.org/2003/015/.
[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]
{BCNP04} B. Barak, R. Canetti, J. B. Nielsen, R. Pass. Universally Composable Protocols with Relaxed Set-Up Assumptions. 45th FOCS, pp. 186--195. 2004.
[5]
{BS05} B. Barak and A. Sahai, How To Play Almost Any Mental Game Over the Net - Concurrent Composition via Super-Polynomial Simulation. 46th FOCS, 2005.
[6]
{B91} D. Beaver. Secure Multi-party Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority. J. Cryptology, (1991) 4: 75--122.
[7]
{BR93} M. Bellare and P. Rogaway. Entity authentication and key distribution. CRYPTO'93, LNCS. 773, pp. 232--249, 1994.
[8]
{BCG93} M. Ben-Or, R. Canetti and O. Goldreich. Asynchronous Secure Computation. 25th Symposium on Theory of Computing (STOC), 1993, pp. 52--61. Longer version appears in TR #755, CS dept., Technion, 1992.
[9]
{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.
[10]
{BKR94} M. Ben-Or, B. Kelmer and T. Rabin. Asynchronous Secure Computations with Optimal Resilience. 13th PODC, 1994, pp. 183--192.
[11]
{BCC88} G. Brassard, D. Chaum and C. Crépeau. Minimum Disclosure Proofs of Knowledge. JCSS, Vol. 37, No. 2, pages 156--189, 1988.
[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]
{C01} R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. Extended abstract in 42nd FOCS, 2001. A revised version (2005) is available at IACR Eprint Archive, eprint. iacr.org/2000/067/ and at the ECCC archive, http://eccc.uni-trier.de/eccc-reports/2001/TR01-016/.
[15]
{C06} R. Canetti. Security and Composition of Cryptographic Protocols: A Tutorial, (Part I). in Distributed Computing Column of ACM SIGACT News, Vol. 37, Num. 3, (Whole Number 140), Sept. 2006.
[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]
{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.
[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]
{CK02} R. Canetti and H. Krawczyk. Universally Composable Key Exchange and Secure Channels. Eurocrypt '02, pages 337--351, 2002. LNCS No. 2332. Extended version at http://eprint.iacr.org/2002/059.
[23]
{CK02a} R. Canetti and H. Krawczyk. Security Analysis of IKE's Signature-based Key-Exchange Protocol. Crypto '02, 2002. Extended version at http://eprint.iacr.org/2002/120.
[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]
{CLOS02} R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai. Universally composable two-party and multi-party secure computation. 34th STOC, pp. 494--503, 2002.
[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]
{DDN00} D. Dolev. C. Dwork and M. Naor. Non-malleable cryptography. SIAM. J. Computing, Vol. 30, No. 2, 2000, pp. 391--437. Preliminary version in 23rd Symposium on Theory of Computing (STOC), 1991.
[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]
{DNS98} C. Dwork, M. Naor, and A. Sahai. Concurrent Zero-Knowledge. In 30th STOC, pages 409--418, 1998.
[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]
{GRR98} R. Gennaro, M. Rabin and T Rabin. Simplified VSS and Fast-track Multiparty Computations with Applications to Threshold Cryptography, 17th PODC, 1998, pp. 101--112.
[38]
{G01} O. Goldreich. Foundations of Cryptography. Cambridge Press, Vol 1 (2001) and Vol 2 (2004).
[39]
{GK89} O. Goldreich and H. Krawczyk. On the Composition of Zero-Knowledge Proof Systems. SIAM. J. Computing, Vol. 25, No. 1, 1996.
[40]
{GMW87} O. Goldreich, S. Micali and A. Wigderson. How to Play any Mental Game. 19th Symposium on Theory of Computing (STOC), 1987, pp. 218--229.
[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]
{GMRi88} S. Goldwasser, S. Micali, and R. L. Rivest. A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM J. Comput., April 1988, pages 281--308.
[45]
{HM00} M. Hirt and U. Maurer. Complete characterization of adversaries tolerable in secure multi-party computation. J. 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.
[46]
{H85} C. A. R. Hoare. Communicating Sequential Processes. International Series in Computer Science, Prentice Hall, 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]
{KLR06} E. Kushilevitz, Y. Lindell and T. Rabin. Information-Theoretically Secure Protocols and Security Under Composition. 38th STOC, pages 109--118, 2006.
[50]
{K06} R. Küsters. Simulation based security with inexhaustible interactive Turing machines. 19th CSFW, 2006.
[51]
{L03} Y. Lindell. General Composition and Universal Composability in Secure Multi-Party Computation. 43rd FOCS, pp. 394--403. 2003.
[52]
{L04} Y. Lindell. Lower Bounds for Concurrent Self Composition. 1st Theory of Cryptology Conference (TCC), pp. 203--222. 2004.
[53]
{LLR02} Y. Lindell, A. Lysyanskaya and T. Rabin. On the composition of authenticated Byzantine agreement. 34th STOC, 2002.
[54]
{LPT04} Y. Lindell, M. Prabhakaran, Y. Tauman. Concurrent General Composition of Secure Protocols in the Timing Model. Manuscript, 2004.
[55]
{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.
[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]
{M89} R. Milner. Communication and Concurrency. Prentice Hall, 1989.
[62]
{M99} R. Milner. Communicating and Mobile Systems: the Pi-Calculus. Cambridge University Press, 1999.
[63]
{MMS98} J. Mitchell, M. Mitchell, A. Schedrov. A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time. 39th FOCS, 1998, pp. 725--734.
[64]
{MRST06} John C. Mitchell, Ajith Ramanathan, Andre Scedrov, Vanessa Teague. A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols. Theor. Comput. Sci. 353(1--3): 118--164 (2006). Preliminary version in LICS'01.
[65]
{P04} R. Pass. Bounded-concurrent secure multi-party computation with a dishonest majority. 36th STOC, pp. 232--241. 2004.
[66]
{P91} T. P. Pedersen: Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. CRYPTO 1991: 129--140
[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]
{PW00} B. Pfitzmann and M. Waidner. Composition and integrity preservation of secure reactive systems. 7th ACM Conf. on Computer and Communication Security (CCS), 2000, pp. 245--254.
[71]
{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.
[72]
{PRS02} M. Prabhakaran, A. Rosen, A. Sahai. Concurrent Zero Knowledge with Logarithmic Round-Complexity. 43rd FOCS, 2002: 366--375.
[73]
{PS04} M. Prabhakaran, A. Sahai. New notions of security: achieving universal composability without trusted setup. 36th STOC, pp. 242--251. 2004.
[74]
{PS05} M. Prabhakaran, A. Sahai. Relaxing Environmental Security: Monitored Functionalities and Client-Server Computation. 2nd Theory of Cryptology Conference (TCC), 2005.
[75]
{RB89} T. Rabin and M. Ben-Or. Verifiable Secret Sharing and Multi-party Protocols with Honest Majority. 21st Symposium on Theory of Computing (STOC), 1989, pp. 73--85.
[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]
{SB+06} C. Sprenger, M. Backes, D. Basin, B. Pfitzmann and M. Waidner. Cryptographically Sound Theorem Proving. 19th Computer Security Foundations Workshop (CSFW), 2006.
[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.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGACT News
ACM SIGACT News  Volume 37, Issue 4
December 2006
117 pages
ISSN:0163-5700
DOI:10.1145/1189056
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2006
Published in SIGACT Volume 37, Issue 4

Check for updates

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 256
    Total Downloads
  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media