CS Paper Radar

TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU

Robin Köstler, Antonio Guimarães

cs.CR ·submitted 2026-11-09 18:45 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Tulva: Practical Asynchronous Threshold FHE

cs.CR ·2026-10-14 ·Valerio Cini, Antonio Guimarães, Russell W. F. Lai, Michał Osadnik, Ivy K. Y. Woo
top venuebenchmarkcode/data similarity 0.66
Abstract · Full version of the paper accepted at the IEEE Symposium on Security and Privacy (S&P) 2027. 63 pages

We present Tulva, a practical threshold FHE scheme which equips a base FHE scheme with an asynchronous threshold decryption mechanism in a modular way. Our scheme simultaneously (1) is compatible with virtually any base FHE scheme and leaves its ciphertexts unchanged apart from an appended random tag, (2) supports a wide range of threshold profiles $(t,K)$ and ring degrees $\geq 256$ with 6-25 bits partial decryption per plaintext bit, and (3) achieves security in the presence of partial decryption queries on challenge ciphertexts based on the standard LWE assumption. We provide an open-source implementation, benchmark its threshold decryption performance and evaluate the end-to-end costs for typical privacy-preserving Ethereum Virtual Machine (EVM) use cases. For 16-out-of-512 threshold and a publicly preprocessed ciphertext, computing secret-dependent partial decryption and public share combination requires only 3.7 ms and 0.5 ms, respectively, on commodity hardware. Compared with the state-of-the-art synchronous scheme [Zyskind et al., CCS'25], we replace their ciphertext-independent yet interactive preparation of secret-correlated randomness with a public, ciphertext-dependent 0.5 s preprocessing step, eliminate interaction in the online phase while maintaining similar decryption time on the same machine, and support 32$\times$ more total users.

0.47

Static Bootstrap Placement for Encrypted Language Model Decoding

cs.CR cs.DCcs.LG ·2026-10-04 ·Halil Ibrahim Kanpak, Didem Unat
similarity 0.59
Abstract · 20 pages, 10 figures, 8 tables

Language models increasingly serve prompts that carry private data, and secure inference under homomorphic encryption lets a client outsource the computation without revealing the prompt. Existing secure inference systems run a forward pass without consuming a token under encryption, and generating text with them requires a client round trip at every generated token. Keeping the loop on the server instead requires selecting and consuming a token under encryption, and placing bootstraps for a loop body that grows with the context. We build AR-HE, which runs the whole loop on the server, selects each token under encryption, retrieves its embedding, and writes it back into the encrypted state. The client sends one prompt and remains offline until the output. One rule places every bootstrap in the run, without search, so the bootstrap cost of a token is a formula in the context length that is known before the run starts. The schedule skips work whose result cannot reach the output, packs bootstraps that share an operand, and keeps the keys and values of past positions in an encrypted cache. With every optimization applied, generating a GPT-2 small token costs 544 seconds on one NVIDIA H100, down from 4715 seconds without optimization. The prompt step before it costs 4630 seconds. The cache alone takes a generated step from 11751 bootstraps to 1072. The formula predicts every step we measured, including steps of a model it was not derived from.

0.43

PEEK: Heterogeneous Parallelism for Privileged Error Detection in Safety-Critical Processors

cs.AR ·2026-10-02 ·Tinglue Wang, Zhenghui Guo, Bing Guo, Jiapeng Guan, Renshuang Jiang +5 more
top venue similarity 0.59
Abstract · This paper has been accepted for publication at MICRO 2026. This arXiv submission is the pre-camera-ready version; the final camera-ready ve…

Heterogeneous parallel error detection architecture has been widely studied for safeguarding OoO superscalar processors in safetycritical systems, as it achieves significantly lower hardware overhead compared to traditional LockStep, by exploiting the parallelism that exists in a secondary execution. However, previous works do not cover the protection of privileged-mode execution, impeding their effectiveness in real-world deployment. Moreover, naive extension to privileged-mode can cause a litany of issues, from abysmal performance due to high synchronization costs, to full deadlocks. Here, we present PEEK, the first privileged parallel error detection architecture. Based on a deep analysis of privileged execution, we redesign the verification pipeline, addressing all the bottlenecks and bugs identified in privileged-mode protection. Evaluated using various metrics on an RTL-level full system running Linux, PEEK achieves full-privilege protection on Linux with negligible performance slowdown and affordable hardware overhead. PEEK has been taped out using a 28nm process, and its source is available at https://anonymous.4open.science/r/PEEK-3000.

0.49

StateSync-GKR: Design and Evaluation of a Reusable Sparse GKR Engine

cs.CR cs.PF ·2026-10-10 ·Jinwook Kim
code/data similarity 0.58
Abstract · 167 pages; 12 main figures and a detailed experimental atlas appendix. v2 evaluates release 1.2.0 (new serving path; reorganized prover arit…

Authenticated state transitions need proof engines that conserve memory, avoid repeated setup, keep every result bound to its request under parallel execution and return complete proofs at service rates. We present StateSync-GKR, a reusable Rust sumcheck/GKR core with a sparse-Merkle frontend, and evaluate release 1.2.0 against release 1.1 measured on the same day on the same instance types, request corpus and latency budgets. Sparse layer reduction keeps additional requested allocation 3,242-fold and peak process memory about 89-fold below the engine's dense reference at width 4,096. Release 1.2 changes two parts of the software while proof bytes and verifier acceptance stay fixed: reorganized round arithmetic raises prepared proving throughput 2.4 to 2.7-fold on a 192-core bare-metal host, and a new serving path starts each job as soon as a worker is free, bounds queued work and buffered replies, and returns proofs in completion order bound to request identifiers. On a 192-core VM at 1,000 requests/s, 99th-percentile latency to verified acceptance falls from 440 to 34 ms. One connection carries 3,300 requests/s with every request inside one second, confirmed in three 60-second runs and a 30-minute run of 5.94 million requests without a latency or queue trend; at 3,400 requests/s reply traffic reaches the provider's documented 5-Gbit/s single-flow limit, and two connections passed 5,000 requests/s in 15-second screens. In single 15-second screens on 48 cores, the highest passing rate rose from 500 to 2,000/s. Offered 1.5 times its highest screened one-connection rate under a memory limit, with excess offers held back by the client, the worker held its resident memory near a fifth of that limit and left no submitted request unresolved. For an integrating service, fewer servers deliver the same proof rate with bounded tail latency, and existing verifiers accept the GKR proofs unchanged.

0.57

Asynchronous Verifiable and Complete Secret Sharing: From Design Patterns to System-Level Trade-offs

cs.CR ·2026-10-27 ·Joachim Bruneau-Queyreix, Martin Zivojinovic, Leo Mendiboure, Tom Claudel, Laurent Réveillère
similarity 0.58
Abstract

Modern secret sharing protocols promise robust secret sharing in fully asynchronous Byzantine systems, but their practical costs remain difficult to compare across papers, assumptions, and workloads. The difficulty is not merely experimental: protocols with similar asymptotic guarantees often place very different work on the critical path through their choices of dissemination, verification, batching, and recovery. This paper turns that fragmented research landscape into a corpus-backed designspace analysis and systems evaluation of asynchronous verifiable and complete secret sharing. We derive a design sieve, select seven representative protocols, and implement them in a common Rust framework. In our experiments on the Grid'5000 platform, we evaluate honest-dealer and faulty-dealer stress executions using latency, throughput, message count, bandwidth, and aggregate CPU-time. The results show that message complexity alone poorly predicts latency, that optimistic paths can be dominated by recovery cost, and that batching or packing helps only when verification stays off the critical path. These findings turn protocol-by-protocol comparisons into design-to-cost guidance for choosing, implementing, and extending asynchronous verifiable and complete sharing protocols.

0.28

Big Secrets Small Shares: Revisiting Secure Multi-Party Computation

cs.CR cs.IT ·2026-10-20 ·Wilton Kim, Van Long Phuoc Pham, Stanislav Kruglik, Han Mao Kiah
similarity 0.57
Abstract

At CRYPTO 2007, Damgård and Nielsen introduced a preprocessing approach to multi-party computation (MPC) to achieve linear communication complexity. Another approach to reduce communication complexity was proposed by Cramer, Damgård, and de Haan at EUROCRYPT 2007, which involved using ramp-secret sharing schemes to jointly share base-field components of secrets from the extension field. In this paper, we combine these two ideas to achieve a non-asymptotic reduction of communication cost in a multi-phase MPC setup. We introduce a new modification of the ramp secret sharing scheme, called compact sharing, and tailor the MPC protocol to accommodate this modification. Compact sharing masks the polynomial coefficients that would otherwise leak during degree reduction. The protocol provides perfect security against static semi-honest adversaries under an explicit tradeoff between the corruption threshold and the extension degree. When the extension degree scales linearly with the number of parties, the gate-evaluation core achieves constant communication overhead relative to an extension-field element, amortized over full preprocessing batches; input and output communication is counted separately.

0.22

Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS

cs.CR ·2026-11-12 ·Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Dario Fiore, Antonio Guimarães +1 more
publishedhot direction similarity 0.57
Abstract · Full version of a paper accepted at ASIACRYPT 2026. 92 pages

An important challenge in homomorphic encryption (HE) is ensuring the integrity of the encrypted computations. Although verifiable computation can address this in theory, making it practical is far from trivial. [Cascudo et al. CRYPTO 2025] recently proposed a solution to this problem for the CKKS scheme. In particular, they propose new succinct arguments that efficiently prove arithmetic circuits and range checks over the ring $R_q = \mathbb{Z}_q[Y]/(Y^N+1)$, and combine them to prove computations on CKKS ciphertexts. Despite the important progress, their work faces scalability challenges: the size of the polynomial commitment proofs, a large $O(N)$ overhead in range proofs, and the lack of an explicit method for efficient -- sublinear in circuit size -- verification. In this paper we present new techniques that remove all these bottlenecks. First, we provide a more efficient arithmetization of CKKS computations. Second, we introduce BatchFold, a new polynomial commitment for $R_q$ that supports batched evaluations and achieves shorter proofs. Third, we design packing, a novel algebraic technique that eliminates the need to commit to massive polynomials and removes the $O(N)$ overhead in range proofs. Finally, we introduce SparsePack, an efficient protocol for proving the evaluations of sparse, circuit-dependent polynomials, leveraging both packing and batched evaluations. We evaluate the efficiency of our solution on a generic neural network architecture, achieving proofs several orders of magnitude smaller and faster than prior approaches.

0.70

A Combined Streaming FPGA Architecture for Client-Side CKKS Encoding and Encryption

cs.CR cs.AR ·2026-10-19 ·Joseph Kurina, Bogdan Pasca, Suleyman Demirsoy, Sunwoong Kim
published similarity 0.57
Abstract · Accepted to the International Conference on Field Programmable Technology (FPT) 2026

Homomorphic encryption allows a computing service to process encrypted data, but the client must first encode and encrypt its inputs. Sharing hardware between floating-point encoding and modular encryption reduces area but requires those transform roles to execute at different times. We present a streaming FPGA architecture for CKKS encoding and encryption that computes the shared floating-point encoding transform once and performs the integer transforms for six residue moduli in parallel. Dedicated transform pipelines exchange intermediate results on chip rather than through off-chip memory. DSP Builder generates the transform RTL, and Altera HLS IP Gen compiler compiles the surrounding SYCL pipeline into IP integrated with DMA and control logic in an accelerator functional unit. At polynomial degree N = 8192, the Altera Agilex 7 implementation delivers 5,143 complete ciphertexts per second at 471 MHz. One SEAL-Embedded CPU worker on the same workstation delivers 113 ciphertexts per second for real-valued inputs using all 4,096 slots. Measurements cover prepared-input computation through complete ciphertext construction, including FPGA submission and output delivery.

0.24