Efficient Lookup Tables for Carry Handling in TFHE

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.