TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU

arXiv:2611.12854 · cs.CR · Submitted 2026-11-09 · Read on arXiv

Listen

Radio episode about this paper

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.

Robin Köstler, Antonio Guimaróaes

University of Luxembourg · IMDEA Software Institute, Madrid, Spain

cs.CR

Submitted: 2026-11-09

Updated: 2026-11-09

Code: https://github.com/robinkoestler/tutti

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 90/100

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.

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

Summary

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

Where the paper says it

TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU Robin K¨ostler1 and Antonio Guimar˜aes2 1 University of Luxembourg, Luxembourg 2 IMDEA Software Institute, Madrid, Spain Abstract. 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.

TUTTI builds upon SPRU (CK, TCHES 2027) by incorporating new methods specifically tailored to exploit parallelism and handle an arbitrary number of messages. p. 0
Where the paper says it

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).

The primary advantage demonstrated is its lower latency than TFHE when bootstrapping a single message, achieving 4. p. 0
Where the paper says it

TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU Robin K¨ostler1 and Antonio Guimar˜aes2 1 University of Luxembourg, Luxembourg 2 IMDEA Software Institute, Madrid, Spain Abstract. 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.

6 ms on 32 threads compared to TFHE-rs' 7.3 ms for a 4-bit bootstrapping on the same hardware configuration. p. 0
Where the paper says it

6 ms on 32 threads, whereas TFHE-rs needs 7. 3 ms for a 4-bit bootstrapping on the same machine and thread count.

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. p. 0
Where the paper says it

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.

4 ms on 192 threads, surpassing SHIP's performance on the same machine.

The technical foundation of TUTTI involves several key optimizations applied to SPRU. p. 1

Where the paper says it

Figure 1 summarizes the latency of TUTTI for a varying number of messages and compares it with SHIP [CHKS25], PaCo [CS25] and TFHE-rs [Zam22]. 1 Contributions and technical overview Let us start with a high-level overview of SPRU, as introduced by Coron and K¨ostler [CK27].

These include restricting the sparse secret to a subring, utilizing an auxiliary prime for rescaling products to avoid consuming multiplicative levels, and performing the linear transform only once on incoming ciphertexts at the bottom of the modulus chain. p. 3
Where the paper says it

Second, as in SHIP, the products of the first step are rescaled by the auxiliary prime used for key switching, so they consume no multiplicative level (Section 5. Third, as in SHIP, the linear transform that moves the messages between coefficients and slots (S2C) runs once on the incoming ciphertext, at the bottom of the modulus chain, instead of at the end of the bootstrapping, where it would act on a much larger modulus (Section 4.

A crucial innovation in its parallel version is replacing rotations with accumulators, enabling each slot to refresh its message independently. p. 2
Where the paper says it

The second step then multiplies the accumulators slot by slot, without any rotation, and the third step is unchanged (Figure 2, right). Every slot then serves a different message: with h accumulators, a single run refreshes all N/2 slots, and in between, 2 k accumulators refresh 2k times as many messages as SPRU, always at the same depth log h.

Additional optimizations address memory bandwidth constraints by shortening individual steps and splitting full-slot bootstrapping into smaller operations for machines with limited memory resources. p. 3
Where the paper says it

5 bits of precision (Section 5. Finally, on machines with limited memory bandwidth, the full-slot bootstrapping can be split into several smaller ones that share a single key, almost 8 times smaller in our experiments, at some cost in latency on many cores (Section 4.

The comparative analysis against SHIP and TFHE-rs reveals that multi-threaded latency is no longer a deciding factor between CKKS schemes and lightweight alternatives in practical FHE literature, as TUTTI demonstrates superior scaling across different architectures (e. p. 0

Where the paper says it

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.

g., achieving 2.4 ms on an Apple M5 Pro laptop versus 4. p. 0
Where the paper says it

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.

5 ms for TFHE-rs). p. 0
Where the paper says it

TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU Robin K¨ostler1 and Antonio Guimar˜aes2 1 University of Luxembourg, Luxembourg 2 IMDEA Software Institute, Madrid, Spain Abstract. 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.

The comparison highlights that TUTTI trades total computational work for enhanced parallelism, targeting low latency on many cores, whereas SHIP exhibits speed advantages in specific single-threaded scenarios. p. 4
Where the paper says it

We implement TUTTI and SHIP in the same library, with the same thread control, and compare them on the same machine, with SHIP on its published chains and TUTTI on sets of the same ring degree and levels (Section 6). TUTTI trades total work for parallelism: on a single thread, SHIP is faster on two of the four parameter sets, but from 48 threads on, TUTTI is faster on every set, by up to 3× (155 against 467 ms on HT14), at a precision on par or better.

A refined security analysis is also provided for block-binary secrets, offering a more accurate estimation of combinatorial attack costs by accounting for the exact block structure. p. 3
Where the paper says it

We instead cost each attack on the exact block structure: lattice attacks with the recent ring-aware hybrids of Hou, Jiang and Ogilvie [HJO26], and combinatorial attacks with Odlyzko’s meet-in-the-middle and May’s Meet-LWE, with and without guessing the error [Odl90,May21,HKLS22,BLL+26] (Section 3). This gives, for each ring degree and Hamming weight, the largest base modulus that keeps 128 bits of security, including for the subring secrets of TUTTI.

Detailed comparisons are presented through Tables 6 and 7, contrasting TUTTI with SHIP across various parameter sets and showing how both schemes produce one of the h factors. p. 2
Where the paper says it

All have a similar precision. The full parameter sets are given in Tables 5 and 9.

Latency breakdown figures (Figure 5) illustrate that the AccMul stage dominates on a single thread (76% of the time on LL13), but scales effectively by a factor of 46x on 192 threads, with scaling limitations observed in the S2C stage beyond about 32 threads. p. 2
Where the paper says it

2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 4 ms 16 ms 64 ms 256 ms 1 s 4 s 16 s TUTTI (HT14) PaCo SHIP TUTTI (S13) TUTTI (LL13) TFHE-rs (4 bits) Slots Bootstrapping time 1 thread 32 threads 192 threads Fig. Bootstrapping latency by the number of bootstrapped messages (fixed-point real-number slots).

The paper also provides figures (Figure 6) detailing precision and peak memory usage for TUTTI on HT14 runs with uniform random messages, and Table 8 summarizing Cosets for HT15 against full-slot TUTTI. p. 4
Where the paper says it

TUTTI trades total work for parallelism: on a single thread, SHIP is faster on two of the four parameter sets, but from 48 threads on, TUTTI is faster on every set, by up to 3× (155 against 467 ms on HT14), at a precision on par or better. Unlike SHIP, TUTTI also becomes faster as fewer messages are bootstrapped, down to 4.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Multi-threaded latency for bootstrapping is significantly reduced by TUTTI, which lifts both limitations of SHIP and SPRU to achieve state-of-the-art multi-threaded latency for any number of messages. This allows AI systems to perform bootstrapping faster on many cores, as seen with 32 threads achieving 4.6 ms for a single message compared to TFHE-rs' 7.3 ms.

  2. Reduced memory bandwidth dependency is achieved by TUTTI's coset variant, which divides the key traffic of AccMul by ht, helping where memory bandwidth limits AccMul, and shrinking the key's memory footprint by ht as well. This makes bootstrapping viable on machines with limited memory bandwidth, such as those with 36 GiB keys for HT15.

  3. Improved precision is maintained across different architectures, as TUTTI achieves a precision of 6.53 bits for single-slot sets (S13 and S13m2) on Apple M5 Pro laptops at 4.68 ms, matching the precision of SPRU's construction while offering better multi-threaded performance than SHIP.

  4. Enhanced security analysis is performed by costing attacks on exact block structures rather than extrapolating from dense secrets, leading to tighter parameter choices where a single message can be bootstrapped at N = 213 instead of N = 215. This allows AI models to utilize smaller ring degrees for the same security level, potentially reducing computational requirements.

  5. The system supports more complex circuit evaluation by utilizing a Hadamard product in TUTTI, which multiplies across the t groups of blocks, enabling it to fill all N/2 slots in one run and supporting larger numbers of message coefficients efficiently through the general construction for n = t · nmax coefficients.

Abstract

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.

Related papers