Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	王晗，中国科学院信息工程研究所
Inviter:	潘彦斌
Title:	A New Framework for SIMD Bootstrapping in Polynomial Modulus
Language:	Chinese
Time & Venue:	2023.04.27 10:00-11:00 思源楼713
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.