Paper 2022/515

MOSFHET: Optimized Software for FHE over the Torus

Antonio Guimarães, Edson Borin, and Diego F. Aranha

Abstract

Homomorphic encryption is one of the most secure solutions for processing sensitive information in untrusted environments, and there have been many recent advances towards its efficient implementation for the evaluation of linear functions and approximated arithmetic. However, the practical performance when evaluating arbitrary (nonlinear) functions is still a major challenge for HE schemes. The TFHE scheme [Chillotti et al., 2016] is the current state-of-the-art for the evaluation of arbitrary functions, and, in this work, we focus on improving its performance. We divide this paper into two parts. First, we review and implement the main techniques to improve performance or error behavior in TFHE proposed so far. For many, this is the first practical implementation. 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. Our implementation is up to 1.2 times faster than previous ones with a similar optimization level, and our novel techniques provide speedups of up to 2.83 times on algorithms such as the Full-Domain Functional Bootstrap (FDFB).

Note: A previous version of this paper reports execution times for Concrete based on a version built using the default run command for Cargo (cargo run), which, unknowingly to us at the time of the experiments, produces an unoptimized version of the library. Upon further reading Concrete's documentation, we noticed it requires specific flags for the optimized build. We now update the paper to report execution times for the optimized version of Concrete, built using the command 'RUSTFLAGS="-C target-cpu=native" cargo run --release'.