Paper 2017/862

Efficient Scalable Constant-Round MPC via Garbled Circuits

Aner Ben-Efraim, Yehuda Lindell, and Eran Omri

Abstract

In the setting of secure multiparty computation, a set of mutually distrustful parties carry out a joint computation of their inputs, without revealing anything but the output. Over recent years, there has been tremendous progress towards making secure computation practical, with great success in the two-party case. In contrast, in the multiparty case, progress has been much slower, even for the case of semi-honest adversaries. In this paper, we consider the case of constant-round multiparty computation, via the garbled circuit approach of BMR (Beaver et al., STOC 1990). In recent work, it was shown that this protocol can be efficiently instantiated for semi-honest adversaries (Ben-Efraim et al., ACM CCS 2016). However, it scales very poorly with the number of parties, since the cost of garbled circuit evaluation is quadratic in the number of parties, per gate. Thus, for a large number of parties, it becomes expensive. We present a new way of constructing a BMR-type garbled circuit that can be evaluated with only a constant number of operations per gate. Our constructions use key-homomorphic pseudorandom functions (one based on DDH and the other on Ring-LWE) and are concretely efficient. In particular, for a large number of parties (e.g., 100), our new circuit can be evaluated faster than the standard BMR garbled circuit that uses only AES computations. Thus, our protocol is an important step towards achieving concretely efficient large-scale multiparty computation for Internet-like settings (where constant-round protocols are needed due to high latency).

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2017
Keywords
Garbled CircuitsConstant Round MPCKey-Homomorphic PRFsConcrete Efficiency
Contact author(s)
anermosh @ post bgu ac il
History
2017-09-11: received
Short URL
https://ia.cr/2017/862
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/862,
      author = {Aner Ben-Efraim and Yehuda Lindell and Eran Omri},
      title = {Efficient Scalable Constant-Round MPC via Garbled Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2017/862},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/862}},
      url = {https://eprint.iacr.org/2017/862}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.