Paper 2018/421

TFHE: Fast Fully Homomorphic Encryption over the Torus

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

Abstract

Abstract. This work describes a fast fully homomorphic encryption scheme over the torus (TFHE), that revisits, generalizes and improves the fully homomorphic encryption (FHE) based on GSW and its ring variants. The simplest FHE schemes consist in bootstrapped binary gates. In this gate bootstrapping mode, we show that the scheme FHEW of [29] can be expressed only in terms of external product between a GSW and a LWE ciphertext. As a consequence of this result and of other optimizations, we decrease the running time of their bootstrapping from 690ms to 13ms single core, using 16MB bootstrapping key instead of 1GB, and preserving the security parameter. In leveled homomorphic mode, we propose two methods to manipulate packed data, in order to decrease the ciphertext expansion and to optimize the evaluation of look-up tables and arbitrary functions in RingGSW based homomorphic schemes. We also extend the automata logic, introduced in [31], to the efficient leveled evaluation of weighted automata, and present a new homomorphic counter called TBSR, that supports all the elementary operations that occur in a multiplication. These improvements speed-up the evaluation of most arithmetic functions in a packed leveled mode, with a noise overhead that remains additive. We finally present a new circuit bootstrapping that converts LWE ciphertexts into low-noise RingGSW ciphertexts in just 137ms, which makes the leveled mode of TFHE composable, and which is fast enough to speed-up arithmetic functions, compared to the gate bootstrapping approach. Finally, we provide an alternative practical analysis of LWE based schemes, which directly relates the security parameter to the error rate of LWE and the entropy of the LWE secret key, and we propose concrete parameter sets and timing comparison for all our constructions.

Note: This paper is the full version of Asiacrypt 2016 and Asiacrypt 2017.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Journal of Cryptology 2019
Keywords
Fully Homomorphic EncryptionBootstrappingLatticesLWEGSWBoolean circuitDeterministic automata
Contact author(s)
ilaria chillotti @ kuleuven be
maria georgievabs @ gmail com
History
2019-04-02: revised
2018-05-10: received
See all versions
Short URL
https://ia.cr/2018/421
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/421,
      author = {Ilaria Chillotti and Nicolas Gama and Mariya Georgieva and Malika Izabachène},
      title = {TFHE: Fast Fully Homomorphic Encryption over the Torus},
      howpublished = {Cryptology ePrint Archive, Paper 2018/421},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/421}},
      url = {https://eprint.iacr.org/2018/421}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.