Paper 2020/834

Minimax Approximation of Sign Function by Composite Polynomial for Homomorphic Comparison

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

Abstract

The comparison operation for two numbers is one of the most commonly used operations in several applications, including deep learning. Several studies have been conducted to efficiently evaluate the comparison operation in homomorphic encryption schemes, termed homomorphic comparison operation. Recently, Cheon et al. (Asiacrypt 2020) proposed new comparison methods that approximate the sign function using composite polynomial in homomorphic encryption and proved that these methods have optimal asymptotic complexity. In this paper, we propose a practically optimal method that approximates the sign function by using compositions of minimax approximate polynomials. It is proved that this approximation method is optimal with respect to depth consumption and the number of non-scalar multiplications. In addition, a polynomial-time algorithm that determines the optimal compositions of minimax approximate polynomials for the proposed homomorphic comparison operation is proposed by using dynamic programming. The numerical analysis demonstrates that the proposed homomorphic comparison operation reduces running time by approximately 45\% (resp. 41\%) on average, compared with the previous algorithm if running time (resp. depth consumption) is to be minimized. In addition, when $N$ is $2^{17}$, and the precision parameter $\alpha$ is 20, the previous algorithm does not achieve 128-bit security, while the proposed algorithm achieves 128-bit security due to small depth consumption.