Cryptology ePrint Archive: Report 2006/432

Universally Composable Security with Global Setup

Ran Canetti and Yevgeniy Dodis and Rafael Pass and Shabsi Walfish

Abstract: Cryptographic protocols are often designed and analyzed under some trusted setup assumptions, namely in settings where the participants have access to global information that is trusted to have some basic security properties. However, current modeling of security in the presence of such setup falls short of providing the expected security guarantees. A quintessential example of this phenomenon is the deniability concern: there exist natural protocols that meet the strongest known composable security notions, and are still vulnerable to bad interactions with rogue protocols that use the same setup.

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:

[ Cryptology ePrint archive ]