Cryptology ePrint Archive: Report 2007/478

Impossibility Results for Universal Composability in Public-Key Models and with Fixed Inputs

Dafna Kidron and Yehuda Lindell

Abstract: Universal composability and concurrent general composition consider a setting where secure protocols are run concurrently with each other and with arbitrary other possibly insecure protocols. Protocols that meet the definition of universal composability are guaranteed to remain secure even when run in this strongly adversarial setting. In the case of an honest majority, or where there is a trusted setup phase of some kind (like a common reference string or the key-registration public-key infrastructure of Barak et al.~in FOCS 2004), it has been shown that any functionality can be securely computed in a universally composable way. On the negative side, it has also been shown that in the {\em plain model}\/ where there is no trusted setup at all, there are large classes of functionalities which cannot be securely computed in a universally composable way without an honest majority.

In this paper we extend these impossibility results for universal composability. We study a number of public-key models and show for which models the impossibility results of universal composability hold and for which they do not. We also consider a setting where the inputs to the protocols running in the network are fixed before any execution begins. The majority of our results are negative and we show that the known impossibility results for universal composability in the case of no honest majority extend to many other settings.

Category / Keywords: cryptographic protocols / universal composability, public-key infrastructure, concurrent general composition, impossibility results

Publication Info: To appear in the Journal of Cryptology.

Date: received 23 Dec 2007, last revised 6 Jun 2010

Contact author: lindell at cs biu ac il

Available format(s): PDF | BibTeX Citation

Version: 20100606:103924 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]