Welcome to the resource topic for 2025/784
Title:
SHIP: A Shallow and Highly Parallelizable CKKS Bootstrapping Algorithm
Authors: Jung Hee Cheon, Guillaume Hanrot, Jongmin Kim, Damien Stehlé
Abstract: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).
ePrint: https://eprint.iacr.org/2025/784
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .