Paper 2004/116

On the Limitations of Universally Composable Two-Party Computation Without Set-up Assumptions

Ran Canetti, Eyal Kushilevitz, and Yehuda Lindell

Abstract

The recently proposed {\em universally composable {\em (UC)} security} framework for analyzing security of cryptographic protocols provides very strong security guarantees. In particular, a protocol proven secure in this framework is guaranteed to maintain its security even when run concurrently with arbitrary other protocols. It has been shown that if a majority of the parties are honest, then universally composable protocols exist for essentially any cryptographic task in the {\em plain model} (i.e., with no setup assumptions beyond that of authenticated communication). When honest majority is not guaranteed, general feasibility results are known only given trusted set-up, such as in the common reference string model. Only little was known regarding the existence of universally composable protocols in the plain model without honest majority, and in particular regarding the important special case of two-party protocols. We study the feasibility of universally composable two-party {\em function evaluation} in the plain model. Our results show that in this setting, very few functions can be securely computed in the framework of universal composability. We demonstrate this by providing broad impossibility results that apply to large classes of deterministic and probabilistic functions. For some of these classes, we also present full characterizations of what can and cannot be securely realized in the framework of universal composability. Specifically, our characterizations are for the classes of deterministic functions in which (a) both parties receive the same output, (b) only one party receives output, and (c) only one party has input.