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

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

doi:10.1007/978-3-662-53641-4_21

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 proceeding › Conference Contribution (Conference Proceeding)

23 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 language	English
Title of host publication	Theory of Cryptography
Subtitle of host publication	14th International Conference, TCC 2016-B, Beijing, China, October 31-November 3, 2016, Proceedings, Part I
Publisher	Springer
Pages	554-581
Number of pages	28
ISBN (Electronic)	9783662536414
ISBN (Print)	9783662536407
DOIs	https://doi.org/10.1007/978-3-662-53641-4_21
Publication status	Published - Nov 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9985
ISSN (Print)	0302-9743

Keywords

cryptographic protocols

Access to Document

10.1007/978-3-662-53641-4_21

http://eprint.iacr.org/2016/156Licence: CC BY

Handle.net

Persistent link

TIPS Fellowship
Smart, N. P.
1/10/16 → 30/09/21
Project: Research
UK-Israel MPC
Smart, N. P.
1/08/15 → 31/12/17
Project: Research
COED - Computing on Encrypted Data
Smart, N. P.
1/10/11 → 30/09/15
Project: Research

Cite this

Lindell, Y., Smart, N., & Soria-Vázquez, E. (2016). More Efficient Constant-Round Multi-Party Computation from BMR and SHE. In Theory of Cryptography: 14th International Conference, TCC 2016-B, Beijing, China, October 31-November 3, 2016, Proceedings, Part I (pp. 554-581). (Lecture Notes in Computer Science; Vol. 9985). Springer. https://doi.org/10.1007/978-3-662-53641-4_21

@inproceedings{b09e727549c5483a90d984e1b24bb385,

title = "More Efficient Constant-Round Multi-Party Computation from BMR and SHE",

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. ",

keywords = "cryptographic protocols",

author = "Yehuda Lindell and Nigel Smart and Eduardo Soria-V{\'a}zquez",

year = "2016",

month = nov,

doi = "10.1007/978-3-662-53641-4_21",

language = "English",

isbn = "9783662536407",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "554--581",

booktitle = "Theory of Cryptography",

}

More Efficient Constant-Round Multi-Party Computation from BMR and SHE. / Lindell, Yehuda ; Smart, Nigel; Soria-Vázquez, Eduardo.
Theory of Cryptography: 14th International Conference, TCC 2016-B, Beijing, China, October 31-November 3, 2016, Proceedings, Part I. Springer, 2016. p. 554-581 (Lecture Notes in Computer Science; Vol. 9985).

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

TY - GEN

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

AU - Lindell, Yehuda

AU - Smart, Nigel

AU - Soria-Vázquez, Eduardo

PY - 2016/11

Y1 - 2016/11

N2 - 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.

AB - 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.

KW - cryptographic protocols

U2 - 10.1007/978-3-662-53641-4_21

DO - 10.1007/978-3-662-53641-4_21

M3 - Conference Contribution (Conference Proceeding)

SN - 9783662536407

T3 - Lecture Notes in Computer Science

SP - 554

EP - 581

BT - Theory of Cryptography

PB - Springer

ER -

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

Abstract

Publication series

Keywords

Access to Document

Handle.net

Fingerprint

Projects

TIPS Fellowship

UK-Israel MPC

COED - Computing on Encrypted Data

Cite this