Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / fully homomorphic encryption, multi-key, on-the-fly MPC

Original Publication (in the same form): IACR-TCC-2016

Date: received 23 Feb 2016, last revised 24 Aug 2016

Contact author: cpeikert at alum mit edu

Available format(s): PDF | BibTeX Citation

Note: Additional details on bootstrapping.

Version: 20160824:071208 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]