Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces Sparse Roots of Unity (SPRU) bootstrapping, a novel algorithm designed to enhance the CKKS homomorphic encryption scheme by embedding the additive group modulo q into complex roots of unity. By circumventing the traditional polynomial evaluation for modular reduction, SPRU significantly reduces the multiplicative depth required for bootstrapping, allowing for smaller ring dimensions and improved operational efficiency. Experimental results demonstrate that SPRU bootstrapping can achieve up to a 5x reduction in latency for ciphertexts with a limited number of slots when implemented using the OpenFHE C++ library.
SPRU bootstrapping slashes CKKS homomorphic encryption latency by up to 5x, revolutionizing efficiency in approximate arithmetic.
We introduce Sparse Roots of Unity (SPRU) bootstrapping, a new bootstrapping algorithm for the CKKS homomorphic encryption scheme for approximate arithmetic. The original CKKS bootstrapping method relies on homomorphically evaluating a polynomial that approximates modular reduction modulo q. In contrast, SPRU bootstrapping directly embeds the additive group modulo q into the complex roots of unity, which can be evaluated natively in the CKKS scheme. This approach significantly reduces the multiplicative depth required for bootstrapping, enabling the use of a smaller ring dimension and improving efficiency. In practice, using the OpenFHE C++ library, SPRU bootstrapping achieves up to a 5x reduction in latency when applied to ciphertexts with a small number of slots.