Paper 2026/1840

Arithmetic-to-Boolean Conversion in ALU with O(1) Bootstrapping via Overflow Cancellation

Abstract

Arithmetic logic unit (ALU) can combine word-level arithmetic with bit-level logic on encrypted machine words. Triangle encoding provides a CKKS-based representation for leveled word arithmetic, but its existing arithmetic-to-Boolean (A2B) conversion recovers only one window per bootstrapping. Consequently, converting an \(\ell\)-bit message requires \(\Theta(\ell)\) sequential functional-bootstrapping on the critical path of each input ciphertext. We first extend triangle encoding from binary to general digit bases, allowing a larger base to shorten each Triangle word and increase the number of packed words per ciphertext. We then introduce shared-overflow cancellation. For overflow bound \(\lVert I\rVert_\infty<B/2\) and window radix \(D=d^\omega\geq B\), a period-\(D\) functional bootstrap evaluates the remainders at all selected positions simultaneously, while the corresponding quotients are recovered by affine arithmetic. At consecutive selected positions, the current remainder and the preceding quotient contain the same shifted overflow coefficient. Their difference cancels this coefficient exactly and yields \( v_i=D_i+c_{i-1}-Dc_i, \) which contains only the window value \(D_i\) and its adjacent carry bits. All such values are available before any carry is resolved. A second multi-value functional bootstrap jointly obtains the carry behavior and the bits of the value reduced modulo \(D\). The corresponding transfer rules compose associatively, thus parallel carry propagation resolves all carries with \(O(\lceil\log_2 \ell \rceil)\) leveled multiplication depth. After carry propagation, a leveled controlled decrement corrects the extracted bits. The optimized A2B conversion therefore has two sequential functional-bootstrap stages per input ciphertext, independent of \(\ell\), and requires no cross-ciphertext batching. We implement the proposed A2B conversion in OpenFHE for 64-, 128-, and 256-bit words. The full benchmark of the optimized version is not yet complete. Preliminary measurements indicate that the two-bootstrap path is approximately \(1.3\times\) faster than our measured three-bootstrap implementation. Applying this factor to the existing same-machine results gives estimated latency speedups of \(3.32\times\)--\(8.12\times\) and estimated amortized speedups of \(5.20\times\)--\(11.32\times\) over Gao--Zheng. These estimates will be replaced by complete measurements.