Paper 2020/304

Multiparty Homomorphic Encryption from Ring-Learning-With-Errors

Christian Mouchet, Juan Troncoso-Pastoriza, Jean-Philippe Bossuat, and Jean-Pierre Hubaux

Abstract

We propose and evaluate a secure-multiparty-computation (MPC) solution in the semi-honest model with dishonest majority that is based on multiparty homomorphic encryption (MHE). To support our solution, we introduce a multiparty version of the Brakerski-Fan-Vercauteren homomorphic cryptosystem and implement it in an open-source library. MHE-based MPC solutions have several advantages: Their transcript is public, their offline phase is compact, and their circuit-evaluation procedure is non-interactive. By exploiting these properties, the communication complexity of MPC tasks is reduced from quadratic to linear in the number of parties, thus enabling secure computation among potentially thousands of parties and in a broad variety of computing paradigms, from the traditional peer-to-peer setting to cloud-outsourcing and smart-contract technologies. MHE-based approaches can also outperform the state-of-the-art solutions, even for a small number of parties. We demonstrate this for three circuits: private input selection with application to private-information retrieval, component-wise vector multiplication with application to private-set intersection, and Beaver multiplication triples generation. For the first circuit, privately selecting one input among eight thousand parties' (of 32 KB each) requires only 1.31 MB of communication per party and completes in 61.7 seconds. For the second circuit with eight parties, our approach is 8.6 times faster and requires 39.3 times less communication than the current methods. For the third circuit and ten parties, our approach generates 20 times more triples per second while requiring 136 times less communication per-triple than an approach based on oblivious transfer. We implemented our scheme in the Lattigo library and open-sourced the code at https://github.com/ldsec/lattigo.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Proceedings on Privacy Enhancing Technologies, 2021, pp. 291–311
DOI
10.2478/popets-2021-0071
Keywords
secure multiparty computationhomomorphic encryptionlattice-based cryptography
Contact author(s)
christian mouchet @ epfl ch
juan troncoso-pastoriza @ epfl ch
jean-philippe bossuat @ epfl ch
jean-pierre hubaux @ epfl ch
History
2021-08-18: last of 2 revisions
2020-03-12: received
See all versions
Short URL
https://ia.cr/2020/304
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/304,
      author = {Christian Mouchet and Juan Troncoso-Pastoriza and Jean-Philippe Bossuat and Jean-Pierre Hubaux},
      title = {Multiparty Homomorphic Encryption from Ring-Learning-With-Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2020/304},
      year = {2020},
      doi = {10.2478/popets-2021-0071},
      note = {\url{https://eprint.iacr.org/2020/304}},
      url = {https://eprint.iacr.org/2020/304}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.