### Multi-Key FHE from LWE, Revisited

Chris Peikert and Sina Shiehian

##### Abstract

Traditional fully homomorphic encryption (FHE) schemes only allow computation on data encrypted under a \emph{single} key. Löpez-Alt, Tromer, and Vaikuntanathan (STOC 2012) proposed the notion of \emph{multi-key} FHE, which allows homomorphic computation on ciphertexts encrypted under different keys, and also gave a construction based on a (somewhat nonstandard) assumption related to NTRU.\@ More recently, Clear and McGoldrick (CRYPTO 2015), followed by Mukherjee and Wichs (EUROCRYPT 2016), proposed a multi-key FHE that builds upon the LWE-based FHE of Gentry, Sahai, and Waters (CRYPTO 2013). However, unlike the original construction of Löpez-Alt \etal, these later LWE-based schemes have the somewhat undesirable property of being single-hop for keys:'' all relevant keys must be known at the start of the homomorphic computation, and the output cannot be usefully combined with ciphertexts encrypted under other keys (unless an expensive bootstrapping'' step is performed). In this work we construct two multi-key FHE schemes, based on LWE assumptions, which are \emph{multi-hop for keys}: the output of a homomorphic computation on ciphertexts encrypted under a set of keys can be used in further homomorphic computation involving \emph{additional} keys, and so on. Moreover, incorporating ciphertexts associated with new keys is a relatively efficient native'' operation akin to homomorphic multiplication, and does not require bootstrapping (in contrast with all other LWE-based solutions). Our systems also have smaller ciphertexts than the previous LWE-based ones; in fact, ciphertexts in our second construction are simply GSW ciphertexts with no auxiliary data.

Available format(s)
Category
Foundations
Publication info
Keywords
fully homomorphic encryptionmulti-keyon-the-fly MPC
Contact author(s)
cpeikert @ alum mit edu
History
2016-08-24: last of 2 revisions
See all versions
Short URL
https://ia.cr/2016/196

CC BY

BibTeX

@misc{cryptoeprint:2016/196,
author = {Chris Peikert and Sina Shiehian},
title = {Multi-Key FHE from LWE, Revisited},
howpublished = {Cryptology ePrint Archive, Paper 2016/196},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/196}},
url = {https://eprint.iacr.org/2016/196}
}

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