Cryptology ePrint Archive: Report 2016/156
More Efficient Constant-Round Multi-Party Computation from BMR and SHE
Yehuda Lindell and Nigel P. Smart and Eduardo Soria-Vazquez
Abstract: 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.
Category / Keywords: cryptographic protocols /
Original Publication (in the same form): IACR-TCC-2016
Date: received 18 Feb 2016, last revised 24 Feb 2017
Contact author: nigel at cs bris ac uk,es15664@bristol ac uk,Yehuda Lindell@biu ac il
Available format(s): PDF | BibTeX Citation
Note: Corrected some misscounts and minor typos.
Version: 20170224:133108 (All versions of this report)
Short URL: ia.cr/2016/156
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]