In this paper we study (interpret) the precise composability guarantee of the generalised universal composability (GUC) feasibility with global setups that was proposed in the recent paper Canetti et al. (2007) from the point of view of full universal composability (FUC), that is, composability with arbitrary protocols, which was the original security goal and motivation for UC. By observing a counter-intuitive phenomenon, we note that the GUC feasibility implicitly assumes that the adversary has limited access to arbitrary external protocols. We then clarify a general principle for achieving FUC security, and propose some approaches for fixing the GUC feasibility under the general principle. Finally, we discuss the relationship between GUC and FUC from both technical and philosophical points of view. This should be helpful in gaining a precise understanding of the GUC feasibility, and for preventing potential misinterpretations and/or misuses in practice.
In this paper we study (interpret) the precise composability guarantee of the generalised universal composability (GUC) feasibility with global setups that was proposed in the recent paper Canetti et al. (2007) from the point of view of full universal composability (FUC), that is, composability with arbitrary protocols, which was the original security goal and motivation for UC. By observing a counter-intuitive phenomenon, we note that the GUC feasibility implicitly assumes that the adversary has limited access to arbitrary external protocols. We then clarify a general principle for achieving FUC security, and propose some approaches for fixing the GUC feasibility under the general principle. Finally, we discuss the relationship between GUC and FUC from both technical and philosophical points of view. This should be helpful in gaining a precise understanding of the GUC feasibility, and for preventing potential misinterpretations and/or misuses in practice.
Yao et al. (A note on the feasibility of generalized universal composability.Theory and Applications of Models of Computationpp. 474–485, 2007; A note on the feasibility of generalised universal composability.Mathematical Structures in Computer Science,19(1), pp. 193–205) claimed a potential limitation on the class of protocols that could be securely implemented in the generalized universal composability (GUC) framework proposed by Canetti et al. (Universally composable security with global setup.Lecture Notes in Computer Science, pp. 61–85, 2007). Specifically, Yao et al. presented a concrete attack on a GUC Zero Knowledge (GUCZK) protocol, a natural adaptation Blum's ZK proof for Directed Hamiltonicity using the general GUC feasibility of Canetti et al. (Universally composable security with global setup.Lecture Notes in Computer Science, pp. 61–85, 2007). Interestingly, the attack was not analysed in the GUC model in Yao et al. (A note on the feasibility of generalised universal composability.Mathematical Structures in Computer Science19(1), pp. 193–205, 2009) but in theFUC model, a new UC-like framework proposed in the same work. Nonetheless, Yao et al. (A note on the feasibility of generalised universal composability.Mathematical Structures in Computer Science19(1), pp. 193–205, 2009) argued that, in light of this attack, GUC would lose its concurrent general composability and proof of knowledge properties. Concretely, they argue that GUC composability would now be with respect to some adversaries with limited access to external arbitrary protocols. In this work, we show that the claimed attack from Yao et al. is indeed harmless and does not contradict the security of the mentioned GUCZK protocol, thus restoring the general feasibility for GUC.
The Universal Composability (UC) framework provides provable security guaranties for harsh application environment, where we want to construct protocols which keep security guarantees even when they are concurrently composed with arbitrary number of arbitrary (even hostile) protocols.This is a very strong guarantee.The UC-framework inherently supports the modular design, which allows secure composition of arbitrary number of UC-secure components with an arbitrary protocol.In contrast, traditional analysis and design is a stand alone analysis where security of a single instance is considered, i.e. an instance which is not in potential interaction with any concurrent instances.Furthermore, a typical traditional analysis is informal, i.e. without a formal proof.In spite of these facts, beyond the task of key-exchange this technology have not really took the attention of the community of applied cryptography.From practitioner's point of view the UC-world may seem more or less an academic interest of theoretical cryptographers.Accordingly we take a pragmatic approach, where we concentrate on meaningful compromises between the assumed adversarial strength, ideality wishes and realization complexity while keeping provable security guarantees within the UC-framework.We believe that even modest but provable goals (especially, if tunable to application scenarios) are interesting if a wider penetration of the UC-technology is desired into the daily-practice of protocol applications.
Modeling security for protocols running in the complex network environment of the Internet can be a daunting task. Ideally, a security model for the Internet should provide the following guarantee: a protocol that implements a particular task specification will retain all the same security properties as the specification itself, even when an arbitrary set of protocols runs concurrently on the same network. This guarantee must hold even when other protocols are maliciously designed to interact badly with the analyzed protocol, and even when the analyzed protocol is composed with other protocols. The popular Universal Composability (UC) security framework aims to provide this guarantee.
Unfortunately, such strong security guarantees come with a price: they are impossible to achieve without the use of some trusted setup. Typically, this trusted setup is global in nature, and takes the form of a Public Key Infrastructure (PKI) and/or a Common Reference String (CRS). However, the current approach to modeling security in the presence of such setups falls short of providing expected security guarantees. A quintessential example of this phenomenon is the deniability concern: there exist natural protocols that meet the strongest known security notions (including UC) while failing to provide the same deniability guarantees that their task specifications imply they should provide.
We introduce the Generalized Universal Composability (GUC) framework to extend the UC security notion and enable the re-establishment of its original intuitive security guarantees even for protocols that use global trusted setups. In particular, GUC enables us to guarantee that secure protocols will provide the same level of deniability as the task specification they implement. To demonstrate the usefulness of the GUC framework, we first apply it to the analysis and construction of deniable authentication protocols. Building upon such deniable authentication protocols, we then prove a general feasibility result showing how to construct protocols satisfying our security notion for a large class of two-party and multi-party tasks (assuming the availability of some reasonable trusted setup). Finally, we highlight the practical applicability of GUC by constructing efficient protocols that securely instantiate two common cryptographic tasks: commitments and zero-knowledge proofs.
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
A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally Composable (UC) security provides this guarantee in a strong sense: A UC-secure protocol maintains its security properties even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, many interesting cryptographic tasks are provably impossible to realize with UC security in the standard, “plain” model of computation. Impossibility holds even if ideally authenticated communication channels are provided. In contrast, it has been demonstrated that general secure computation can be obtained in a number of idealized models. Each one of these models represents a form of trust that is put in some of the system’s components. This survey examines and compares some of these trust models, both from the point of view of their sufficiency for building UC secure protocols, and from the point of view of their practical realizability. We start with the common reference string (CRS) model, and then describe several relaxations and alternatives including the Defective CRS model, the key registration models, the hardware token model, the global and augmented CRS models, and a timing assumption. Finally, we briefly touch upon trust models for obtaining authenticated communication.
Universally composable protocols (Canetti, FOCS 2000) are cryptographic protocols that remain secure even when run concurrently with arbitrary other protocols. Thus, universally composable protocols can be run in modern networks, like the Internet, and their security is guaranteed. However, the de nition of universal composition actually assumes that each execution of the protocol is assigned a unique session identi er, and furthermore, that this identi er is known to all the participating parties. In addition, all universally composable protocols assume that the set of participating parties and the speci cation of the protocol to be run are a-priori agreed upon and known to all parties. In a decentralized network like the Internet, this setup information must be securely generated by the parties themselves. In this note we formalize the setup problem and show how to securely realize it with a simple and highly ecient protocol.