Paper 2016/870

Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène

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 (Eurocrypt 2015) can be expressed only in terms of this external product. As a result, we obtain a speed up from less than 1 second to less than 0.1 seconds. 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 (ePrint 2014/283) 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.

Note: Minor corrections and updated citations

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in ASIACRYPT 2016
Keywords
Fully Homomorphic EncryptionBootstrappingLatticesLWEGSW
Contact author(s)
ilaria chillotti @ uvsq fr
History
2017-02-20: last of 2 revisions
2016-09-10: received
See all versions
Short URL
https://ia.cr/2016/870
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/870,
      author = {Ilaria Chillotti and Nicolas Gama and Mariya Georgieva and Malika Izabachène},
      title = {Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds},
      howpublished = {Cryptology ePrint Archive, Paper 2016/870},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/870}},
      url = {https://eprint.iacr.org/2016/870}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.