TFHE: Fast Fully Homomorphic Encryption over the Torus

v1.0.1 -- TFHE for Linux and MacOs, date: 2017.08.15
v1.0 -- First official release, date: 2017.05.02
v1.0-rc2 -- Second release candidate, date: 2017.04.21
v1.0-rc1 -- First release candidate, date: 2017.04.05
v0.1 -- Proof of Concept, date: 2016.08.10

TFHE is an open-source library for fully homomorphic encryption, distributed under the terms of the Apache 2.0 license.

The underlying scheme is described in best paper of the IACR conference Asiacrypt 2016: “Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds”, presented by Ilaria Chillotti, Nicolas Gama, Mariya Georgieva and Malika Izabachène.

Description

TFHE is a C/C++ library which implements a very fast gate-by-gate bootstrapping, based on [CGGI16] and [CGGI17]. The library allows to evaluate an arbitrary boolean circuit composed of binary gates, over encrypted data, without revealing any information on the data.

The library supports the homomorphic evaluation of the 10 binary gates (And, Or, Xor, Nand, Nor, etc…), as well as the negation and the Mux gate. Each binary gate takes about 13 milliseconds single-core time to evaluate, which improves [DM15] by a factor 53, and the mux gate takes about 26 CPU-ms.

Unlike other libraries, the gate-bootstrapping mode of TFHE has no restriction on the number of gates or on their composition. This allows to perform any computation over encrypted data, even if the actual function that will be applied is not yet known when the data is encrypted. The library is easy to use with either manually crafted circuits, or with the output of automated circuit generation tools.

From the user point of view, the library can:

Under the hood

The library implements a Ring-variant of the GSW [GSW13] cryptosystem and makes many optimizations described in [DM15], [CGGI16] and [CGGI17].

It also implements a dedicated Fast Fourier Transformation for the anticyclic ring \(\mathbb{R}[X]/(X^N+1)\), and uses AVX assembly vectorization instructions. The default parameter set achieves a 110-bit cryptographic security, based on ideal lattice assumptions.

Since the running time per gate seems to be the bottleneck of fully homomorphic encryption, an optimal circuits for TFHE is most likely a circuit with the smallest possible number of gates, and to a lesser extent, the possibility to evaluate them in parallel.

Dependencies

The library interface can be used in a regular C code. However, to compile the core of the library you will need a standard x86_64 C++11 compiler. The project has been tested and reported to work with the GNU compiler g++/gcc (>=5.2) as well as the clang compiler (>=3.8) on both Linux and MacOS platforms. Compilation under Windows is not supported at this time.

At least one FFT processor is needed to run the project:

References

[CGGI17]: I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. Improving TFHE: faster packed homomorphic operations and efficient circuit bootstrapping. Asiacrypt 2017. Cryptology ePrint Archive, report 2017/430.

[CGGI16]: I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. Asiacrypt 2016. Cryptology ePrint Archive, report 2016/870.

[DM15]: L. Ducas and D. Micciancio. FHEW: Bootstrapping homomorphic encryption in less than a second. In Eurocrypt 2015, pages 617-640.

[GSW13]: C. Gentry, A. Sahai, and B. Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In Crypto 2013, pages 75-92