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 \emph{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.
Category / Keywords: foundations / secure multi-party computation, protocol composition, universal composability, general composition Publication Info: This paper appeared in the 44th FOCS, 2003. Date: received 24 Jul 2003, last revised 5 Mar 2008 Contact author: lindell at cs biu ac il Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: This is the final version. Version: 20080305:072440 (All versions of this report) Short URL: ia.cr/2003/141 Discussion forum: Show discussion | Start new discussion