Paper 2023/1788

Homomorphic Multiple Precision Multiplication for CKKS and Reduced Modulus Consumption

Jung Hee Cheon, CryptoLab Inc., Seoul National University
Wonhee Cho, Seoul National University
Jaehyung Kim, CryptoLab Inc.
Damien Stehlé, CryptoLab Inc.

Homomorphic Encryption (HE) schemes such as BGV, BFV, and CKKS consume some ciphertext modulus for each multiplication. Bootstrapping (BTS) restores the modulus and allows homomorphic computation to continue, but it is time-consuming and requires a significant amount of modulus. For these reasons, decreasing modulus consumption is crucial topic for BGV, BFV and CKKS, on which numerous studies have been conducted. We propose a novel method, called $\mathsf{mult}^2$, to perform ciphertext multiplication in the CKKS scheme with lower modulus consumption. $\mathsf{mult}^2$ relies an a new decomposition of a ciphertext into a pair of ciphertexts that homomorphically performs a weak form of Euclidean division. It multiplies two ciphertexts in decomposed formats with homomorphic double precision multiplication, and its result approximately decrypts to the same value as does the ordinary CKKS multiplication. $\mathsf{mult}^2$ can perform homomorphic multiplication by consuming almost half of the modulus. We extend it to $\mathsf{mult}^t$ for any $t\geq 2$, which relies on the decomposition of a ciphertext into $t$ components. All other CKKS operations can be equally performed on pair/tuple formats, leading to the double-CKKS (resp. tuple-CKKS) scheme enabling homomorphic double (resp. multiple) precision arithmetic. As a result, when the ciphertext modulus and dimension are fixed, the proposed algorithms enable the evaluation of deeper circuits without bootstrapping, or allow to reduce the number of bootstrappings required for the evaluation of the same circuits. Furthermore, they can be used to increase the precision without increasing the parameters. For example, $\mathsf{mult}^2$ enables 8 sequential multiplications with 100 bit scaling factor with a ciphertext modulus of only 680 bits, which is impossible with the ordinary CKKS multiplication algorithm.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. CCS 2023
Fully Homomorphic EncryptionCKKS schemeApproximate multiplicationHigh precisionSmall parameters
Contact author(s)
jhcheon @ snu ac kr
wony0404 @ snu ac kr
jaehyungkim @ cryptolab co kr
damien stehle @ cryptolab co kr
2023-11-24: approved
2023-11-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Wonhee Cho and Jaehyung Kim and Damien Stehlé},
      title = {Homomorphic Multiple Precision Multiplication for {CKKS} and Reduced Modulus Consumption},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1788},
      year = {2023},
      doi = {10.1145/3576915.3623086},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.