CryptoDB
Batch Bootstrapping II: Bootstrapping in Polynomial Modulus Only Requires $\tilde O(1)$ FHE Multiplications in Amortization
| Authors: |
|
|---|---|
| Download: |
|
| Conference: | EUROCRYPT 2023 |
| Abstract: | 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. |
BibTeX
@inproceedings{eurocrypt-2023-32909,
title={Batch Bootstrapping II: Bootstrapping in Polynomial Modulus Only Requires $\tilde O(1)$ FHE Multiplications in Amortization},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-30620-4_12},
author={Feng-Hao Liu and Han Wang},
year=2023
}