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

Yehuda Lindell, Nigel Smart, Eduardo Soria-Vázquez

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

17 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationTheory of Cryptography
Subtitle of host publication14th International Conference, TCC 2016-B, Beijing, China, October 31-November 3, 2016, Proceedings, Part I
PublisherSpringer
Pages554-581
Number of pages28
ISBN (Electronic)9783662536414
ISBN (Print)9783662536407
DOIs
Publication statusPublished - Nov 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9985
ISSN (Print)0302-9743

Keywords

  • cryptographic protocols

Fingerprint Dive into the research topics of 'More Efficient Constant-Round Multi-Party Computation from BMR and SHE'. Together they form a unique fingerprint.

Cite this