International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Batch Bootstrapping I: A New Framework for SIMD Bootstrapping in Polynomial Modulus

Authors:
Feng-Hao Liu , Florida Atlantic University
Han Wang , Chinese Academy of Science
Download:
DOI: 10.1007/978-3-031-30620-4_11 (login may be required)
Search ePrint
Search Google
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
}