Cryptology ePrint Archive: Report 2020/304

Multiparty Homomorphic Encryption from Ring-Learning-With-Errors

Christian Mouchet and Juan Troncoso-Pastoriza and 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, based on multiparty homomorphic encryption (MHE). To support this solution, we introduce a multiparty version of the Brakerski-Fan-Vercauteren lattice-based homomorphic cryptosystem, implement it in an open-source library, and evaluate its performance. We show that such MHE-based MPC solutions have several advantages over current approaches: Their public transcripts and non-interactive circuit-evaluation capabilities enable a broad variety of computing paradigms, ranging from the traditional peer-to-peer setting to cloud-outsourcing and smart-contract technologies. Exploiting these properties, the communication complexity of MPC tasks can be reduced from quadratic to linear in the number of parties, thus enabling secure computation among thousands of parties. Additionally, MHE-based approaches can outperform the state-of-the-art even for a small number of parties. We demonstrate this for three circuits: component-wise vector multiplication with application to private-set intersection, private input selection with application to private-information retrieval, and multiplication triples generation. For the first circuit evaluated among eight parties, our approach is 8.6 times faster and requires 39.3 times less communication than the state-of-the-art approach. The input selection circuit over eight thousand parties completed in 61.7 seconds and required 1.31 MB of communication per party.

Category / Keywords: cryptographic protocols / secure multiparty computation, homomorphic encryption, lattice-based cryptography

Date: received 8 Mar 2020, last revised 22 Dec 2020

Contact author: christian mouchet at epfl ch,juan troncoso-pastoriza@epfl ch,jean-philippe bossuat@epfl ch,jean-pierre hubaux@epfl ch

Available format(s): PDF | BibTeX Citation

Version: 20201222:154623 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]