Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lower Bounds and Impossibility Results for Concurrent Self Composition.

Yehuda Lindell

Published Jan 1, 2004• 0 citations
OpenAlex

Abstract

In the setting of concurrent self composition, a single protocol is executed many times concurrently by a single set of parties. In this paper, we prove lower bounds and impossibility results for secure protocols in this setting. First and foremost, we prove that there exist large classes of functionalities that cannot be securely computed under concurrent self composition, by any protocol. We also prove a communication complexity lower bound on protocols that securely compute a large class of functionalities in this setting. Specifically, we show that any protocol that computes a functionality from this class and remains secure for m concurrent executions, must have bandwidth of at least m bits. The above results are unconditional and hold for any type of simulation (i.e., even for non-black-box simulation). In addition, we prove a severe lower bound on protocols that are proven secure using black-box simulation. Specifically, we show that any protocol that computes the blind signature or oblivious transfer functionalities and remains secure for m concurrent executions, where security is proven via black-box simulation, must have at least m rounds of communication. Our results hold for the plain model, where no trusted setup phase is assumed. While proving our impossibility results, we also show that for many functionalities, security under concurrent self composition (where a single secure protocol is run many times) is actually equivalent to the seemingly more stringent requirement of security under concurrent general composition (where a secure protocol is run concurrently with other arbitrary protocols). This observation has significance beyond the impossibility results that are derived by it for concurrent self composition.

Related papers

Concurrent Composition of Secure Protocols in the Timing Model.

Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran

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.

•Jan 1, 2005•3 citations

Protocols for Bounded-Concurrent Secure Two-Party Computation in the Plain Model.

Yehuda Lindell

Until recently, most research on the topic of secure computation focused on the stand-alone model, where a single protocol execution takes place. In this paper, we construct protocols for the setting of bounded-concurrent self composition, where a (single) secure protocol is run many times concurrently, and there is a predetermined bound on the number of concurrent executions. In short, we show that any two-party functionality can be securely computed under boundedconcurrent self composition, in the plain model (where the only setup assumption made is that the parties communicate via authenticated channels). Our protocol provides the first feasibility result for general two-party computation in the plain model, for any model of concurrency. All previous protocols assumed a trusted setup phase in order to obtain a common reference string. On the downside, the number of rounds of communication in our protocol is super-linear in the bound on the number of concurrent executions. However, we believe that our constructions will lead to more efficient protocols for this task.

•Jan 1, 2003•6 citations

Bounded-concurrent secure two-party computation without setup assumptions

Yehuda Lindell

In this paper we study the feasibility of obtaining protocols for general two-party computation that remain secure under concurrent composition. (A general protocol can be used for obtaining secure computation of any functionality.) We consider a scenario where no trusted setup is assumed (and so, for example, there is no common reference string available to the parties); we call this the "plain model". We present both negative and positive results for this model. Specifically, we show that a general two-party protocol that remains secure for m concurrent executions and can be proven via black-box simulation, must have more than m rounds of communication. An important corollary of this result is that there do not exist protocols for black-box secure general two-party computation for the case of unbounded concurrency (where any polynomial number of concurrent executions may be run). On the positive side, we show that under general cryptographic assumptions, there exist secure protocols for general two-party computation in the model of bounded concurrent composition (in this model the number of concurrent executions is fixed and the protocol design may depend on this number). Our protocol has O(m) rounds of communication, where m is the bound on the number of concurrent executions, and uses both black-box and non black-box techniques. We note that this protocol constitutes the first feasibility result for general two-party computation without setup assumptions for any model of concurrency.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2003•117 citations

Bounded-concurrent secure two-party computation without setup assumptions

Yehuda Lindell

In this paper we study the feasibility of obtaining protocols for general two-party computation that remain secure under concurrent composition. (A general protocol can be used for obtaining secure computation of any functionality.) We consider a scenario where no trusted setup is assumed (and so, for example, there is no common reference string available to the parties); we call this the "plain model". We present both negative and positive results for this model. Specifically, we show that a general two-party protocol that remains secure for m concurrent executions and can be proven via black-box simulation, must have more than m rounds of communication. An important corollary of this result is that there do not exist protocols for black-box secure general two-party computation for the case of unbounded concurrency (where any polynomial number of concurrent executions may be run). On the positive side, we show that under general cryptographic assumptions, there exist secure protocols for general two-party computation in the model of bounded concurrent composition (in this model the number of concurrent executions is fixed and the protocol design may depend on this number). Our protocol has O(m) rounds of communication, where m is the bound on the number of concurrent executions, and uses both black-box and non black-box techniques. We note that this protocol constitutes the first feasibility result for general two-party computation without setup assumptions for any model of concurrency.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2003•10 citations

General composition and universal composability in secure multi-party computation

Yehuda Lindell

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.

Annual Symposium on Foundations of Computer Science•Mar 2, 2004•57 citations

Concurrent general composition of secure protocols in the timing model

Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran

In the setting of secure multiparty computation, a set of mutually distrustful parties wish to jointly compute some function of their input (i.e., they wish to securely carry out some distributed task). %The joint computation should be such that even 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 where there is no honest majority (or trusted setup).In this paper, we investigate the feasibility of obtaining secure multiparty protocols in a network where certain time bounds are assumed. Specifically, the security of our protocols rely on the very reasonable assumption that local clocks do not "drift" too much (i.e., it is assumed that they proceed at approximately the same rate). We show that under this mild timing assumption, it is possible to securely compute any functionality under concurrent general composition (as long as messages from the arbitrary other protocols are delayed for a specified amount of time).

ACM Symposium on Theory of Computing (STOC)•May 22, 2005•45 citations
In the setting of concurrent self composition, a single protocol is executed many times concurrently by a single set of parties. In this paper, we prove lower bounds and impossibility results for secure protocols in this setting. First and foremost, we prove that there exist large classes of functionalities that cannot be securely computed under concurrent self composition, by any protocol. We also prove a communication complexity lower bound on protocols that securely compute a large class of functionalities in this setting. Specifically, we show that any protocol that computes a functionality from this class and remains secure for m concurrent executions, must have bandwidth of at least m bits. The above results are unconditional and hold for any type of simulation (i.e., even for non-black-box simulation). In addition, we prove a severe lower bound on protocols that are proven secure using black-box simulation. Specifically, we show that any protocol that computes the blind signature or oblivious transfer functionalities and remains secure for m concurrent executions, where security is proven via black-box simulation, must have at least m rounds of communication. Our results hold for the plain model, where no trusted setup phase is assumed. While proving our impossibility results, we also show that for many functionalities, security under concurrent self composition (where a single secure protocol is run many times) is actually equivalent to the seemingly more stringent requirement of security under concurrent general composition (where a secure protocol is run concurrently with other arbitrary protocols). This observation has significance beyond the impossibility results that are derived by it for concurrent self composition.
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.
Until recently, most research on the topic of secure computation focused on the stand-alone model, where a single protocol execution takes place. In this paper, we construct protocols for the setting of bounded-concurrent self composition, where a (single) secure protocol is run many times concurrently, and there is a predetermined bound on the number of concurrent executions. In short, we show that any two-party functionality can be securely computed under boundedconcurrent self composition, in the plain model (where the only setup assumption made is that the parties communicate via authenticated channels). Our protocol provides the first feasibility result for general two-party computation in the plain model, for any model of concurrency. All previous protocols assumed a trusted setup phase in order to obtain a common reference string. On the downside, the number of rounds of communication in our protocol is super-linear in the bound on the number of concurrent executions. However, we believe that our constructions will lead to more efficient protocols for this task.
In this paper we study the feasibility of obtaining protocols for general two-party computation that remain secure under concurrent composition. (A general protocol can be used for obtaining secure computation of any functionality.) We consider a scenario where no trusted setup is assumed (and so, for example, there is no common reference string available to the parties); we call this the "plain model". We present both negative and positive results for this model. Specifically, we show that a general two-party protocol that remains secure for m concurrent executions and can be proven via black-box simulation, must have more than m rounds of communication. An important corollary of this result is that there do not exist protocols for black-box secure general two-party computation for the case of unbounded concurrency (where any polynomial number of concurrent executions may be run). On the positive side, we show that under general cryptographic assumptions, there exist secure protocols for general two-party computation in the model of bounded concurrent composition (in this model the number of concurrent executions is fixed and the protocol design may depend on this number). Our protocol has O(m) rounds of communication, where m is the bound on the number of concurrent executions, and uses both black-box and non black-box techniques. We note that this protocol constitutes the first feasibility result for general two-party computation without setup assumptions for any model of concurrency.
In this paper we study the feasibility of obtaining protocols for general two-party computation that remain secure under concurrent composition. (A general protocol can be used for obtaining secure computation of any functionality.) We consider a scenario where no trusted setup is assumed (and so, for example, there is no common reference string available to the parties); we call this the "plain model". We present both negative and positive results for this model. Specifically, we show that a general two-party protocol that remains secure for m concurrent executions and can be proven via black-box simulation, must have more than m rounds of communication. An important corollary of this result is that there do not exist protocols for black-box secure general two-party computation for the case of unbounded concurrency (where any polynomial number of concurrent executions may be run). On the positive side, we show that under general cryptographic assumptions, there exist secure protocols for general two-party computation in the model of bounded concurrent composition (in this model the number of concurrent executions is fixed and the protocol design may depend on this number). Our protocol has O(m) rounds of communication, where m is the bound on the number of concurrent executions, and uses both black-box and non black-box techniques. We note that this protocol constitutes the first feasibility result for general two-party computation without setup assumptions for any model of concurrency.
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.
In the setting of secure multiparty computation, a set of mutually distrustful parties wish to jointly compute some function of their input (i.e., they wish to securely carry out some distributed task). %The joint computation should be such that even 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 where there is no honest majority (or trusted setup).In this paper, we investigate the feasibility of obtaining secure multiparty protocols in a network where certain time bounds are assumed. Specifically, the security of our protocols rely on the very reasonable assumption that local clocks do not "drift" too much (i.e., it is assumed that they proceed at approximately the same rate). We show that under this mild timing assumption, it is possible to securely compute any functionality under concurrent general composition (as long as messages from the arbitrary other protocols are delayed for a specified amount of time).