TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU

summary

The gist

This paper introduces TUTTI, a novel CKKS bootstrapping procedure designed to achieve superior low-latency performance in multi-threaded environments compared to existing solutions.

In short

TUTTI is a new CKKS bootstrapping procedure designed for fast, low-latency performance in multi-threaded environments. It improves upon existing methods like SPRU by exploiting parallelism to handle many messages efficiently. TUTTI achieves lower latency than TFHE and significantly outperforms SHIP when processing large volumes of real-number messages.

Key concepts

CKKS Bootstrapping
This is a crucial process in Fully Homomorphic Encryption (FHE) that refreshes the noise level in an encrypted computation. It allows computations to continue without the errors accumulating too much, ensuring accurate results even after many operations.
Parallelism Exploitation
TUTTI specifically optimizes its design to take advantage of multiple CPU cores simultaneously. Instead of processing tasks sequentially, it structures the bootstrapping steps so that different parts of the computation can happen at once, drastically reducing overall waiting time.
Multi-threaded Latency
This refers to how quickly a cryptographic operation finishes when using many processor threads. The paper shows TUTTI scales much better than other methods; for example, it achieves 2.4 ms on an Apple M5 Pro laptop, demonstrating superior speed compared to alternatives like TFHE-rs.

Terminology used across episodes

This episode discusses

The paper

TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU · Read on arXiv

Robin Köstler, Antonio Guimaróaes

University of Luxembourg · IMDEA Software Institute, Madrid, Spain

This paper introduces TUTTI, a new CKKS bootstrapping procedure that outperforms previous low-latency solutions in multi-threaded latency for any number of messages and, most notably, has a lower latency than TFHE when bootstrapping a single one. Our bootstrapping builds upon SPRU (CK, TCHES 2027), improving it with new methods for exploiting parallelism and increasing the number of messages, as well as with a refined security analysis, of independent interest, of the block-binary secret keys of LMSS (AsiaCCS 2023). TUTTI bootstraps 4096 real-number messages in 46 to 83.4 ms on 192 threads to restore 1 to 9 multiplicative levels, outperforming SHIP (CHKS, Eurocrypt 2025) by a factor of up to 3 on the same machine. Unlike SHIP, TUTTI gains immediately from bootstrapping fewer messages, with a 256-message bootstrapping taking just 15 to 34 ms on 32 threads. For a single message, TUTTI takes 4.6 ms on 32 threads, whereas TFHE-rs needs 7.3 ms for a 4-bit bootstrapping on the same machine and thread count. We show that this advantage persists across different architectures: on an Apple M5 Pro laptop (ARM), TUTTI takes 2.4 ms on 14 threads, against 4.5 ms for TFHE-rs. Differences between CKKS and lightweight schemes such as TFHE remain on several fronts, from functionality to key sizes and security assumptions, but our work shows that multi-threaded latency is no longer one of them, closing a long-standing gap in the practical FHE literature.

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: We're looking at the paper: "TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU".

Elias: Here's the gist of the paper. This paper introduces TUTTI, a novel CKKS bootstrapping procedure designed to achieve superior low-latency performance in multi-threaded environments compared to existing solutions.

Nadia: TUTTI builds upon SPRU (CK, TCHES 2027) by incorporating new methods specifically tailored to exploit parallelism and handle an arbitrary number of messages.

Elias: The primary advantage demonstrated is its lower latency than TFHE when bootstrapping a single message, achieving 4.6 ms on 32 threads compared to TFHE-rs' 7.3 ms for a 4-bit bootstrapping on the same hardware configuration.

Nadia: Furthermore, TUTTI significantly outperforms SHIP (CHKS, Eurocrypt 2025) by up to a factor of three when bootstrapping a large number of messages; for instance, it bootstraps 4096 real-number messages in 46 to 83.4 ms on 192 threads, surpassing SHIP's performance on the same machine.

Paper summary: Nadia: To summarize this TUTTI paper, the authors introduce a new CKKS bootstrapping procedure that aims to achieve better low-latency performance in multi-threaded settings than existing solutions.

Elias: The core thesis is that their new bootstrapping builds upon SPRU but incorporates novel methods specifically targeting parallelism and the ability to handle an arbitrary number of messages.

Priya: What’s the most compelling claim they make about this new procedure, beyond just being better than old ones?

Nadia: The primary advantage demonstrated is that it achieves lower latency than TFHE when bootstrapping a single message, hitting four point six milliseconds on thirty two threads <ref:2611.12854#pg3>.

Elias: They also show it significantly outperforms SHIP by up to a factor of three when dealing with a large number of messages, specifically bootstrapping four thousand ninety-nine real number messages in forty six to eighty three point four milliseconds across one hundred ninety two threads.

Priya: So, the paper is essentially claiming that this new method offers a significant performance boost for both small and large message sets when running on multiple cores.

Nadia: Exactly, because they also noted that even for a smaller task, like bootstrapping two hundred fifty six messages, it takes just fifteen to thirty four milliseconds on thirty two threads.

Elias: This isn't just about one specific test case; it’s about showing the procedure scales well and maintains performance across different message counts and thread counts.

Priya: I’m still looking at how they handled the complexity of CKKS, which is a fixed-point arithmetic scheme, because that's where most people think bootstrapping would be slow.

Nadia: They address that by restricting the sparse secret to a subring and using an auxiliary prime for rescaling products to avoid consuming multiplicative levels when they do the math.

Elias: Plus, they perform the linear transform only once on incoming ciphertexts at the bottom of the modulus chain, which is a big optimization compared to older methods.

Conclusion: Nadia: So, looking at the TUTTI paper by Robin Köstler and Antonio Guimarães, it really shows how much performance can be gained by rethinking how we parallelize CKKS bootstrapping procedures.

Elias: The implication for us is that multi-threaded latency isn't a barrier anymore when choosing between CKKS and other lightweight alternatives in practical FHE literature.

Priya: In simpler terms, this means that for real applications like private neural network inference, the time spent on bootstrapping might become less of a bottleneck if you use a procedure like TUTTI.

Nadia: It suggests that we should look at how we structure our operations to take advantage of these parallel capabilities rather than just focusing on minimizing the total computational work itself.

Elias: The paper points out that TUTTI trades total computational work for enhanced parallelism, which is a different trade-off than what some other schemes like SHIP emphasize.

Priya: It’s about finding the sweet spot where you get fast enough results without running into massive memory or time constraints on your specific hardware setup.

Nadia: That’s the practical side of it, and they even provided a refined security analysis for block binary secrets to give us a better sense of the costs involved in attacks.

Elias: It gives us more concrete numbers about the complexity of attacking these schemes, which is always valuable when we are designing systems.

More episodes

← Home