Paper 2015/1238

Asynchronous Secure Multiparty Computation in Constant Time

Ran Cohen


In the setting of secure multiparty computation, a set of mutually distrusting parties wish to securely compute a joint function. It is well known that if the communication model is asynchronous, meaning that messages can be arbitrarily delayed by an unbounded (yet finite) amount of time, secure computation is feasible if and only if at least two-thirds of the parties are honest, as was shown by Ben-Or, Canetti, and Goldreich [STOC'93] and by Ben-Or, Kelmer, and Rabin [PODC'94]. The running-time of all currently known protocols depends on the function to evaluate. In this work we present the first asynchronous MPC protocol that runs in constant time. Our starting point is the asynchronous MPC protocol of Hirt, Nielsen, and Przydatek [Eurocrypt'05, ICALP'08]. We integrate \emph{threshold fully homomorphic encryption} in order to reduce the interactions between the parties, thus completely removing the need for the expensive \emph{king-slaves} approach taken by Hirt et al.. Initially, assuming an honest majority, we construct a constant-time protocol in the asynchronous Byzantine agreement (ABA) hybrid model. Using a concurrent ABA protocol that runs in constant expected time, we obtain a constant expected time asynchronous MPC protocol, secure facing static malicious adversaries, assuming t<n/3.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2016
multiparty computationasynchronous communicationthreshold FHEconstant-time protocolsByzantine agreement.
Contact author(s)
cohenrb @ cs biu ac il
2016-01-04: revised
2015-12-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ran Cohen},
      title = {Asynchronous Secure Multiparty Computation in Constant Time},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1238},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.