Cryptology ePrint Archive: Report 2016/1066

Optimizing Semi-Honest Secure Multiparty Computation for the Internet

Aner Ben-Efraim and Yehuda Lindell and Eran Omri

Abstract: In the setting of secure multiparty computation, a set of parties with private inputs wish to compute some function of their inputs without revealing anything but their output. Over the last decade, the efficiency of secure \emph{two-party} computation has advanced in leaps and bounds, with speedups of some orders of magnitude, making it fast enough to be of use in practice. In contrast, progress on the case of multiparty computation (with more than two parties) has been much slower, with very little work being done. Currently, the only implemented efficient multiparty protocol has many rounds of communication (linear in the depth of the circuit being computed) and thus is not suited for Internet-like settings where latency is not very low.

In this paper, we construct highly efficient \emph{constant-round} protocols for the setting of multiparty computation for semi-honest adversaries. Our protocols work by constructing a multiparty garbled circuit, as proposed in BMR (Beaver et al., STOC 1990). Our first protocol uses oblivious transfer and constitutes the \textit{first} concretely-efficient constant-round multiparty protocol for the case of no honest majority. Our second protocol uses BGW, and is significantly more efficient than the FairplayMP protocol (Ben-David et al., CCS 2008) that also uses BGW.

We ran extensive experimentation comparing our different protocols with each other and with a highly-optimized implementation of semi-honest GMW. Due to our protocol being constant round, it significantly outperforms GMW in Internet-like settings. For example, with 13 parties situated in the Virginia and Ireland Amazon regions and the SHA256 circuit with 90,000 gates and of depth 4000, the overall running time of our protocol is 25 seconds compared to 335 seconds for GMW. Furthermore, our \emph{online time} is under half a second compared to 330 seconds for GMW.

Category / Keywords: cryptographic protocols / secure multiparty computation, semi-honest adversaries, constant-round protocols, concrete efficiency

Original Publication (with minor differences): ACM CCS 2016
DOI:
10.1145/2976749.2978347

Date: received 14 Nov 2016

Contact author: lindell at biu ac il

Available format(s): PDF | BibTeX Citation

Version: 20161115:151020 (All versions of this report)

Short URL: ia.cr/2016/1066

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]