Paper 2025/066

Efficient Homomorphic Integer Computer from CKKS

Abstract

As Fully Homomorphic Encryption (FHE) enables computation over encrypted data, it is a natural question of how efficiently it handles standard integer computations like $64$-bit arithmetic. It has long been believed that the CGGI/DM family or the BGV/BFV family are the best options, depending on the size of the parallelism. The discrete variant of CKKS, suggested by Drucker et al. [J.Cryptol.'24], provides an interesting alternative for integer computations. Notably, the modular reduction framework proposed by Kim and Noh [CiC'25] built on top of the CKKS-style functional bootstrapping by Bae et al. [Asiacrypt'24] gives an efficient arithmetic modulo small integers. In this work, we propose a novel homomorphic computer for unsigned integer computations. We represent a large integer (e.g. $64$-bit) as a vector of smaller chunks (e.g. $4$-bit) and construct arithmetic operations relying on discrete CKKS. The proposed scheme supports many of the operations supported in TFHE-rs while outperforming it in terms of amortized running time. Notably, our homomorphic $64$-bit multiplication takes $8.85$ms per slot, which is more than three orders of magnitude faster than TFHE-rs.