IACR News item: 24 February 2016
Chris Peikert, Sina Shiehian
ePrint Report
Traditional fully homomorphic encryption (FHE) schemes only allow
computation on data encrypted under a single key. L{\'o}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 based
on learning with errors (LWE). However, unlike the original
construction of L{\'o}pez-Alt \etal, these later LWE-based schemes
have the somewhat undesirable property of being ``single-hop'' with
respect to keys, i.e., 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 with respect to 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. Our systems also have smaller ciphertexts than the previous LWE-based ones; indeed, ciphertexts in our second construction are simply GSW ciphertexts with no auxiliary data.
In this work we construct two multi-key FHE schemes, based on LWE assumptions, which are \emph{multi-hop with respect to 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. Our systems also have smaller ciphertexts than the previous LWE-based ones; indeed, ciphertexts in our second construction are simply GSW ciphertexts with no auxiliary data.
Additional news items may be found on the IACR news page.