Multiparty Homomorphic Encryption from Ring-Learning-with-Errors
Authors: Christian Mouchet (École polytechnique fédérale de Lausanne), Juan Troncoso-Pastoriza (École polytechnique fédérale de Lausanne), Jean-Philippe Bossuat (École polytechnique fédérale de Lausanne), Jean-Pierre Hubaux (École polytechnique fédérale de Lausanne)
Volume: 2021
Issue: 4
Pages: 291–311
DOI: https://doi.org/10.2478/popets-2021-0071
Abstract: We propose and evaluate a securemultiparty-computation (MPC) solution in the semihonest 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 noninteractive. 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 github.com/ldsec/lattigo.
Keywords: secure multiparty computation, homomorphic encryption
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
