Paper 2020/488 Original: eprint.iacr.org/2020/488 ↗

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

Abstract

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.