Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds - Archive ouverte HAL Access content directly
Conference Papers Year : 2016

Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds

(1) , (1, 2) , (3) , (4)
1
2
3
4

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 1GB bootstrapping key size to 24MB, 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.
Not file

Dates and versions

cea-01832762 , version 1 (09-07-2018)

Identifiers

Cite

I. Chillotti, N. Gama, M. Georgieva, M. Izabachène. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. Advances in Cryptology – ASIACRYPT 2016. ASIACRYPT 2016. Lecture Notes in Computer Science, Dec 2016, Hanoi, Vietnam. pp.3-33, ⟨10.1007/978-3-662-53887-6_1⟩. ⟨cea-01832762⟩
194 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More