Fast Fully Homomorphic Encryption Library over the Torus
version 1.1  Updated security parameters release date: 2020.02.21
version 1.0  first release date: 2017.05.02
version 1.0rc1  first prerelease date: 2017.04.05
version 0.1  Proof of concept release date: 2016.08.18
TFHE is opensource software distributed under the terms of the Apache 2.0 license. The scheme is described in the paper "Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds" presented at the IACR conference Asiacrypt 2016 by Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, Malika Izabachène.
The TFHE library implements a very fast gatebygate bootstrapping, based on [CGGI16]. Namely, any binary gate is evaluated homomorphically in about 13 milliseconds on a single core which improves [DM15] by a factor 50, and the mux gate takes about 26 CPUms (or 13ms on 2 cores).
The library implements a Ringvariant of the GSW [GSW13] cryptosystem and makes many optimizations described in [DM15] and [CGGI16].
It also implements a dedicated Fast Fourier Transformation for the anticyclic ring R[X]/(X^N+1), and uses AVX, AVX2 and FMA assembly vectorization instructions. The default parameter set achieves at least 110bit of cryptographic security, based on ideal lattice assumptions.
From the user point of view, the library can evaluate a netlist of binary gates homomorphically at a rate of about 50 gates per second per core, without decrypting its input. It suffices to provide the sequence of gates, as well as ciphertexts of the input bits. And the library computes ciphertexts of the output bits.
Unlike other libraries, TFHE has no restriction on the number of gates or on their composition. This makes the library usable with either manually crafted circuits, or with the output of automated circuit generation tools. For TFHE, optimal circuits have the smallest possible number of gates, and to a lesser extent, the possibility to evaluate them in parallel.
The library interface can be used in a regular C code. However, to compile the core of the library you will need a standard C++11 compiler. Currently, the project has been tested with the g++ >= 5.2 compiler and clang >=3.8 under Linux, as well as clang under MacOS. In the future, we plan to extend the compatibility to other compilers, platforms and operating systems.
At least one FFT processor is needed to run the project:
To build the library with the default options, run make
and make install
from the top level directory of the TFHE project. This assumes that the standard tool cmake is already installed on the system, and an
uptodate c++ compiler (i.e. g++ >=5.2 or clang >= 3.8) as well.
It will compile the shared library in optimized mode, and install it to the /usr/local/lib
folder.
If you want to choose additional compile options (i.e. other installation folder, debug mode, tests, fftw), you need to run cmake manually and pass the desired options:
mkdir build
cd build
cmake ../src DENABLE_TESTS=on DENABLE_FFTW=on DCMAKE_BUILD_TYPE=debug
make
The available options are the following:
Variable Name  values 

CMAKE_INSTALL_PREFIX  /usr/local installation folder (libs go in lib/ and headers in include/) 
CMAKE_BUILD_TYPE 

ENABLE_TESTS 
on/off compiles the library's unit tests and sample applications in the test/ folder. To enable this target, you first need to download google test sources: git submodule init; git submodule update (then, use ctest to run all unittests) 
ENABLE_FFTW  on/off compiles libtfhefftw.a, using FFTW3 (GPL licence) for fast FFT computations 
ENABLE_NAYUKI_PORTABLE  on/off compiles libtfhenayukiportable.a, using the fast C version of nayuki for FFT computations 
ENABLE_NAYUKI_AVX  on/off compiles libtfhenayukiavx.a, using the avx assembly version of nayuki for FFT computations 
ENABLE_SPQLIOS_AVX  on/off compiles libtfhespqliosavx.a, using tfhe's dedicated avx assembly version for FFT computations 
ENABLE_SPQLIOS_FMA  on/off compiles libtfhespqliosfma.a, using tfhe's dedicated fma assembly version for FFT computations 
The current parameters implemented in the TFHE library have been updated from the ones proposend in the original TFHE paper [CGGI16], according to the new estimates done in the JoC paper [CGGI19], and new attack models integrated in LWE estimator{:target="_blank"}. The implementation uses two sets of keys on two different noise levels, both required to execute the gate bootstrapping.
ciphertext dimension n

noise rate (stdev) sd

security bits $\lambda$  

KeySwitching key (LWE)  630  $2^{15}$  128 bits 
Bootstrapping key (RingLWE)  1024  $2^{25}$  130 bits 
Overall security  128 bits 
With these parameters, the gate bootstrapping runs in about 1020 ms
, depending on the machine: as instance, one bootstrapped binary gate takes about 13 ms
on a Intel i99900k CPU and about 17 ms
on an average i7 Xeon processor (single core).
Our security estimates are made by using the LWE estimator{:target="_blank"}. The estimates can change according to the new attacks proposed in the litterature and the updates of the estimator itself. If you want to use safe parameters on the library in production, please double check the estimates and update your code with the new parameters.
The code to use in the LWE estimator to estimate hardness for the standard deviation sd
($2^{25}$ in the example) and dimension n
(1024 in the example) is provided below. We recommend to target at least 128bits of security.
In our implementation, we use 32 bits integers (q=2**32
) and binary keys.
For the choice of all the other TFHE parameters, please refer to the noise formulas in [CGGI19].
Note: we estimate the parameters by using some of the models listed in the Estimate all the LWE and NTRU schemes{:target="_blank"}.
In particular, we consider the classical cost of BKZbeta on a lattice of dimension d
to be 2^(0.292*beta + 16.4 + log(8*d,2))
.
To obtain more conservative parameters, we suggest using the coreSVP methodology using classical cost 2^(0.292*beta)
and quantum cost 2^(0.265*beta)
.
# To reproduce the estimate run this snippet on http://aleph.sagemath.org/
from sage.all import load, sqrt, RR, ZZ, pi, oo
load('https://bitbucket.org/malb/lweestimator/raw/HEAD/estimator.py')
n = 1024 # ciphertext dimension (also, key entropy)
sd = 2**(25) # noise standard deviation
alpha = sqrt(2*pi)*sd # estimator defines noise rate = sqrt(2pi).stdev
q = 2**32 # for compatibility only
m = oo # the attacker can use as many samples he wishes
secret_distribution = (0,1)
success_probability = 0.99
# Chosen cost model
# BKZ cost models: CLASSICAL  0.292*beta + 16.4 + log(8*d,2)  primal
# i.e. BKZ.sieve = lambda beta, d, B: ZZ(2)**RR(0.292*beta + 16.4 + log(8*d,2))
print("CLASSICAL PRIMAL")
print(primal_usvp(n, alpha, q, secret_distribution=secret_distribution, m=m, success_probability=success_probability, reduction_cost_model=BKZ.sieve))
# BKZ cost models: CLASSICAL  0.292*beta + 16.4 + log(8*d,2)  dual
# i.e. BKZ.sieve = lambda beta, d, B: ZZ(2)**RR(0.292*beta + 16.4 + log(8*d,2))
print("CLASSICAL DUAL")
print(dual_scale(n, alpha, q, secret_distribution=secret_distribution, m=m, success_probability=success_probability, reduction_cost_model=BKZ.sieve))
# For more conservative parameters, both classical and quantum
# BKZ cost models: CLASSICAL  0.292 beta  primal
reduction_cost_model = lambda beta, d, B: ZZ(2)**RR(0.292*beta)
print("CLASSICAL PRIMAL (conservative)")
print(primal_usvp(n, alpha, q, secret_distribution=secret_distribution, m=m, success_probability=success_probability, reduction_cost_model=reduction_cost_model))
# BKZ cost models: CLASSICAL  0.292 beta  dual
print("CLASSICAL DUAL (conservative)")
print(dual_scale(n, alpha, q, secret_distribution=secret_distribution, m=m, success_probability=success_probability, reduction_cost_model=reduction_cost_model))
# BKZ cost models: QUANTUM  0.265 beta  primal
reduction_cost_model = lambda beta, d, B: ZZ(2)**RR(0.265*beta)
print("QUANTUM PRIMAL (conservative)")
print(primal_usvp(n, alpha, q, secret_distribution=secret_distribution, m=m, success_probability=success_probability, reduction_cost_model=reduction_cost_model))
# BKZ cost models: QUANTUM  0.265 beta  dual
print("QUANTUM DUAL (conservative)")
print(dual_scale(n, alpha, q, secret_distribution=secret_distribution, m=m, success_probability=success_probability, reduction_cost_model=reduction_cost_model))
_We would like to thank Fernando Virdia{:target="blank"} for the help in the estimation of the security parameters.
[CGGI19]: I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. TFHE: Fast Fully Homomorphic Encryptionover the Torus. In Journal of Cryptology, volume 33, pages 34–91 (2020). PDF{:target="_blank"}
[CGGI16]: I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In Asiacrypt 2016 (Best Paper), pages 333. PDF{:target="_blank"} Slides{:target="_blank"}
[DM15]: L. Ducas and D. Micciancio. FHEW: Bootstrapping homomorphic encryption in less than a second. In Eurocrypt 2015, pages 617640. PDF{:target="_blank"}
[GSW13]: C. Gentry, A. Sahai, and B. Waters. Homomorphic encryption from learning with errors: Conceptuallysimpler, asymptoticallyfaster, attributebased. In Crypto 2013, pages 7592. PDF{:target="_blank"}
[CGGI17]: I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. Faster Packed Homomorphic Operations and Efficient Circuit Bootstrapping for TFHE. ASIACRYPT (1) 2017: 377408. PDF{:target="_blank"} Slides{:target="_blank"}
[CGGI18]: I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. TFHE: Fast Fully Homomorphic Encryption over the Torus. IACR Cryptology ePrint Archive 2018: 421 (2018) (Invited JoC). PDF{:target="_blank"} Slides{:target="_blank"}
[BGG18]: C. Boura, N. Gama, M. Georgieva: Chimera: a unified framework for B/FV, TFHE and HEAAN fully homomorphic encryption and predictions for deep learning. IACR Cryptology ePrint Archive 2018: 758 (2018). PDF{:target="_blank"} Slides{:target="_blank"}
[CIM19]: S. Carpov, M. Izabachène, V. Mollimard: New Techniques for Multivalue Input Homomorphic Evaluation and Applications. CTRSA 2019: 106126. PDF{:target="_blank"}
[Google FHE]: Fully Homomorphic Encryption (FHE) github
[Concrete]: Concrete Operates oN Ciphertexts Rapidly by Extending TfhE. github
[Cingulata]: Compilation toolchain and runtime environment targeting TFHE github
[CGGTP19]: S. Carpov, N. Gama, M. Georgieva, J.R. TroncosoPastoriza: Privacypreserving semiparallel logistic regression training with Fully Homomorphic Encryption.(among the winners Idash 2018) IACR Cryptology ePrint Archive 2019: 101 (2019) PDF{:target="_blank"} Slides{:target="_blank"}
[CCS19]: H. Chen, I. Chillotti, Y. Song: MultiKey Homomophic Encryption from TFHE. IACR Cryptology ePrint Archive 2019: 116 (2019). PDF{:target="_blank"}
[BMMP18]: F. Bourse, M. Minelli, M. Minihold, P. Paillier: Fast Homomorphic Evaluation of Deep Discretized Neural Networks. CRYPTO (3) 2018: 483512. PDF{:target="_blank"}
[CGGI16]: I. Chillotti, N. Gama, M. Georgieva, M. Izabachène: A Homomorphic LWE Based Evoting Scheme. PQCrypto 2016: 245265. PDF{:target="_blank"} Slides{:target="_blank"}
[cuFHE]: CUDAaccelerated Fully Homomorphic Encryption Library: PDF{:target="_blank"}
(Please contact us to add your work based on TFHE)