Universal composability and concurrent general composition consider a setting where secure protocols are run concurrently with each other and with arbitrary other possibly insecure protocols. Protocols that meet the definition of universal composability are guaranteed to remain secure even when run in this strongly adversarial setting. In the case of an honest majority, or where there is a trusted setup phase of some kind (like a common reference string or the keyregistration public-key infrastructure of Barak et al. in FOCS 2004), it has been shown that any functionality can be securely computed in a universally composable way. On the negative side, it has also been shown that in the plain model where there is no trusted setup at all, there are large classes of functionalities which cannot be securely computed in a universally composable way without an honest majority. In this paper we extend these impossibility results for universal composability. We study a number of public-key models and show for which models the impossibility results of universal composability hold and for which they do not. We also consider a setting where the inputs to the protocols running in the network are fixed before any execution begins. The majority of our results are negative and we show that the known impossibility results for universal composability in the case of no honest majority extend to many other settings.
Universal composability and concurrent general composition consider a setting where secure protocols are run concurrently with each other and with arbitrary other possibly insecure protocols. Protocols that meet the definition of universal composability are guaranteed to remain secure even when run in this strongly adversarial setting. In the case of an honest majority, or where there is a trusted setup phase of some kind (like a common reference string or the keyregistration public-key infrastructure of Barak et al. in FOCS 2004), it has been shown that any functionality can be securely computed in a universally composable way. On the negative side, it has also been shown that in the plain model where there is no trusted setup at all, there are large classes of functionalities which cannot be securely computed in a universally composable way without an honest majority. In this paper we extend these impossibility results for universal composability. We study a number of public-key models and show for which models the impossibility results of universal composability hold and for which they do not. We also consider a setting where the inputs to the protocols running in the network are fixed before any execution begins. The majority of our results are negative and we show that the known impossibility results for universal composability in the case of no honest majority extend to many other settings.
A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally composable (UC) protocols provide this guarantee in a strong sense: A protocol remains secure even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, UC protocols for carrying out general tasks are known to exist only if a majority of the participants are honest, or in the common reference string (CRS) model where all parties are assumed to have access to a common string that is drawn from some pre-defined distribution. Furthermore, carrying out many interesting tasks in a UC manner and without honest majority or set-up assumptions is impossible, even if ideally authenticated communication is provided. A natural question is thus whether there exist more relaxed set-up assumptions than the CRS model that still allow for UC protocols. We answer this question in the affirmative: we propose alternative and relaxed set-up assumptions and show that they suffice for reproducing the general feasibility results for UC protocols in the CRS model. These alternative assumptions have the flavor of a "public-key infrastructure": parties have registered public keys, no single registration authority needs to be fully trusted, and no single piece of information has to be globally trusted and available. In addition, unlike known protocols in the CRS model, the proposed protocols guarantee some basic level of security even if the set-up assumption is violated.
Abstract. The recently proposed universally composable (UC) security framework, for analyzing security of cryptographic protocols, provides very strong security guarantees. In particular, a protocol proven secure in this framework is guaranteed to maintain its security even when deployed in arbitrary multi-party, multi-protocol, multi-execution environments. Protocols for securely carrying out essentially any cryptographic task in a universally composable way exist, both in the case of an honest majority (in the plain model, i.e., without set-up assumptions) and in the case of no honest majority (in the common reference string model). However, in the plain model, little was known for the case of no honest majority and, in particular, for the important special case of two-party protocols. We study the feasibility of universally composable two-party function evaluation in the plain model. Our results show that very few functions can be computed in this model so as to provide the UC security guarantees. Specifically, for the case of deterministic functions, we provide a full characterization of the functions computable in this model. (Essentially, these are the functions that depend on at most one of the parties’ inputs, and furthermore are “efficiently invertible ” in a sense defined within.) For the case of probabilistic functions, we show that the only functions computable in this model are those where one of the parties can essentially uniquely determine the joint output. 1
In the setting of secure multiparty computation, a set of mutually distrustful parties wish to securely compute some joint function of their inputs. In the stand-alone case, it has been shown that every efficient function can be securely computed. However, in the setting of concurrent composition, broad impossibility results have been proven for the case of no honest majority and no trusted setup phase. These results hold both for the case of general composition (where a secure protocol is run many times concurrently with arbitrary other protocols) and self composition (where a single secure protocol is run many times concurrently). In this paper, we investigate the feasibility of obtaining security in the concurrent setting, assuming that each party has a local clock and that these clocks proceed at approximately the same rate. We show that under this mild timing assumption, it is possible to securely compute any multiparty functionality under concurrent self composition. Loosely speaking, we also show that it is possible to securely compute any multiparty functionality under concurrent general composition, as long as the secure protocol is run only with protocols whose messages are delayed by a specified amount of time. On the negative side, we show that it is impossible to achieve security under concurrent general composition with no restrictions whatsoever on the network (like the aforementioned delays), even in the timing model.
Concurrent general composition relates to a setting where a secure protocol is run in a network concurrently with other, arbitrary protocols. Clearly, security in such a setting is what is desired, or even needed, in modern computer networks where many different protocols are executed concurrently. Our main result is a proof that security under concurrent general composition is equivalent to a relaxed variant of universal composability (where the only difference relates to the order of quantifiers in the definition). An important corollary of this theorem is that existing impossibility results for universal composability (or actually its relaxed variant) are inherent in any definition achieving security under concurrent general composition. We stress that the impossibility results obtained are not "black-box", and apply even to non-black-box simulation. Our main result also demonstrates that the definition of universal composability is somewhat "minimal", in that the composition guarantee provided by universal composability (almost) implies the definition itself. This indicates that the security definition of universal composability is not overly restrictive.
We show how to securely realize any multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider a multi-party network with open communication and an adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and make general intractability assumptions.
We show how to securely realize any multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider a multi-party network with open communication and an adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and make general intractability assumptions.