Research on Secure Protocol Composition


General Introduction

In a stand-alone setting of computation, a single set of parties carry out a single protocol execution in isolation. That is, it is assumed that these parties are the only ones running a protocol and that they run it only once. In this setting, powerful feasibility results for secure multiparty computation have been demonstrated. In short, it has been shown that any efficient functionality can be securely computed [Y,GMW,BGW,CCD]. These results hold for the stand-alone setting. However, in modern networks, many protocols are simultaneously (or concurrently) executed. This setting raises new adversarial threats that must be addressed. Indeed, the security of a protocol in the stand-alone setting does not necessarily imply its security under concurrent composition. It is therefore of fundamental importance to study the feasibility of obtaining secure two-party and multi-party protocols for this more general setting. Below, we typically refer to concurrent composition only.

Generally speaking, the notion of "protocol composition" refers to a setting where many protocol executions take place. This includes many possible scenarios. One very important distinction between different types of composition relates to the context in which the secure protocol is being executed. Loosely speaking, this defines two classes of composition: self composition where a single secure protocol is executed many times, and general composition where a secure protocol is executed many times together with arbitrary other protocols.

Click here to view the powerpoint slides of a survey on the topic of secure concurrent composition of multiparty protocols.


My Contributions

An immediate question that arises when discussing protocol composition is whether or not it is actually different from the stand-alone setting. That is, is it "harder" to achieve security in the setting of concurrent composition than in the stand-alone setting? In the past, it has been shown that there exist zero-knowledge protocols that are secure in the stand-alone setting but that are not secure under (parallel) composition (Goldreich-Krawczyk, SICOMP 1996) and that the round complexity of concurrent zero-knowledge must be greater (e.g., Canetti, Kilian, Petrank and Rosen, STOC 2001). Going one step further, we show that there exist problems that cannot be solved under composition by any protocol running for any (polynomial) number of rounds. Specifically, we show that it is impossible to obtain protocols for authenticated Byzantine agreement (in the case of 1/3 or more corrupted parties) that remain secure even under parallel composition. We note that in the stand-alone model, the authenticated Byzantine agreement problem can be solved for any number of corrupted parties. Beyond that discussed above, this result has general ramifications due to the widespread use of Byzantine agreement in secure protocol construction (see [GL02]).

In light of the above, a highly important research project is to understand the feasibility (or infeasibility) of obtaining secure multiparty computation under composition. A very important step forward in this direction was taken with the introduction of the definition of universal composability (Canetti, FOCS 2001). A protocol that is secure under this definition is guaranteed to remain secure under concurrent general composition and so can be safely executed in a modern network setting, like the Internet. It has been shown that in the case of an honest majority, universally composable protocols exist for any functionality. However, when no such honest majority exists, very little was known.

We show that in the common reference string model, where all parties are given access to a string chosen by some predetermined distribution, it is possible to securely compute any multi-party functionality. This holds for any number of corrupted parties and in the face of malicious, adaptive adversaries.

On the flip side, we show that when no trusted setup phase is available (that can be used, for example, in order to obtain a common reference string), then there are large classes of functionalities that cannot be securely computed under the definition of universal composability. Thus, universally composable protocols can be constructed in the case of an honest majority or using some trusted preprocessing phase. Arguably, both of these assumptions are very problematic in today's decentralized world of distributed computing. The above results therefore prompt the question of whether of not the definition of universal composability is possibly too stringent. In other words, can security under concurrent general composition be achieved (without going the route of universal composability). We prove the negative. That is, any protocol that is secure under concurrent general composition is also secure under universal composability; therefore, the above impossibility results apply in a very general sense, and not just to the specific definition of universal composability. We note that the above result is unconditional and holds for even non-black-box simulation. However, it does follow the ideal/real model simulation-based paradigm for defining security. Therefore, impossibility is not demonstrated for weaker (and less desirable) notions of security.

Having ruled out the possibility of obtaining security under concurrent general composition, we turn to the question of concurrent self composition (where a secure protocol is executed many times in a network by itself). Surprisingly, we show that any protocol that is secure under concurrent self composition is also secure under concurrent general composition (even though in the latter case, arbitrary and maliciously designed protocols may also run in the network). Again, having met impossibility, we consider an even more relaxed scenario called m-bounded concurrent composition. In this scenario, an a-priori bound m on the number of concurrent execution is given and the protocol needs only to remain secure when this bound is not passed. We present lower bounds for this scenario demonstrating that any protocol that is secure under m-bounded concurrent composition must have bandwidth of at least m bits. Furthermore, if the protocol is proven secure using black-box simulation, then more than m rounds of communication are needed. This black-box lower bound is of interest because all known techniques for obtaining "highly efficient" protocols use black-box simulation. On the positive side, we show that any two-party functionality can be securely computed under m-bounded concurrent self composition (albeit with high round complexity and high bandwidth). Subsequent to the above work, constant-round (but high-bandwidth) protocols for m-bounded concurrent self composition in the two-party and multi-party settings were demonstrated respectively by Rosen and Pass (FOCS 2003) and Pass (STOC 2004). In addition, motivated by the above-described broad impossibility results, Prabhakaran and Sahai have investigated the possibility of obtaining secure protocols under weakened notions of security (STOC 2004).

The above-mentioned positive results on bounded-concurrent composition are less than satisfactory for two main reasons. First and foremost, the model of bounded concurrency is a problematic one to assume in real network settings. Note that the required assumption is a global bound on the number of executions, and not a local one. It is therefore not clear that such an assumption can reasonably be made. Second, our lower bounds demonstrate difficulties with obtaining highly efficient protocols for this setting. This situation provides motivation for searching for alternative, more reasonable, models where security may be obtained. One such model is the timing model where it is assumed that parties have local clocks that proceed at approximately the same rate (note that there is no requirement on clock synchronization, but just that they do not run at radically different rates). In this model, we show that any multiparty functionality can be securely computed under concurrent general composition, as long as the messages of other arbitrary protocols are (locally) delayed by a fixed number of time units.

Another interesting question that we have considered relates to the fact that all known protocols for secure multiparty computation that have information-theoretic security are conjectured to be secure under concurrent composition. (This conjecture has not been proven, but is widely believed.) The connection between security under composition and security in the face of computationally unbounded adversaries seems rather surprising. We present a series of results in this setting that deepens our understanding of this connection. We show, against accepted folklore, that statistical security in the information-theoretic setting does not imply security under concurrent general composition. In contrast, we show that perfect security does imply such security. A number of other results are also demonstrated, including the fact that statistical security implies a weaker form of composition (concurrent self composition with fixed inputs) and that a slight modification to any statistically-secure protocol suffices for obtaining security under concurrent general composition.

My book. The introduction of my book (below) contains a survey on the security of protocols under concurrent composition, as well as some of the material from above.

Note: In some places above, we have provided references to work (of others) that is highly relevant. In no way is this supposed to be a complete or current list. We hope, however, that it will be helpful in understanding the current state of knowledge on some of the topics discussed here.

Back Home