Cryptology ePrint Archive: Report 2015/523

Efficient Constant Round Multi-Party Computation Combining BMR and SPDZ

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

Abstract: 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.

Category / Keywords: cryptographic protocols /

Original Publication (in the same form): IACR-CRYPTO-2015

Date: received 31 May 2015, last revised 1 Jun 2016

Contact author: Yehuda Lindell at biu ac il, benny@pinkas net, nigel@cs bris ac uk, ay yanay@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160601:093850 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]