Paper 2026/1840

Efficient Homomorphic Arithmetic Logical Units with \texorpdfstring{$O(1)$}{O(1)} Bootstrapping

Abstract

Arithmetic logic units (ALU) combine word-level arithmetic with bitwise operations over encrypted data. The state-of-the-art scheme, GZ26 (CRYPTO'26), constructs an ALU in CKKS via triangle encoding, but has two limitations: the radix-$2$ design restricts packing capacity, while the arithmetic-to-Boolean (A2B) conversion requires $O(\ell)$ functional bootstrappings for $\ell$-bit message without batching independent ciphertexts. In this paper, we first generalize triangle encoding to arbitrary integer bases while preserving leveled modular arithmetic in CKKS. Larger bases reduce the number of slots required per message, allowing more messages to be packed into each ciphertext. %To ensure correct decoding despite rounding during CKKS plaintext encoding, we derive sufficient conditions relating the digit base to the encoding scale. For power-of-two digit bases, we introduce an A2B conversion using two functional bootstrapping after overflow refreshing, without batching independent ciphertexts. Our key insight is to transform triangle encoding into radix representation with unknown carries, from which candidate bits can be extracted using a single multi-value functional bootstrapping. Specifically, we first cancel the overflow shared by neighboring windows using one functional bootstrapping followed by linear operations, leaving expressions involving only radix digits and adjacent binary carries. Then we use a multi-value functional bootstrapping to jointly extract candidate bits and evaluate the local carry state, which determines how carries propagate between windows. Finally, we recover the canonical bits through parallel carry propagation and bit correction, using only leveled homomorphic operations. We implement our scheme in OpenFHE and evaluate it for 64-bit, 128-bit, and 256-bit message. The experimental results show that using \(d=2\) achieves the lowest latency for A2B conversion, yielding \(3.49\times\)--\(9.71\times\) speedups over GZ26 at the same packing capacity. In addition, using \(d=32\) increases the packing capacity and achieves the best amortized performance, yielding \(8.15\times\)--\(28.47\times\) speedups.