Paper 2015/523

Efficient Constant Round Multi-Party Computation Combining BMR and SPDZ

Yehuda Lindell, Benny Pinkas, Nigel P. Smart, and Avishay Yanai


Recently, there has been huge progress in the field of concretely efficient secure computation, even while providing security in the presence of \emph{malicious adversaries}. This is especially the case in the two-party setting, where constant-round protocols exist that remain fast even over slow networks. However, in the multi-party setting, all concretely efficient fully-secure protocols, such as SPDZ, require many rounds of communication. In this paper, we present an MPC protocol that is fully-secure in the presence of malicious adversaries and for any number of corrupted parties. Our construction is based on the constant-round BMR protocol of Beaver et al., and is the first version of that protocol that is \emph{concretely} efficient for the dishonest majority case. Our protocol includes an online phase that is extremely fast and mainly consists of each party locally evaluating a garbled circuit. For the offline phase we present both a generic construction (using any underlying MPC protocol), and a highly efficient instantiation based on the SPDZ protocol. Our estimates show the protocol to be considerably more efficient than previous fully-secure multi-party protocols.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in CRYPTO 2015
Contact author(s)
Yehuda Lindell @ biu ac il
benny @ pinkas net
nigel @ cs bris ac uk
ay yanay @ gmail com
2017-12-19: last of 5 revisions
2015-05-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yehuda Lindell and Benny Pinkas and Nigel P.  Smart and Avishay Yanai},
      title = {Efficient Constant Round Multi-Party Computation Combining {BMR} and {SPDZ}},
      howpublished = {Cryptology ePrint Archive, Paper 2015/523},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.