Welcome to the resource topic for
**2020/488**

**Title:**

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

**Authors:**
Yongwoo Lee, Joonwoo Lee, Young-Sik Kim, Jong-Seon No

**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.

**ePrint:**
https://eprint.iacr.org/2020/488

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .