Accelerating Fully Homomorphic Encryption by Bridging Modular and Bit-Level Arithmetic
Eduardo Chielle, Oleg Mazonka, Homer Gamil, Michail Maniatakos
The dramatic increase of data breaches in modern computing platforms has
emphasized that access control is not sufficient to protect sensitive user
data. Recent advances in cryptography allow end-to-end processing of encrypted
data without the need for decryption using Fully Homomorphic Encryption (FHE).
Such computation however, is still orders of magnitude slower than direct
(unencrypted) computation. Depending on the underlying cryptographic scheme,
FHE schemes can work natively either at bit-level using Boolean circuits, or
over integers using modular arithmetic. Operations on integers are limited to
addition/subtraction and multiplication. On the other hand, bit-level
arithmetic is much more comprehensive allowing more operations, such as
comparison and division. While modular arithmetic can emulate bit-level
computation, there is a significant cost in performance. In this work, we
propose a novel method, dubbed \emph{bridging}, that blends faster and
restricted modular computation with slower and comprehensive bit-level
computation, making them both usable within the same application and with the
same cryptographic scheme instantiation. We introduce and open source C++ types
representing the two distinct arithmetic modes, offering the possibility to
convert from one to the other. Experimental results show that bridging modular
and bit-level arithmetic computation can lead to 1-2 orders of magnitude
performance improvement for tested synthetic benchmarks, as well as two
real-world FHE applications: A URL denylisting case study, and a genotype
imputation application. Bridging performance enhancement comes from two
factors: 1) Reduced number of operations (especially ciphertext
multiplications), and 2) Arithmetic circuits with smaller multiplicative depth,
allowing more efficient encryption parameters with smaller polynomial degrees.