Paper 2020/552

Optimal Minimax Polynomial Approximation of Modular Reduction for Bootstrapping of Approximate Homomorphic Encryption

Joon-Woo Lee and Eunsang Lee and Yongwoo Lee and Young-Sik Kim and Jong-Seon No

Abstract

Approximate homomorphic encryption, called Cheon-Kim-Kim-Song (CKKS) scheme, is a fully homomorphic encryption scheme that supports arithmetic operations for real or complex number data encrypted. Since the bootstrapping of the CKKS scheme is a big bottleneck for practical use, this makes many cryptographers optimize its bootstrapping, but they cannot obtain its optimal solution. One of the core procedures in the bootstrapping is to approximate the modular reduction function, and several works have been done for the polynomial approximation of this function in the minimax aspect. In this paper, we obtain a fast algorithm to derive the optimal minimax generalized approximate polynomial of any continuous functions over any union of the finite number of intervals, which uses a variant of the Remez algorithm, called modified Remez algorithm. Using that results, we derive the optimal minimax approximate polynomial for the modular reduction function rather than the sine or cosine function in the CKKS scheme. From the numerical analysis, there is some gap of the approximation error by two in the logarithm scale between the cosine minimax approximation and the proposed direct minimax approximation. There is some inherent flat error region for the cosine minimax approximation such that the minimax approximation error does not decrease as the degree of the approximation polynomial increases, but the approximation error for the proposed one is improved as the degree of approximation polynomial increases. Further, we propose a composite function approximation using inverse sine function to obtain approximation error smaller than the fundamental flat error with a small number of the non-scalar multiplications. For the direct approximation, we reduce the number of non-scalar multiplications by 30% by using odd function property of the minimax approximate polynomial of modular reduction function. From the numerical analysis, it is known that the composite function approximation is desirable when the running time of bootstrapping is important, and the direct approximation with odd function optimization is desirable when the depth is important.