Skip to content
Open access

Efficient Lookup Tables for Carry Handling in TFHE

Oct 2026 · IACR Communications in Cryptology · 0 citations · 19 references

TL;DR

This work introduces a single-bootstrap message and carry extraction technique that computes both outputs using a single programmable bootstrap, and proposes a three-operand group-state combination method for parallel carry propagation.

Abstract

Fully Homomorphic Encryption (FHE) enables computation on encrypted data while preserving privacy. TFHE is an FHE scheme that efficiently supports arbitrary function evaluation on small encrypted values. Large integers are typically represented across multiple ciphertexts, making carry handling a fundamental component of practical integer arithmetic. Two particularly important operations are message and carry extraction, which separate the message and carry components of a ciphertext, and carry propagation. In this work, we present two optimisations for carry handling in TFHE based on redesigned Lookup Tables for programmable bootstrapping. First, we introduce a single-bootstrap message and carry extraction technique that computes both outputs using a single programmable bootstrap. By modifying the Lookup Table construction, we significantly reduce the error growth compared to a direct MultiLUT-based approach, reducing the required parameter overhead from 48 % to 2 % while achieving a 1.95 × speedup over the extraction method currently used in TFHE-rs. Second, we propose a three-operand group-state combination method for parallel carry propagation. Our approach reduces the sequential depth of the Hillis-Steele prefix-scan from ⌈ log 2 ( g ) ⌉ to ⌈ log 3 ( g ) ⌉ and lowers the total number of required bootstraps, resulting in up to 1.37 × faster carry propagation for large encrypted integers. Both techniques are integrated in the TFHE-rs library and available as patch files.

Read PDF

Similar papers

Efficient Homomorphic Arithmetic Logical Units with O (1) Bootstrapping

This paper first generalizes triangle encoding to arbitrary integer bases while preserving leveled modular arithmetic in CKKS to transform triangle encoding into radix representation with unknown carries, from which candidate bits can be extracted using a single multi-value functional bootstrapping.

Xuan Shen, 3. ZhihaoLi⋆, Rui-Da Wang et al. · 0 citations
Review Open access Sep 2026

A survey on fully homomorphic encryption compilers

This paper systematically reviews existing FHE compilers, examining their techniques and effectiveness to explore the current state of the art and identify areas for future research.

Zhuo-Yu Tian, Sheng-Yu Fan, Xiang-Long Deng et al. · 0 citations
Conference Open access Sep 2026

FPGA Acceleration of Fully Homomorphic Encryption with Adaptive Key Switching

Fully Homomorphic Encryption (FHE) enables privacy-preserving cloud services but incurs substantial computation overhead, making hardware acceleration essential. Among FHE operations, key-switching is a major performance bottleneck. Recent cryptographic advances introduce a novel key-switching method (i.e., KLSS) that...

Zhi-Han Xu, Jayashree Adivarahan, Rajgopal Kannan et al. · 0 citations
Book Open access Nov 2026

Private LLM Inference: Optimizing Tricycle

The adoption of Large Language Models (LLM) in scenarios with sensitive data requires the use of privacy-preserving technologies to guarantee confidentiality. Private LLM inference using Fully-Homomorphic Encryption (FHE) guarantees data privacy by encrypting the input beforehand and performing inference directly over...

Zaira Pindado, Hugo Sanz-González, Thomas Spendlhofer et al. · 0 citations
Preprint Oct 2026

Fully Homomorphic Encryption for Statistical Modeling

Fully homomorphic encryption allows arithmetic to be carried out on encrypted values, so that a party performing a computation need not see the data it operates on. This is useful wherever collaborating parties or sites cannot share data records or computed summaries yet need to do a joint analysis. We demonstrate the...

B. Narasimhan · 0 citations

Coral: General and Efficient Framework for Homomorphic Evaluation of Symmetric Ciphers

This work presents C ORAL, a general and efficient transciphering framework built on TFHE that decomposes an entire decryption circuit to a uniform evaluation strategy and provides optimized procedures for four recurring computational modules: linear Boolean operations, sparse low-degree Boolean functions, modular addi...

Ji-Kang Bai, Rui-Da Wang, Xian-Hui Lu et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.