Concurrent General Composition of Secure Protocols in the Timing Model

Yael Kalai, Yehuda Lindell, Manoj Prabhakaran


Broad impossibility results have recently been proven regarding the feasibility of obtaining protocols that remain secure under concurrent composition, unless an honest majority or trusted setup phase are assumed. 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). One approach for bypassing these impossibility results is to consider more limited settings of concurrency that still realistically model real-world networks. 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., proceed at approximately the same rate). We show that under this timing assumption, it is possible to securely compute any multi-party functionality under concurrent general composition (as long as messages from the arbitrary other protocols are delayed for a specified amount of time).

Postscript, gzipped Postscript.

Back Home