Paper 2019/658

Two-Thirds Honest-Majority MPC for Malicious Adversaries at Almost the Cost of Semi-Honest

Jun Furukawa and Yehuda Lindell

Abstract

Secure multiparty computation (MPC) enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. Protocols for semi-honest adversaries guarantee security as long as the corrupted parties run the specified protocol and ensure that nothing is leaked in the transcript. In contrast, protocols for malicious adversaries guarantee security in the presence of arbitrary adversaries who can run any attack strategy. Security for malicious adversaries is typically what is needed in practice (and is always preferred), but comes at a significant cost. In this paper, we present the first protocol for a two-thirds honest majority that achieves security in the presence of malicious adversaries at essentially the exact same cost as the best known protocols for semi-honest adversaries. Our construction is not a general transformation and thus it is possible that better semi-honest protocols will be constructed which do not support our transformation. Nevertheless, for the current state-of-the-art for many parties (based on Shamir sharing), our protocol invokes the best semi-honest multiplication protocol exactly once per multiplication gate (plus some additional local computation that is negligible to the overall cost). Concretely, the best version of our protocol requires each party to send on average of just $2\frac23$ elements per multiplication gate (when the number of multiplication gates is at least the number of parties). This is four times faster than the previous-best protocol of Barak et al. (ACM CCS 2018) for small fields, and twice as fast as the previous-best protocol of Chida et al. (CRYPTO 2018) for large fields.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM CCS 2019
Keywords
secure multiparty computationhonest majorityconcrete efficiency
Contact author(s)
lindell @ biu ac il
jun furukawa @ necam com
History
2019-07-16: last of 2 revisions
2019-06-04: received
See all versions
Short URL
https://ia.cr/2019/658
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/658,
      author = {Jun Furukawa and Yehuda Lindell},
      title = {Two-Thirds Honest-Majority MPC for Malicious Adversaries at Almost the Cost of Semi-Honest},
      howpublished = {Cryptology ePrint Archive, Paper 2019/658},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/658}},
      url = {https://eprint.iacr.org/2019/658}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.