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

By Yehuda Lindell, Nigel P. Smart, Eduardo Soria-Vazquez. 2016

215 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Information Systems

Citations in the corpus

Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ (2019, background): “First and foremost, the works of [16,25] build directly on this work and show how to construct the BMR garbled circuit more efficiently.”
Global-Scale Secure Multiparty Computation (2017, methodology): “However, state-of-the-art protocols based on BMR that are maliciously secure against corruption of n − 1 parties require either O (n) somewhat homomorphic encryptions [32] or O (n) SPDZ multiplication subprotocols [31] per AND gate both of which are relatively inefficient.”