Paper 2016/196

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.

Note: Additional details on bootstrapping.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in TCC 2016
Keywords
fully homomorphic encryptionmulti-keyon-the-fly MPC
Contact author(s)
cpeikert @ alum mit edu
History
2016-08-24: last of 2 revisions
2016-02-24: received
See all versions
Short URL
https://ia.cr/2016/196
License
Creative Commons Attribution
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.