Improved Ciphertext Multiplication for RNS-CKKS Homomorphic Encryption

Homomorphic encryption (HE) enables direct computations on encrypted data and plays a crucial role in ensuring the privacy of cloud computing. The CKKS algorithm is among the most popular HE schemes, wherein a ciphertext comprises a pair of long polynomials with very large coefficients. The residue number system (RNS) effectively mitigates the complexity associated with large coefficient modular multiplications. Nonetheless, the subsequent relinearization and rescaling processes for the ciphertext multiplication actually exhibit higher complexities due to the modulus switching. This paper proposes two innovative methods to reformulate the relinearization and rescaling using RNS representation for the CKKS HE. The first reformulation substantially reduces the number of layers of multiplications and accordingly the latency. The second method further combines scalar multiplications through approximations that only generate negligible noise overhead. As a result, the complexity of ciphertext multiplication is substantially reduced. For an example case, the first proposed design reduces the latency by 27.3% compared to the best previous architecture. The second design reduces the latency and area requirement by 45.4% and 28.3%, respectively.