Hitchhiker's guide to the TFHE scheme

Also referred to as the holy grail of cryptography, Fully Homomorphic Encryption (FHE) allows for arbitrary calculations over encrypted data. First proposed as a challenge by Rivest et al. in 1978, the existence of an FHE scheme has only been shown by Gentry in 2009. However, until these days, existing general-purpose FHE schemes suffer from a substantial computational overhead, which has been vastly reduced since the original construction of Gentry, but it still poses an obstacle that prevents a massive practical deployment of FHE. The TFHE scheme by Chillotti et al. represents the state-of-the-art among general-purpose FHE schemes. This paper aims to serve as a thorough guide to the TFHE scheme, with a strong focus on the reliability of computations over encrypted data, and help researchers and developers understand the internal mechanisms of TFHE in detail. In particular, it may serve as a baseline for future improvements and/or modifications of TFHE or related schemes.