Universally composable two-party and multi-party secure computation

ABSTRACT

We show how to securely realize any multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider a multi-party network with open communication and an adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and make general intractability assumptions.

REFERENCES

• 1: D. Beaver Secure Multi-party Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority, Journal of Cryptology, Vol. 4, pp. 75--122, 1991.
• 2: D. Beaver, and S. Goldwasser, Multiparty Computation with Faulty Majority, FOCS 89.
• 3: M. Ben-Or, S. Goldwasser and A. Wigderson, "Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation", STOC 1998.
• 4: M. Blum , "Coin flipping by telephone", IEEE Spring COMPCOM, pp. 133--137, Feb. 1982.
• 5: M. Blum How to Prove a Theorem So No One Else Can Claim It. Proceedings of the International Congress of (MATH)ematicians, Berkeley, California, USA, 1986, pp. 1444--1451.
• 6: Manuel Blum , Paul Feldman , Silvio Micali, Non-interactive zero-knowledge and its applications, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.103-112, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62222]
• 7: Manuel Blum , Alfredo De Santis , Silvio Micali , Giuseppe Persiano, Noninteractive zero-knowledge, SIAM Journal on Computing, v.20 n.6, p.1084-1118, Dec. 1991 [doi>10.1137/0220068]
• 8: 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]
• 9: R. Canetti Security and composition of multi-party cryptographic protocols", Journal of Cryptology, Vol. 13, No. 1, winter 2000.
• 10: R. Canetti, "Universally Composable Security: A New paradigm for Cryptographic Protocols", 42nd FOCS, 2001. Full version at http://eprint.iacr.org/2000/067.
• 11: 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]
• 12: Ran Canetti , Marc Fischlin, Universally Composable Commitments, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.19-40, August 19-23, 2001
• 13: R. Canetti, Y. Lindell, R. Ostrovsky and A. Sahai. Universally Composable Two-Party and Multiparty Secure Computation. In the ePrint archive: http://eprint.iacr.org.
• 14: R. Canetti and T. Rabin. Universal Composition with Joint State. IACR's Eprint archive, http://eprint.iacr.org/2002/.
• 15: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 16: Ivan Damgård , Jesper Buus Nielsen, Improved Non-committing Encryption Schemes Based on a General Complexity Assumption, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.432-450, August 20-24, 2000
• 17: I. Damgard and J. Nielsen Perfect Hiding or Perfect Binding Universally Composable Commitment Schemes with Constanst Expansion Factor. Manuscrtipt on Damgard homepage, 2001.
• 18: Y. Dodis and S. Micali Secure Computation, CRYPTO 2000.
• 19: A. DeSantis, G. DiCrescenzo, R. Ostrovsky, G. Persiano, A. Sahai. Robust Non-interactive Zero-Knowledge. CRYPTO 2001.
• 20: Giovanni Di Crescenzo , Yuval Ishai , Rafail Ostrovsky, Non-interactive and non-malleable commitment, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.141-150, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276722]
• 21: Giovanni Di Crescenzo , Jonathan Katz , Rafail Ostrovsky , Adam Smith, Efficient and Non-interactive Non-malleable Commitment, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.40-59, May 06-10, 2001
• 22: A. DeSantis and G. Persiano. Zero-Knowledge Proofs of Knowledge Without Interaction. FOCS 1992.
• 23: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 24: 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]
• 25: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 26: Uriel Feige , Adi Shamir, Zero knowledge proofs of knowledge in two rounds, Proceedings on Advances in cryptology, p.526-544, July 1989, Santa Barbara, California, United States
• 27: U. Feige, D. Lapidot, and A. Shamir, Multiple non-interactive zero knowledge proofs based on a single random string. FOCS 1990.
• 28: Zvi Galil , Stuart Haber , Moti Yung, Cryptographic Computation: Secure Faut-Tolerant Protocols and the Public-Key Model, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.135-155, August 16-20, 1987
• 29: J. A. Garay , P. MacKenzie, Concurrent oblivious transfer, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.314, November 12-14, 2000
• 30: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 31: O. Goldreich. Secure Multi-Party Computation. Manuscript. Preliminary version, 1998. www.wisdom.weizmann.ac.il/~oded/pp.html.
• 32: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 33: 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]
• 34: Shafi Goldwasser , Leonid A. Levin, Fair Computation of General Functions in Presence of Immoral Majority, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.77-93, August 11-15, 1990
• 35: S. Goldwasser and S. Micali. Probabilistic Encryption. In JCSS 28(2), pages 270--299, 1984.
• 36: 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]
• 37: Joe Kilian, Uses of randomness in algorithms and protocols, MIT Press, Cambridge, MA, 1990
• 38: E. Kushilevitz, S. Micali and R. Ostrovsky, Reducibility and Completeness In Multi-Party Private Computations, FOCS 94.
• 39: 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]
• 40: S. Micali and P. Rogaway, Secure Computation, unpublished manuscript, 1992. Preliminary version in CRYPTO '91, LNCS 576, Springer-Verlag, 1991.
• 41: M. Naor, Bit Commitment using Pseudorandom Generators. Journal of Cryptology, Vol. 4, pages 151--158, 1991.
• 42: 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]
• 43: M. Rabin, How to exchange secrets by oblivious transfer, Tech. Memo TR-81, Aiken Computation Laboratory, Harvard U., 1981.
• 44: 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]
• 45: R. Richardson and J. Kilian On the Concurrent Composition of Zero-Knowledge Proofs. Eurocrypt 1999.
• 46: Amit Sahai, Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.543, October 17-18, 1999
• 47: A. Yao How to generate and exchange secrets, FOCS 1986.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

General Terms:
Algorithms, Experimentation, Performance, Security, Theory