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

Journal of Cryptology

Lower Bounds and Impossibility Results for Concurrent Self Composition

Yehuda Lindell

Published Sep 27, 2007• 36 citations
Publisher
DOI
10.1007/s00145-007-9015-5

Related papers

Lower Bounds for Concurrent Self Composition

Yehuda Lindell

Lecture notes in computer science•Jan 1, 2004•105 citations

New Impossibility Results for Concurrent Composition and a Non-interactive Completeness Theorem for Secure Computation

Shweta Agrawal, Vipul Goyal, Abhishek Jain +2 more

Lecture notes in computer science•Jan 1, 2012•18 citations

Simulatable Security and Polynomially Bounded Concurrent Composition.

Dennis Hofheinz, Dominique Unruh

•Jan 1, 2006•2 citations

Concurrent Composition in the Bounded Quantum Storage Model

Dominique Unruh

Lecture notes in computer science•Jan 1, 2011•17 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

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•60 citations
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.
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.