MOSFHET: Optimized Software for FHE over the Torus Antonio Guimarães $ ^{1} $ · Edson Borin $ ^{2} $ · Diego F. Aranha $ ^{3} $ Abstract Homomorphic encryption is one of the most secure solutions for processing sensitive information in untrusted environments. Recent advances have improved the efficiency of homomorphic encryption for evaluating approximate arithmetic and linear and arbitrary functions. The TFHE scheme [Chillotti et al., 2016] is the current state-of-the-art for evaluating arbitrary functions. This work focuses on improving its performance. The paper is divided into two parts. First, we review and implement the main techniques to improve performance or error behavior in TFHE proposed so far. Then, we introduce novel improvements to several of them and new approaches to implement some commonly used procedures. We also show which proposals can be suitably combined to achieve better results. We provide a single library containing all the reviewed techniques as well as our original contributions. Among the techniques we introduce, we highlight a new method for multi-value bootstrapping based on blind rotation unfolding and a faster-than-memory seed expansion, which introduces speedups of up to 2 times to basic arithmetic operations. Keywords Homomorphic encryption · TFHE · Functional bootstrap · Programmable bootstrap · Efficient implementation 1 Introduction The idea of performing computation over encrypted data was a long-chased goal in the cryptography community. The concept was first defined in 1978 by Rivest et al. [1], but for decades proposed solutions only achieved partial homomorphism. In 2009, Gentry [2] presented the first Fully Homomorphic Encryption (FHE) scheme, based on ideal lattices, enabling arbitrary computation through the evaluation of logic gates. Efficiency was a problem from the start, but Gentry's work also established a blueprint later used to build more efficient FHE schemes based on the Learning With Errors (LWE) problem [3] and its variants [4, 5]. Many of these follow-up works presented significant improvements in efficiency-wise, but the literature generally evolved around the needs of specific use cases, leaving behind, in terms of performance, capabilities such as the evaluation of arbitrary functions. Currently, one of the most efficient solutions for homomorphic evaluation is the CKKS cryptosystem [6], which was proposed aiming specifically at the homomorphic evaluation of neural network algorithms, a major use case for FHE. These algorithms require a high throughput of linear arithmetic operations and are capable of correctly operating even with relatively large imprecisions [7]. Considering that, CKKS offers a very efficient homomorphic evaluation of approximate arithmetic in a SIMD-like manner. Its efficiency, however, restricts functionality, as the scheme needs to rely on arithmetic approximations for non-polynomial and nonlinear functions. The cost of evaluating such approximations might grow exponentially withMOSFHET: Optimized Software for FHE over the Torus Antonio Guimarães $ ^{1} $ · Edson Borin $ ^{2} $ · Diego F. Aranha $ ^{3} $ Abstract Homomorphic encryption is one of the most secure solutions for processing sensitive information in untrusted environments. Recent advances have improved the efficiency of homomorphic encryption for evaluating approximate arithmetic and linear and arbitrary functions. The TFHE scheme [Chillotti et al., 2016] is the current state-of-the-art for evaluating arbitrary functions. This work focuses on improving its performance. The paper is divided into two parts. First, we review and implement the main techniques to improve performance or error behavior in TFHE proposed so far. Then, we introduce novel improvements to several of them and new approaches to implement some commonly used procedures. We also show which proposals can be suitably combined to achieve better results. We provide a single library containing all the reviewed techniques as well as our original contributions. Among the techniques we introduce, we highlight a new method for multi-value bootstrapping based on blind rotation unfolding and a faster-than-memory seed expansion, which introduces speedups of up to 2 times to basic arithmetic operations. Keywords Homomorphic encryption · TFHE · Functional bootstrap · Programmable bootstrap · Efficient implementation 1 Introduction The idea of performing computation over encrypted data was a long-chased goal in the cryptography community. The concept was first defined in 1978 by Rivest et al. [1], but for decades proposed solutions only achieved partial homomorphism. In 2009, Gentry [2] presented the first Fully Homomorphic Encryption (FHE) scheme, based on ideal lattices, enabling arbitrary computation through the evaluation of logic gates. Efficiency was a problem from the start, but Gentry's work also established a blueprint later used to build more efficient FHE schemes based on the Learning With Errors (LWE) problem [3] and its variants [4, 5]. Many of these follow-up works presented significant improvements in efficiency-wise, but the literature generally evolved around the needs of specific use cases, leaving behind, in terms of performance, capabilities such as the evaluation of arbitrary functions. Currently, one of the most efficient solutions for homomorphic evaluation is the CKKS cryptosystem [6], which was proposed aiming specifically at the homomorphic evaluation of neural network algorithms, a major use case for FHE. These algorithms require a high throughput of linear arithmetic operations and are capable of correctly operating even with relatively large imprecisions [7]. Considering that, CKKS offers a very efficient homomorphic evaluation of approximate arithmetic in a SIMD-like manner. Its efficiency, however, restricts functionality, as the scheme needs to rely on arithmetic approximations for non-polynomial and nonlinear functions. The cost of evaluating such approximations might grow exponentially with