Research on Secure Protocol Composition
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
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
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.
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]).
Y. Lindell, A. Lysyanskaya and T. Rabin.
On the Composition of Authenticated Byzantine Agreement.
In the 34th STOC, pages 514-523, 2002. Full version available.
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.
R. Canetti, Y. Lindell, R. Ostrovsky and A. Sahai.
Universally Composable Two-Party and Multi-Party Secure Computation.
In the 34th STOC, pages 494-503, 2002. Full version available.
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.
R. Canetti, E. Kushilevitz and Y. Lindell. On the Limitations
of Universally Composable Two-Party Computation Without Set-Up
In the Journal of Cryptology, 19(2):135-167, 2006.
An extended abstract appeared in Eurocrypt 2003, Springer-Verlag (LNCS 2656), pages 68-86, 2003.
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.
Y. Lindell. General Composition and Universal Composability
in Secure Multi-Party Computation.
To appear in the Journal of Cryptology.
An extended abstract appeared in the 44th FOCS, pages 394-403, 2003.
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
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).
Y. Lindell. Lower Bounds for Concurrent Self Composition.
In the 1st Theory of Cryptography Conference (TCC), Springer-Verlag (LNCS 2951), pages 203-222, 2004.
The full version appears in the Journal of Cryptology, 21(2):200-249, 2008
(this version combines the results of the paper at TCC 2004 together with the lower bound from the paper appearing next here).
Y. Lindell. Bounded-Concurrent Secure Two-Party Computation Without Setup Assumptions.
In the 35th STOC, pages 683-692, 2003.
The full version of the upper bound from this paper appears in the Chicago Journal of Theoretical Computer
Science, 2006(1):1-50, 2006.
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.
- Y.T. Kalai, Y. Lindell and M. Prabhakaran.
Concurrent Composition of Secure Protocols in the
In the Journal of Cryptology, 20(4):431-492, 2007.
An extended abstract appeared in the 37th STOC, pages 644-653, 2005.
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.
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.
E. Kushilevitz, Y. Lindell and T. Rabin. Information-Theoretically
Secure Protocols and Security Under Composition.
In the 38th STOC, pages 109-118, 2006. To appear in SICOMP.
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