We extend the notion of universally composable (UC) security in a way that re-establishes its original intuitive guarantee even for protocols that use globally available setup. The new formulation prevents bad interactions even with adaptively chosen protocols that use the same setup. In particular, it guarantees deniability. While for protocols that use no setup the proposed requirements are the same as in traditional UC security, for protocols that use global setup the proposed requirements are significantly stronger. In fact, realizing Zero Knowledge or commitment becomes provably impossible, even in the Common Reference String model. Still, we propose reasonable alternative setup assumptions and protocols that allow realizing practically any cryptographic task under standard hardness assumptions even against adaptive corruptions.
Category / Keywords: foundations / Universal Composability, Generalized Universal Composability, ACRS, CRS, Key Registration, Deniability, Zero Knowledge, Bit Commitment, Multi-Party Computation Publication Info: This is the full version of a paper accepted to TCC 2007. Date: received 20 Nov 2006, last revised 2 Oct 2007 Contact author: walfish at cs nyu edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: Introduced "Coin-Tossing Lemma" to repair a subtle bug in the rewinding proof. Various minor bug fixes and notational alterations. Re-styled some security properties using attack games, to properly facilitate the application of number theoretic assumptions (like Strong RSA) in Sigma protocols. Version: 20071002:061601 (All versions of this report) Short URL: ia.cr/2006/432 Discussion forum: Show discussion | Start new discussion