SHIP: A Shallow and Highly Parallelizable CKKS Bootstrapping Algorithm

The CKKS fully homomorphic encryption scheme enables efficient homomorphic operations in terms of throughput, but its bootstrapping algorithm incurs a significant latency. In this work, we introduce SHIP, a novel bootstrapping algorithm for CKKS ciphertexts. SHIP enjoys a very shallow homomorphic multiplicative depth compared to state-of-the-art CKKS bootstrapping algorithms. Bootstrapping depth directly impacts the required Ring-LWE modulus, and hence the Ring- LWE degree. The massive depth saving allows us to report the first bootstrapping of CKKS ciphertexts for full-dimensional cleartext vectors in ring degree N=2^13, without resorting to an expensive scheme switching to DM/CGGI. SHIP also enjoys great parallelizability, with minimal communication between threads. The combined ring size reduction and high parallelizability lead to very low latency. In ring degree N=2^13, our experimental implementation runs in 215ms on a 32-core CPU for real-valued cleartext vectors. This is 2.5x lower than the smallest latency we could observe with the HEaaN library (using 48 cores). For binary cleartext vectors, the latency is lowered to 174ms, which is 2.2x lower than Bae et al [Eurocrypt’24] (with 32 cores).