Multi-key Fully-Homomorphic Encryption in the Plain Model

Prabhanjan Ananth, Abhishek Jain, ZhengZhong Jin, and Giulio Malavolta

Abstract

The notion of multi-key fully homomorphic encryption (multi-key FHE) [Löpez-Alt, Tromer, Vaikuntanathan, STOC'12] was proposed as a generalization of fully homomorphic encryption to the multiparty setting. In a multi-key FHE scheme for $n$ parties, each party can individually choose a key pair and use it to encrypt its own private input. Given $n$ ciphertexts computed in this manner, the parties can homomorphically evaluate a circuit $C$ over them to obtain a new ciphertext containing the output of $C$, which can then be decrypted via a decryption protocol. The key efficiency property is that the size of the (evaluated) ciphertext is independent of the size of the circuit. Multi-key FHE with one-round decryption [Mukherjee and Wichs, Eurocrypt'16], has found several powerful applications in cryptography over the past few years. However, an important drawback of all such known schemes is that they require a trusted setup. In this work, we address the problem of constructing multi-key FHE in the plain model. We obtain the following results: - A multi-key FHE scheme with one-round decryption based on the hardness of learning with errors (LWE), ring LWE, and decisional small polynomial ratio (DSPR) problems. - A variant of multi-key FHE where we relax the decryption algorithm to be non-compact -- i.e., where the decryption complexity can depend on the size of $C$ -- based on the hardness of LWE. We call this variant multi-homomorphic encryption (MHE). We observe that MHE is already sufficient for some applications of multi-key FHE.

Note: Subsumes ia.cr/2020/169

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in TCC 2020
Keywords
Fully Homomorphic EncryptionMultiparty Computation
Contact author(s)
prabhanjan va @ gmail com
abhishek @ cs jhu edu
zjin12 @ jhu edu
giulio malavolta @ hotmail it
History
2020-11-15: revised
See all versions
Short URL
https://ia.cr/2020/180

CC BY

BibTeX

@misc{cryptoeprint:2020/180,
author = {Prabhanjan Ananth and Abhishek Jain and ZhengZhong Jin and Giulio Malavolta},
title = {Multi-key Fully-Homomorphic Encryption in the Plain Model},
howpublished = {Cryptology ePrint Archive, Paper 2020/180},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/180}},
url = {https://eprint.iacr.org/2020/180}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.