💻 computer science

Low-Latency Bootstrapping for CKKS using Roots of Unity

This paper introduces Sparse Roots of Unity (SPRU), a novel bootstrapping algorithm for the CKKS homomorphic encryption scheme that embeds modular arithmetic into complex roots of unity to significantly reduce multiplicative depth and achieve up to a 5x latency improvement compared to traditional methods.

Original authors: Jean-Sebastien Coron, Robin Koestler

Published 2026-07-31

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Jean-Sebastien Coron, Robin Koestler

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message to a friend, but you can't trust the post office. You lock your letter in a box, but the post office needs to sort it, stack it, and maybe even open it to check the address without ever seeing what's inside. This is the magic of Fully Homomorphic Encryption (FHE). It allows computers to perform calculations on data that is still locked in its encrypted form. Think of it like a magical kitchen where you can bake a cake using ingredients that are still in their sealed, unopened packages; the oven does the work, and when you finally open the box at the end, you have a fresh cake, but the oven never knew what the ingredients were.

However, there's a catch. Every time the computer does a math operation on this locked data, a tiny bit of "noise" or static gets added to the box, like dust settling on a lens. If you do too many calculations, the noise gets so loud that the message becomes garbled and unreadable. To fix this, scientists use a process called bootstrapping. It's like a magical reset button: the computer takes the noisy, locked box, performs a complex trick to clean out the dust, and puts the message back into a fresh, clean box so the calculations can continue. The problem is, this cleaning trick is incredibly slow and heavy, like trying to wash a car with a toothbrush. It takes so much computing power that it slows everything down, making real-world applications feel sluggish.

This is where a new paper by Jean-Sébastien Coron and Robin Köstler steps in. They introduce a clever new way to perform this "cleaning" process, called Sparse Roots of Unity (SPRU) bootstrapping. Instead of using the old, heavy-handed method that tries to approximate a complex curve (like a sine wave) to clean the data, they found a way to map the data directly onto a circle of numbers called "roots of unity." Imagine instead of scrubbing the car with a toothbrush, you just slide the car onto a giant, spinning carousel that naturally wipes the dust off as it turns. Their method is much faster and lighter, especially when you are dealing with a small number of data items at once. By using this new approach, they showed that the time it takes to reset the encryption can be cut by up to 5 times compared to the standard method, making the magic of secret computing feel much more like a reality than a distant dream.

The Old Way: The Heavy Lifter

To understand why this new trick is so special, let's look at how the old method worked. In the standard CKKS encryption scheme (the most popular one for doing math on decimals), the bootstrapping process was like trying to guess the shape of a mountain by drawing a smooth line over it. The computer had to evaluate a complicated polynomial (a fancy math formula) that approximated a "modular reduction." Think of modular reduction as a way to wrap a long number line into a circle so it fits back into a small box. The old method tried to draw a sine wave (a wavy line) to mimic this wrapping process.

While this worked, it was a heavy lift. It required a deep stack of mathematical operations, which meant the computer had to use a very large "ring dimension" (a measure of the size of the mathematical playground). This was like trying to run a marathon while carrying a heavy backpack; it slowed everything down and limited how much useful work could be done after the reset. The authors point out that this high "multiplicative depth" (the number of layers of math you have to go through) was the main bottleneck, making the process too slow for practical use, especially when you only needed to process a few numbers at a time.

The New Way: The Carousel of Roots

The authors' new idea, SPRU bootstrapping, changes the game by skipping the heavy approximation entirely. Instead of trying to draw a wavy line to mimic the wrapping, they realized they could simply embed the data directly onto the "roots of unity."

Here is a simple analogy: Imagine the old method was like trying to translate a secret code by writing a long, complicated dictionary entry for every single letter. It took forever. The new method is like realizing that the secret code is actually just a set of keys that fit perfectly into a specific lock. Instead of translating, you just turn the key.

In technical terms, they map the additive group (the way numbers add up) directly into the complex roots of unity (points on a circle in the complex number system). Because the CKKS encryption scheme natively understands these complex numbers, the computer can perform the "cleaning" operation directly, without needing to approximate a sine wave. It's like switching from building a bridge out of individual bricks to using a pre-fabricated arch that fits perfectly.

The Secret Sauce: Sparsity and Packing

The paper doesn't just stop at the new map; they also introduced two clever optimizations to make it even faster, especially when dealing with a small number of data slots (like a few numbers in a list).

Packing the Bits: In the old days, if you had a secret key with 1,000 bits, the computer had to handle each bit one by one. The authors realized they could "pack" these bits into the slots of the encryption, like stuffing 1,000 letters into a single, super-efficient mailbox. This reduced the number of heavy calculations needed from a massive amount to just a logarithmic amount (think of it as cutting a long list down to a short summary).
The Sparse Block Trick: They also assumed the secret key had a special structure: instead of random bits, the key was divided into blocks where only one bit in each block was a "1" and the rest were "0". This is like having a row of light switches where only one is on in every group of ten. By using this "sparse" structure, they could replace many difficult multiplication steps with simple addition steps. It's the difference from multiplying a long list of numbers to just adding a few of them. This reduced the "depth" of the calculation even further, from a deep tower to a small staircase.

The Results: Speeding Up the Magic

The authors tested their new method using the OpenFHE library, a popular tool for building encryption software. They compared their SPRU bootstrapping against the original, heavy-handed method.

The results were striking for specific scenarios. When bootstrapping ciphertexts with a small number of slots (which is common in many real-world applications), their new method was up to 5 times faster (a 5x reduction in latency). This is a huge deal because it means the "reset button" doesn't have to wait so long, allowing the computer to get back to doing useful work much quicker.

However, the paper is careful to note that this isn't a magic bullet for every situation. If you are trying to process a massive number of slots (a huge list of data), the original method might still be more efficient. But for the many cases where we are dealing with smaller batches of data, this new approach offers a significant speedup.

Why It Matters

The beauty of this work is that it doesn't just tweak the numbers; it fundamentally changes how we think about the bootstrapping process. By moving away from the heavy polynomial approximations and embracing the native capabilities of the encryption scheme, the authors have shown that we can make fully homomorphic encryption much more practical.

They proved that by using these "roots of unity" and smart packing techniques, we can significantly reduce the time and computing power needed to keep encrypted data usable. While the paper focuses on the technical details and the math behind the scenes, the takeaway is clear: the dream of doing complex calculations on secret data without slowing down is getting a little closer to reality. The authors have provided a new, lighter, and faster way to keep the magic alive, making it possible to imagine a future where your private data can be processed in the cloud without ever being seen, and without waiting forever for the result.

Technical Summary: Low-Latency Bootstrapping for CKKS using Roots of Unity

Problem Statement

The CKKS homomorphic encryption scheme supports approximate arithmetic on encrypted complex numbers, making it suitable for secure machine learning and cloud computing. However, a critical bottleneck in CKKS is the bootstrapping procedure, which is required to refresh ciphertexts and enable unlimited computation depth.

The original CKKS bootstrapping method [CHK+18a] relies on homomorphically evaluating a polynomial approximation of the modular reduction function (specifically, a scaled sine function). This approach suffers from two main drawbacks:

High Multiplicative Depth: The polynomial approximation requires a deep circuit, necessitating a large ciphertext modulus.
Inefficiency for Small Slot Counts: The complexity of the original method scales with the number of slots ( $n$ ) and the ring dimension ( $N$ ), often requiring $O(\log n + \log N)$ operations. This high depth forces the use of larger ring dimensions to maintain security, leading to increased latency.

The authors identify a need for a bootstrapping algorithm that reduces multiplicative depth, thereby allowing for smaller ring dimensions and significantly lower latency, particularly for ciphertexts with a small number of slots.

Methodology: Sparse Roots of Unity (SPRU)

The paper introduces Sparse Roots of Unity (SPRU) bootstrapping, a novel algorithm that fundamentally changes how modular reduction is performed in CKKS.

Core Concept: Native Embedding

Instead of approximating modular reduction via a sine function, SPRU bootstrapping directly embeds the additive group $\mathbb{Z}_q$ into the multiplicative group of complex roots of unity. The authors utilize the homomorphism:
$f: \mathbb{Z}_q \to \mathbb{C}, \quad x \mapsto \exp(2i\pi \cdot x/q)$

For an LWE-style decryption equation $m = \langle s, c \rangle \pmod q$ , the authors observe that:
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} \exp(2i\pi \cdot c_k s_k / q)$
Since the secret key bits $s_k \in \{0, 1\}$ act as selectors, this product can be rewritten as:
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} (1 + (\exp(2i\pi \cdot c_k/q) - 1) \cdot s_k)$
By isolating the imaginary part and applying a linear scaling factor, the original message $m$ can be recovered. This equation can be evaluated homomorphically within the CKKS scheme without polynomial approximation of the sine function.

Key Optimizations

To make this approach practical, the authors introduce two critical optimizations:

Packing Secret-Key Bits:
Instead of encrypting each secret key bit individually, the $N$ bits are packed into the $N/2$ slots of two CKKS ciphertexts. The terms $(\exp(2i\pi \cdot c_k/q) - 1)$ are similarly packed. The product of these terms is computed using the Product Operator ( $Pr_{N/2 \to 1}$ ), which reduces the number of homomorphic multiplications from $O(N)$ to $O(\log N)$ .
Sparse Block Secret Key:
The authors assume a structured secret key $s$ divided into $h$ blocks of size $B = N/h$ , where each block contains exactly one non-zero bit (a '1'). This structure allows the product within each block to be replaced by a sum.
- The sum within blocks is computed using the Trace Operator ( $Tr_{N/2 \to h}$ ), which involves only additions and automorphisms (no multiplicative depth).
- The final product is taken over the $h$ block results.
- Result: The multiplicative depth is reduced from $\log_2 N + 2$ to $\log_2 h + 1$ . Since $h \ll N$ , this significantly lowers the required modulus size.

Extension to Multiple Slots

The method is generalized to handle $n$ slots (where $n \le N/2$ ). The decryption matrix is extracted, and the bootstrapping equation is applied in parallel to each of the $n$ message components. The complexity is $O(n + \log N)$ , which is asymptotically higher than the original CKKS bootstrapping ( $O(\log n + \log N)$ ) for large $n$ . However, for small $n$ , the reduced multiplicative depth yields superior practical performance.

Key Contributions

SPRU Bootstrapping Algorithm: A new bootstrapping technique for CKKS that replaces sine-function approximation with native evaluation of roots of unity.
Reduced Multiplicative Depth: By leveraging sparse block secret keys and the trace operator, the algorithm achieves a multiplicative depth of $O(\log h)$ , significantly lower than the $O(\log N)$ of the original method.
Optimized Implementation: The authors provide an open-source implementation using the OpenFHE C++ library, demonstrating compatibility with Residue Number System (RNS) arithmetic and existing linear transformation optimizations (SlotToCoeff).
Security Analysis: A formal analysis of the block binary secret key distribution, showing that it does not weaken the security of the RLWE problem against known attacks (hybrid dual and meet-in-the-middle attacks), provided parameters are adjusted correctly.

Results

The authors benchmarked SPRU bootstrapping against the original CKKS bootstrapping using the OpenFHE library with 128-bit security parameters.

Latency Reduction: For ciphertexts with a small number of slots, SPRU bootstrapping achieves up to a 5x reduction in latency.
Efficiency: The reduction in multiplicative depth allows for the use of smaller ring dimensions, further contributing to the speedup.
Parallelism: The method is highly parallelizable; with $n$ processors, it can achieve $O(\log N)$ complexity comparable to the original method.

Significance and Claims

The paper claims that SPRU bootstrapping offers a practical alternative to the original CKKS bootstrapping, specifically targeting scenarios where low latency is critical and the number of slots is small. By avoiding expensive polynomial approximations and reducing the multiplicative depth, the method enables more efficient ciphertext refreshing.

The authors position their work as a significant step toward making fully homomorphic encryption more viable for real-world applications requiring frequent bootstrapping. They note that while their method is optimized for small slot counts, it complements existing work (such as the independent work by Cheon et al. [CHKS25] which focuses on full $N/2$ -slot bootstrapping) by offering a different trade-off favoring latency over massive parallelism for small data sets.

The paper concludes that the reduced multiplicative depth is the primary driver of efficiency, freeing up more computational levels for useful operations after bootstrapping and allowing for smaller, faster ring dimensions.