Search

The sign function can be adopted to implement the comparison operation, max function, and rectified linear unit (ReLU) function in the Cheon–Kim–Kim–Song (CKKS) scheme; hence, several studies have been conducted to efficiently evaluate the sign function in the CKKS scheme. Recently, Lee et al. (IEEE Trans. Depend. Sec. Comp.) proposed a practically optimal approximation method for the sign function in the CKKS scheme using a composition of minimax approximate polynomials. In addition, Lee et al. proposed a polynomial-time algorithm that finds the degrees of component polynomials that minimize the number of non-scalar multiplications. However, homomorphic comparison/max/ReLU functions using Lee et al.’s approximation method have not been successfully implemented in the residue number system variant CKKS (RNS-CKKS) scheme. In addition, the degrees of component polynomials found by Lee et al.’s algorithm are not optimized for the RNS-CKKS scheme because the algorithm does not consider that the running time of non-scalar multiplication depends significantly on the ciphertext level in the RNS-CKKS scheme. In this study, we propose a fast algorithm for the inverse minimax approximation error, which is a subroutine required to find the optimal set of degrees of component polynomials. The proposed algorithm facilitates determining the optimal set of degrees of component polynomials with higher degrees than in the previous study. In addition, we propose a method to find the degrees of component polynomials optimized for the RNS-CKKS scheme using the proposed algorithm for the inverse minimax approximation error. We successfully implement the homomorphic comparison, max function, and ReLU function algorithms on the RNS-CKKS scheme with a low comparison failure rate ( $< 2^{-15}$ ), and provide various parameter sets according to the precision parameter $\alpha $ . We reduce the depth consumption of the homomorphic comparison, max function, and ReLU function algorithms by one depth for several values of $\alpha $ . In addition, the numerical analysis demonstrates that the homomorphic comparison, max function, and ReLU function algorithms using the degrees of component polynomials found by the proposed algorithm reduce the running time by 6%, 7%, and 6% on average, respectively, compared with those using the degrees of component polynomials found by Lee et al.’s algorithm.

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 article, 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 = \mathcal {O}(m^{3/2})$ is relaxed as $\mathcal {O}(m)$ , and thus the level loss in bootstrapping can be reduced. The solution to the cast problem is determined in an efficient manner without iteration.