Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds
In this paper, we revisit fully homomorphic encryption (FHE) based on GSW and its ring variants. We notice that the internal product of GSW can be replaced by a simpler external product between a GSW and an LWE ciphertext.
- PDF / 724,612 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 25 Downloads / 263 Views
4
Laboratoire de Math´ematiques de Versailles, UVSQ, CNRS, Universit´e Paris-Saclay, 78035 Versailles, France [email protected] 2 Inpher, Lausanne, Switzerland [email protected] 3 Gemalto, 6 rue de la Verrerie, 92190 Meudon, France [email protected] CEA LIST, Point Courrier 172, 91191 Gif-sur-Yvette Cedex, France [email protected]
Abstract. In this paper, we revisit fully homomorphic encryption (FHE) based on GSW and its ring variants. We notice that the internal product of GSW can be replaced by a simpler external product between a GSW and an LWE ciphertext. We show that the bootstrapping scheme FHEW of Ducas and Micciancio [11] can be expressed only in terms of this external product. As a result, we obtain a speed up from less than 1 s to less than 0.1 s. We also reduce the 1 GB bootstrapping key size to 24 MB, preserving the same security levels, and we improve the noise propagation overhead by replacing exact decomposition algorithms with approximate ones. Moreover, our external product allows to explain the unique asymmetry in the noise propagation of GSW samples and makes it possible to evaluate deterministic automata homomorphically as in [13] in an efficient way with a noise overhead only linear in the length of the tested word. Finally, we provide an alternative practical analysis of LWE based scheme, which directly relates the security parameter to the error rate of LWE and the entropy of the LWE secret key. Keywords: Fully homomorphic encryption · Bootstrapping · Lattices · LWE · GSW
1
Introduction
Fully homomorphic encryption (FHE) allows to perform computations over encrypted data without decrypting them. This concept has long been regarded as an open problem until the breakthrough paper of Gentry in 2009 [15] which demonstrates the feasibility of computing any function on encrypted data. Since c International Association for Cryptologic Research 2016 J.H. Cheon and T. Takagi (Eds.): ASIACRYPT 2016, Part I, LNCS 10031, pp. 3–33, 2016. DOI: 10.1007/978-3-662-53887-6 1
4
I. Chillotti et al.
then, many constructions have appeared involving new mathematical and algorithmic concepts and improving efficiency. In homomorphic encryption, messages are encrypted with a noise that grows at each homomorphic evaluation of an elementary operation. In a somewhat encryption scheme, the number of homomorphic operations is limited, but can be made asymptotically large using bootstrapping [15]. This technical trick introduced by Gentry allows to evaluate arbitrary circuits by essentially evaluating the decryption function on encrypted secret keys. This step has remained very costly until the recent paper of Ducas and Micciancio [11], which presented a very fast bootstrapping procedure running in around 0.69 s, making an important step towards practical FHE for arbitrary NAND circuits. In this paper, we further improve the bootstrapping procedure. We first provide an intuitive formalization of LWE/RingLWE on numbers or polynomials over the real torus, obtained by combining the Scale-Inv
Data Loading...
