Paper 2020/488

Near-optimal Polynomial for Modulus Reduction Using L2-norm for Approximate Homomorphic Encryption

Yongwoo Lee, Joonwoo Lee, Young-Sik Kim, and Jong-Seon No


Since Cheon et al. introduced an approximate homomorphic encryption scheme for complex numbers called Cheon-Kim-Kim-Song (CKKS) scheme, it has been widely used and applied in real-life situations, such as privacy-preserving machine learning. The polynomial approximation of a modulus reduction is the most difficult part of the bootstrapping for the CKKS scheme. In this paper, we cast the problem of finding an approximate polynomial for a modulus reduction into an L2-norm minimization problem. As a result, we find an approximate polynomial for the modulus reduction without using the sine function, which is the upper bound for the approximation of the modulus reduction. With the proposed method, we can reduce the degree of the polynomial required for an approximate modulus reduction, while also reducing the error compared with the most recent result reported by Han et al. (CT-RSA' 20). Consequently, we can achieve a low-error approximation, such that the maximum error is less than $2^{-40}$ for the size of the message $m/q\approx 2^{-10}$. By using the proposed method, the constraint of $q = O(m^{3/2})$ is relaxed as $O(m)$, and thus the level loss in bootstrapping can be reduced. The solution of the cast problem is determined in an efficient manner without iteration.

Note: This work is submitted to IEEE Transactions on Information Forensics & Security, 20-Apr-2020.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Approximate arithmeticbootstrappingCheon-Kim-Kim-Song (CKKS) schemefully homomorphic encryption (FHE)privacy preserving.
Contact author(s)
yongwool @ ccl snu ac kr
joonwoo3511 @ ccl snu ac kr
iamyskim @ chosun ac kr
jsno @ snu ac kr
2020-04-28: received
Short URL
Creative Commons Attribution


      author = {Yongwoo Lee and Joonwoo Lee and Young-Sik Kim and Jong-Seon No},
      title = {Near-optimal Polynomial for Modulus Reduction Using L2-norm for Approximate Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/488},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.