Multi-key FHE from LWE, Revisited
Traditional fully homomorphic encryption (FHE) schemes only allow computation on data encrypted under a single key. López-Alt, Tromer, and Vaikuntanathan (STOC 2012) proposed the notion of multi-key FHE, which allows homomorphic computation on ciphertexts
- PDF / 411,238 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 206 Views
Abstract. Traditional fully homomorphic encryption (FHE) schemes only allow computation on data encrypted under a single key. L´ opez-Alt, Tromer, and Vaikuntanathan (STOC 2012) proposed the notion of 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´ opez-Alt et al., 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 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 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.
1
Introduction
Secure multiparty computation (MPC) is an important and well-studied problem in cryptography. In MPC, multiple users want to jointly perform a computation on their respective inputs via an interactive protocol. Informally, the goal is for the protocol to reveal nothing more than the output of the computation. C. Peikert—This material is based upon work supported by the National Science Foundation under CAREER Award CCF-1054495 and CNS-1606362, and by the Alfred P. Sloan Foundation. The views expressed are those of the authors and do not necessarily reflect the official policy or position of the National Science Foundation or the Sloan Foundation. c International Association for Cryptologic Research 2016 M. Hirt and A. Smith (Eds.): TCC 2016-B, Part II, LNCS 9986, pp. 217–238, 2016. DOI: 10.1007/978-3-662-53644-5 9
218
C. Peikert and S. Shiehian
Fully homomorphic encryption (FHE) is a powerful tool for constructing secure MPC protocols. One approach suggested in Gentry’s seminal work [9], and later optimized by Asharov et al. [4], is to have an initial phase in which all parties run a protocol to generate a sharing of an FHE secret key, then use the public key to encrypt their inputs and publish the ciphertexts. The parties then locally compute an encryption of the output using homomorphic operations. Finally, they run a protocol to decrypt the encrypted output, usin
Data Loading...
