Abstract
Concurrent general composition relates to a setting where a secure protocol is run in a network concurrently with other, arbitrary protocols. Clearly, security in such a setting is what is desired, or even needed, in modern computer networks where many different protocols are executed concurrently. Canetti (FOCS 2001) introduced the notion of universal composability and showed that security under this definition is sufficient for achieving concurrent general composition. However, it is not known whether or not the opposite direction also holds.
Our main result is a proof that security under concurrent general composition, when interpreted in the natural way under the simulation paradigm, is equivalent to a variant of universal composability, where the only difference relates to the order of quantifiers in the definition. (In newer versions of universal composability, these variants are equivalent.) An important corollary of this theorem is that existing impossibility results for universal composability (for all its variants) are inherent for definitions that imply security under concurrent general composition, as formulated here. In particular, there are large classes of two-party functionalities for which it is impossible to obtain protocols (in the plain model) that remain secure under concurrent general composition. We stress that the impossibility results obtained are not “black-box,” and apply even to non-black-box simulation.
Our main result also demonstrates that the definition of universal composability is somewhat “minimal” in that the composition guarantee provided by universal composability implies the definition itself. This indicates that the security definition of universal composability is not overly restrictive.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B. Barak, A. Sahai, How to play almost any mental game over the net—concurrent composition via super-polynomial simulation, in 46th FOCS (2005), pp. 543–552
B. Barak, R. Canetti, J. Nielsen, R. Pass, Universally composable protocols with relaxed set-up assumptions, in 45th FOCS (2004), pp. 186–195
D. Beaver, Foundations of secure interactive computing, in CRYPTO’91. LNCS, vol. 576 (Springer, Berlin, 1991), pp. 377–391
M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in 20th STOC (1988), pp. 1–10
R. Canetti, Security and composition of multiparty cryptographic protocols. J. Cryptol. 13(1), 143–202 (2000)
R. Canetti, Universally composable security: a new paradigm for cryptographic protocols, in 42nd FOCS (2001), pp. 136–145
R. Canetti, Universally composable security: a new paradigm for cryptographic protocols, in Cryptology ePrint Archive, Report 2000/067. Version updated 2005
R. Canetti, M. Fischlin, Universally composable commitments, in CRYPTO’01. LNCS, vol. 2139 (Springer, Berlin, 2001), pp. 19–40
R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai, Universally composable two-party and multi-party computation, in 34th STOC (2002), pp. 494–503
R. Canetti, J. Kilian, E. Petrank, A. Rosen, Black-box concurrent zero-knowledge requires \(\tilde{\Omega}(\log n)\) rounds. SIAM J. Comput. 32(1), 1–47 (2003)
R. Canetti, E. Kushilevitz, Y. Lindell, On the limitations of universal composable two-party computation without set-up assumptions. J. Cryptol. 19(2), 135–167 (2006)
D. Chaum, C. Crepeau, I. Damgard, Multi-party unconditionally secure protocols, in 20th STOC (1988), pp. 11–19
C. Dwork, M. Naor, O. Reingold, L.J. Stockmeyer, Magic functions. J. ACM 50(6), 852–921 (2003)
C. Dwork, M. Naor, A. Sahai, Concurrent zero-knowledge. J. ACM 51(6), 851–898 (2004)
O. Goldreich, Cryptography and cryptographic protocols. Distrib. Comput. 16(2), 177–199 (2003)
O. Goldreich, Basic Applications. Foundations of Cryptography, vol. 2 (Cambridge University Press, Cambridge, 2004)
O. Goldreich, S. Micali, A. Wigderson, How to play any mental game—a completeness theorem for protocols with honest majority, in 19th STOC (1987), pp. 218–229
S. Goldwasser, L. Levin, Fair computation of general functions in presence of immoral majority, in CRYPTO’90. LNCS, vol. 537 (Springer, Berlin, 1990), pp. 77–93
S. Goldwasser, Y. Lindell, Secure computation without agreement. J. Cryptol. 18(3), 247–287 (2005)
Y. Kalai, Y. Lindell, M. Prabhakaran, Concurrent general composition of secure protocols in the timing model, in the 37th STOC (2005), pp. 644–653. In J. Cryptol. 20(4), 431–492 (2007)
Y. Lindell, Bounded-concurrent secure two-party computation without setup assumptions, in 35th STOC (2003), pp. 683–692
Y. Lindell, General composition and universal composability in secure multi-party computation. (Extended abstract of this paper), in 44th FOCS (2003), pp. 394–403
Y. Lindell, Composition of Secure Multi-Party Protocols—A Comprehensive Study. LNCS, vol. 2815 (Springer, Berlin, 2003)
Y. Lindell, Lower bounds for concurrent self composition, in 1st Theory of Cryptography Conference (TCC). LNCS, vol. 2951 (Springer, Berlin, 2004), pp. 203–222. J. Cryptol. 21(2), 200–249 (2008)
T. Malkin, R. Moriarty, N. Yakovenko, Generalized environmental security from number theoretic assumptions, in The 3rd TCC. LNCS, vol. 3876 (Springer, Berlin, 2006), pp. 343–359
S. Micali, P. Rogaway, Secure Computation. Unpublished manuscript, 1992. Preliminary version in CRYPTO’91, LNCS vol. 576 (Springer, Berlin, 1991), pp. 392–404
S. Micali, R. Pass, A. Rosen, Input-indistinguishable computation, in 47th FOCS (2006) pp. 367–378
R. Pass, Simulation in quasi-polynomial time, and its application to protocol composition, in Eurocrypt 2003. LNCS, vol. 2656 (Springer, Berlin, 2003), pp. 160–176
R. Pass, Bounded-concurrent secure multi-party computation with a dishonest majority, in 36th STOC (2004), pp. 232–241
R. Pass, A. Rosen, Bounded-concurrent secure two-party computation in a constant number of rounds, in 44th FOCS (2003)
B. Pfitzmann, M. Waidner, Composition and integrity preservation of secure reactive systems, in 7th ACM Conference on Computer and Communication Security (2000), pp. 245–254
M. Prabhakaran, A. Sahai, New notions of security: universal composability without trusted setup, in 36th STOC (2004), pp. 242–251
T. Rabin, M. Ben-Or, Verifiable secret sharing and multi-party protocols with honest majority, in 21st STOC (1989), pp. 73–85
R. Richardson, J. Kilian, On the concurrent composition of zero-knowledge proofs, in EUROCRYPT’99. LNCS, vol. 1592 (Springer, Berlin, 1999), pp. 415–431
A. Yao, How to generate and exchange secrets, in 27th FOCS (1986), pp. 162–167
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Oded Goldreich
An extended abstract of this work appeared in the 44th FOCS, 2003.
Yehuda Lindell: Most of this work was carried out while the author was at the IBM T.J. Watson Research Center.
Rights and permissions
About this article
Cite this article
Lindell, Y. General Composition and Universal Composability in Secure Multiparty Computation. J Cryptol 22, 395–428 (2009). https://doi.org/10.1007/s00145-008-9021-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-008-9021-2