Paper 2015/1238

Asynchronous Secure Multiparty Computation in Constant Time

Ran Cohen

Abstract

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.

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

BibTeX

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