Paper 2016/156

More Efficient Constant-Round Multi-Party Computation from BMR and SHE

Yehuda Lindell, Nigel P. Smart, and Eduardo Soria-Vazquez


We present a multi-party computation protocol in the case of dishonest majority which has very low round complexity. Our protocol sits philosophically between Gentry's Fully Homomorphic Encryption based protocol and the SPDZ-BMR protocol of Lindell et al (CRYPTO 2015). Our protocol avoids various inefficiencies of the previous two protocols. Compared to Gentry's protocol we only require Somewhat Homomorphic Encryption (SHE). Whilst in comparison to the SPDZ-BMR protocol we require only a quadratic complexity in the number of players (as opposed to cubic), we have fewer rounds, and we require less proofs of correctness of ciphertexts. Additionally, we present a variant of our protocol which trades the depth of the garbling circuit (computed using SHE) for some more multiplications in the offline and online phases.

Note: Corrected some misscounts and minor typos.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in TCC 2016
Contact author(s)
nigel @ cs bris ac uk
es15664 @ bristol ac uk
Yehuda Lindell @ biu ac il
2017-02-24: last of 5 revisions
2016-02-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yehuda Lindell and Nigel P.  Smart and Eduardo Soria-Vazquez},
      title = {More Efficient Constant-Round Multi-Party Computation from BMR and SHE},
      howpublished = {Cryptology ePrint Archive, Paper 2016/156},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.