Paper 2017/816

A Framework for Constructing Fast MPC over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority

Yehuda Lindell and Ariel Nof


Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. The two classic adversary models considered are \emph{semi-honest} (where the adversary follows the protocol specification but tries to learn more than allowed by examining the protocol transcript) and \emph{malicious} (where the adversary may follow any arbitrary attack strategy). Protocols for semi-honest adversaries are often far more efficient, but in many cases the security guarantees are not strong enough. In this paper, we present a new efficient method for ``compiling'' a large class of protocols that are secure in the presence of semi-honest adversaries into protocols that are secure in the presence of malicious adversaries. Our method assumes an honest majority (i.e., that $t<n/2$ where $t$ is the number of corrupted parties and $n$ is the number of parties overall), and is applicable to many semi-honest protocols based on secret-sharing. In order to achieve high efficiency, our protocol is \emph{secure with abort} and does not achieve fairness, meaning that the adversary may receive output while the honest parties~do~not. We present a number of instantiations of our compiler, and obtain protocol variants that are very efficient for both a small and large number of parties. We implemented our protocol variants and ran extensive experiments to compare them with each other. Our results show that secure computation with an honest majority can be practical, even with security in the presence of malicious adversaries. For example, we securely compute a large arithmetic circuit of depth 20 with 1,000,000 multiplication gates, in approximately 0.5 seconds with three parties, and approximately 29 seconds with 50 parties, and just under 1 minute with 90 parties.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM CCS 2017
Contact author(s)
nofdinar @ gmail com
2018-12-12: last of 3 revisions
2017-08-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yehuda Lindell and Ariel Nof},
      title = {A Framework for Constructing Fast MPC over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority},
      howpublished = {Cryptology ePrint Archive, Paper 2017/816},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.