GNUC: A New Universal Composability Framework.

Dennis Hofheinz, Victor Shoup

Published Jan 1, 2011• 17 citations

Abstract

We put forward a framework for the modular design and analysis of multi-party protocols. Our framework is called “GNUC ” (with the recursive meaning “GNUC’s Not UC”), already alluding to the similarity to Canetti’s Universal Composability (UC) framework. In particular, like UC, we offer a universal composition theorem, as well as a theorem for composing protocols with joint state. We deviate from UC in several important aspects. Specifically, we have a rather different view than UC on the structuring of protocols, on the notion of polynomial-time protocols and attacks, and on corruptions. We will motivate our definitional choices by explaining why the definitions in the UC framework are problematic, and how we overcome these problems. Our goal is to offer a framework that is largely compatible with UC, such that previous results formulated in UC carry over to GNUC with minimal changes. We exemplify this by giving explicit formulations for several important protocol tasks, including authenticated and secure communication, as well as commitment and secure function evaluation. 1

Related papers

Diving Deep Into UC

Céline Chevalier, Éric Sageloli

Introduced by Canetti in 2001, Universal Composability (UC) is a widely adopted security model that enables the specification and proof of security for a broad range of protocols, offering strong security guarantees. At its core lies the universal composition theorem (UC theorem), which ensures that protocols proven secure within the framework remain secure even when deployed in real-world environments with multiple instances of them. In this work, we present two key contributions. First, we identify several problems with the UC framework, in particular the UC Theorem. They include counterexamples, limitations that make it unusable for important classes of protocols, and weaknesses in its proof. These problems reveal flaws in nearly all the fundamental concepts of UC. Second, we propose a revised formulation of the main concepts of UC to address these issues. Although the resulting modifications are nontrivial, our updated definitions are designed to remain as faithful as possible to the structure and intent of the original model.

IACR Communications in CryptologyMay 4, 20260 citations

A Simpler Variant of Universally Composable Security for Standard Multiparty Computation.

Ran Canetti, Asaf Cohen, Yehuda Lindell

In this paper, we present a simpler and more restricted variant of the universally composable security (UC) framework that is suitable for “standard ” two-party and multiparty computation tasks. Many of the complications of the UC framework exist in order to enable more general tasks than classic secure computation. This generality may be a barrier to entry for those who are used to the stand-alone model of secure computation and wish to work with universally composable security but are overwhelmed by the differences. The variant presented here (called simplified universally composable security, or just SUC) is closer to the definition of security for multiparty computation in the stand-alone setting. The main difference is that a protocol in the SUC framework runs with a fixed set of parties who know each other’s identities ahead of time, and machines cannot be added dynamically to the execution. As a result, the definitions of polynomial time and protocol composition are much simpler. In addition, the SUC framework has authenticated channels built in, as is standard in previous definitions of security, and all communication is done via the adversary in order to enable arbitrary scheduling of messages. Due to these differences, not all cryptographic tasks can be expressed in the SUC framework.

Jan 1, 20141 citation

Polynomial Runtime and Composability.

Dennis Hofheinz, Dominique Unruh, Jörn Müller‐Quade

Abstract. To prove security of a multi-party cryptographic protocol, one often reduces attacks on the protocol to attacks on a suitable computational problem. Thus, if the computational problem is hard, then the protocol is secure. But to allow for a security reduction, the protocol itself and the attack on the protocol must be efficient, i.e., polynomialtime. Of course, the obvious way to enforce an overall polynomial runtime of the protocol is to require each individual protocol machine and adversarial entity to be polynomialtime. However, as the specific case of zero-knowledge protocols demonstrates, an a priori polynomial-time bound on all entities may not be an optimal choice because the running time of some machines needs to depend on that of others. As we want to be able to model arbitrary protocol tasks, we work in the Universal Composability framework (UC). This framework additionally provides strong composability guarantees. We will point out that in the UC setting, finding a useful notion of polynomial-time for the analysis of general protocols is a highly non-trivial task. Our goal in this work is to find a good and useful definition of polynomial-time for multiparty protocols in the UC setting that matches the intuition of what is feasible. A good

Jan 1, 20099 citations

New Notions of Security: Achieving Universal Composability without Trusted Setup.

Manoj Prabhakaran, Amit Sahai

We propose a modification to the framework of Universally Composable (UC) security [3]. Our new notion, involves comparing the protocol executions with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [3] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework. 1

Jan 1, 20047 citations

New notions of security

Manoj Prabhakaran, Amit Sahai

We propose a modification to the framework of Universally Composable (UC) security [3]. Our new notion involves comparing the real protocol execution with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [3] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework.

ACM Symposium on Theory of Computing (STOC)Jun 13, 2004149 citations

Leakage Tolerant Interactive Protocols.

Nir Bitansky, Ran Canetti, Shai Halevi

We put forth a framework for expressing security requirements from interactive protocols in the presence of arbitrary leakage. This allows capturing different levels of leakage tolerance of protocols, namely the preservation (or degradation) of security, under coordinated attacks that include various forms of leakage from the secret states of participating components. The framework extends the universally composable (UC) security framework. We also prove a variant of the UC theorem, that enables modular design and analysis of protocols even in face of general, non-modular leakage. We then construct leakage tolerant protocols for basic tasks, such as, secure message transmission, message authentication, commitment, oblivious transfer and zero knowledge. A central component in several of our constructions is the observation that resilience to adaptive party corruptions

Jan 1, 20114 citations