Paper 2006/432

Universally Composable Security with Global Setup

Ran Canetti, Yevgeniy Dodis, 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.

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.