Paper 2004/045

Lower Bounds and Impossibility Results for Concurrent Self Composition

Yehuda Lindell


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 {\em cannot} be securely computed under concurrent self composition, by any protocol. We also prove a {\em 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 {\em 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 {\em self} composition (where a single secure protocol is run many times) is actually equivalent to the seemingly more stringent requirement of security under concurrent {\em 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. This paper combines the results from a paper appearing in TCC'04 with the lower bound from a paper in STOC'03.
secure multiparty computationself compositiongeneral compositionlower boundsblack-box and non-black-box simulation
Contact author(s)
lindell @ us ibm com
2005-04-04: last of 2 revisions
2004-02-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yehuda Lindell},
      title = {Lower Bounds and Impossibility Results for Concurrent Self Composition},
      howpublished = {Cryptology ePrint Archive, Paper 2004/045},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.