Paper 2025/651 Original: eprint.iacr.org/2025/651 ↗
Low-Latency Bootstrapping for CKKS using Roots of Unity
Abstract
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 5× reduction in latency when applied to ciphertexts with a small number of slots.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2025-05-27: last updated
- 2025-04-09: published
- Short URL
- https://ia.cr/2025/651
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2025/651,
author = {Jean-Sébastien Coron and Robin Köstler},
title = {Low-Latency Bootstrapping for CKKS using Roots of Unity},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/651},
year = {2025},
url = {https://eprint.iacr.org/2025/651}
}