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.
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
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.· Cybersecurity· 0 citations
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.· Proceedings of the 3rd ACM W...· 0 citations
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...
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.