International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Concurrent Composition of Secure Protocols in the Timing Model

Authors:
Yael Kalai
Yehuda Lindell
Manoj Prabhakaran
Download:
URL: http://eprint.iacr.org/2005/036
Search ePrint
Search Google
Abstract: 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 {\em 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 {\em any} multiparty functionality under concurrent \emph{self} composition. We also show that it is possible to securely compute {\em any} multiparty functionality under concurrent {\em 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.
BibTeX
@misc{eprint-2005-12375,
  title={Concurrent Composition of Secure Protocols in the Timing Model},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / multiparty computation, concurrent general composition, timing model},
  url={http://eprint.iacr.org/2005/036},
  note={Appeared in STOC 2005. lindell@cs.biu.ac.il 13345 received 10 Feb 2005, last revised 16 Jul 2006},
  author={Yael Kalai and Yehuda Lindell and Manoj Prabhakaran},
  year=2005
}