Tutti cuts fully homomorphic encryption bootstrapping latency on CPUs
TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU
Cryptography and Security
Summary
Fully homomorphic encryption lets computers work on encrypted data, but it slows down after some calculations. Bootstrapping resets this slowdown, but it’s usually slow itself. The authors present TUTTI, a new method that speeds up this reset step significantly on CPUs, even beating previous faster systems. This improvement works especially well when handling many data points and scales efficiently across different computer hardware.
What this means in practice
- •For cloud service providers: Implement ultra-fast encrypted data processing to speed up secure multi-party computations on cloud CPUs.
- •For privacy-focused app developers: Build apps that perform real-time encrypted calculations on users’ devices with reduced delay using TUTTI bootstrapping.$Commercial implications: This paper enables products that deliver faster privacy-preserving computations on consumer devices, improving user experience in secure apps.
Authors
Robin Köstler, Antonio Guimarães
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.