International Association
for Cryptologic Research

In this series of work, we aim at improving the bootstrapping paradigm for fully homomorphic encryption (FHE). Our main goal is to show that the amortized cost of bootstrapping within a polynomial modulus only requires $\tilde O(1)$ FHE multiplications. To achieve this, we develop substantial algebraic techniques in two papers. Particularly, the first one (this work) proposes a new mathematical framework for batch homomorphic computation that is compatible with the existing bootstrapping methods of AP14/FHEW/TFHE. To show that our overall method requires only a polynomial modulus, we develop a critical algebraic analysis over noise growth, which might be of independent interest. Overall, the framework yields an amortized complexity $\tilde O(\sep^{0.75})$ FHE multiplications, where $\sep$ is the security parameter. This improves the prior methods of AP14/FHEW/TFHE, which required $O(\sep)$ FHE multiplications in amortization. Developing many substantial new techniques based on the foundation of this work, the sequel (\emph{Bootstrapping II}, in Eurocrypt 2023) shows how to further improve the recursive bootstrapping method of MS18 (Micciancio and Sorrell, ICALP 2018), whose amortized efficiency is $O(3^{1/\epsilon} \cdot \sep^{\epsilon})$ FHE multiplications for any arbitrary constant $\epsilon >0$. The dependency on $\epsilon$ posts an inherent tradeoff between theory and practice -- theoretically, smaller $\epsilon$'s are better under the asymptotic measure, but the constant $3^{1/\epsilon}$ would become prohibitively large as $\epsilon$ approaches $0$. Our new methods can break the tradeoff and achieve $\tilde O(1)$ amortized complexity. This is a substantial theoretical improvement and can potentially lead to more practical methods.

This work continues the exploration of the batch framework proposed in \emph{Batch Bootstrapping I} (Liu and Wang, Eurocrypt 2023). By further designing novel batch homomorphic algorithms based on the batch framework, this work shows how to bootstrap $\sep$ LWE input ciphertexts within a polynomial modulus, using $\tilde O(\sep)$ FHE multiplications. This implies an amortized complexity $\tilde O(1)$ FHE multiplications per input ciphertext, significantly improving our first work (whose amortized complexity is $\tilde O(\sep^{0.75})$) and another theoretical state of the art MS18 (Micciancio and Sorrell, ICALP 2018), whose amortized complexity is $O(3^{1/\epsilon} \cdot \sep^{\epsilon})$, for any arbitrary constant $\epsilon$. We believe that all our new homomorphic algorithms might be useful in general applications, and thus can be of independent interests.

This work constructs an identity based encryption from the ring learning with errors assumption (RLWE), with shorter master public keys and tighter security analysis. To achieve this, we develop three new methods: (1) a new homomorphic equality test method using nice algebraic structures of the rings, (2) a new family of hash functions with natural homomorphic evaluation algorithms, and (3) a new insight for tighter reduction analyses. These methods can be used to improve other important cryptographic tasks, and thus are of general interests. Particularly, our homomorphic equality test method can derive a new method for packing/unpacking GSW-style encodings, showing a new non-trivial advantage of RLWE over the plain LWE. Moreover, our new insight for tighter analyses can improve the analyses of all the currently known partition-based IBE designs, achieving the best of the both from prior analytical frameworks of Waters (Eurocrypt ’05) and Bellare and Ristenpart (Eurocrypt ’09).