TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU
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 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. 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: 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, whereas TFHE-rs needs 7. 3 ms for a 4-bit bootstrapping
on the same machine and thread count. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The technical foundation of TUTTI involves several key optimizations applied to SPRU. p. 1 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]. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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. 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. 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. All have a similar precision. The full parameter sets are given in Tables 5 and 9. 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). 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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
-
Multi-threaded latency for bootstrapping is significantly reduced by TUTTI, which
lifts both limitations
of SHIP and SPRU to achievestate-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. -
Reduced memory bandwidth dependency is achieved by TUTTI's coset variant, which
divides the key traffic of AccMul by ht,
helping wherememory 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. -
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.
-
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. -
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
- From Strategy Search to Policy Learning: MCTS-Guided Adversarial Co-Evolution for LLM Safety Alignment
- Privacy Leakage from Recurrent State in LLM Inference
- Incrementally Verifiable Oracle Aided Computation
- Privilege and confidentiality in generative AI workflows
- BadMoE: Backdooring Mixture-of-Experts LLMs via Routing-Aware Triggers and Task-Underutilized Experts
- CoVault: Secure, Scalable Analytics of Personal Data