Paper 2016/196

Multi-Key FHE from LWE, Revisited

Chris Peikert and Sina Shiehian


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.

Available format(s)
Publication info
Published by the IACR in TCC 2016
fully homomorphic encryptionmulti-keyon-the-fly MPC
Contact author(s)
cpeikert @ alum mit edu
2016-08-24: last of 2 revisions
2016-02-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chris Peikert and Sina Shiehian},
      title = {Multi-Key FHE from LWE, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2016/196},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.