CryptoDB
Batch Bootstrapping I: A New Framework for SIMD Bootstrapping in Polynomial Modulus
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | EUROCRYPT 2023 |
| Abstract: | 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. |
BibTeX
@inproceedings{eurocrypt-2023-32907,
title={Batch Bootstrapping I: A New Framework for SIMD Bootstrapping in Polynomial Modulus},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-30620-4_11},
author={Feng-Hao Liu and Han Wang},
year=2023
}