Paper 2020/834

Minimax Approximation of Sign Function by Composite Polynomial for Homomorphic Comparison

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

Abstract

The comparison function of the two numbers is one of the most commonly used operations in many applications including deep learning and data processing systems. Several studies have been conducted to efficiently evaluate the comparison function in homomorphic encryption schemes which only allow addition and multiplication for the ciphertext. Recently, new comparison methods that approximate sign function using composite polynomial in the homomorphic encryption, called homomorphic comparison operation, were proposed and it was proved that the methods have optimal asymptotic complexity. In this paper, we propose new optimal algorithms that approximate the sign function in the homomorphic encryption by using composite polynomials of the minimax approximate polynomials, which are constructed by the modified Remez algorithm. It is proved that the number of required non-scalar multiplications and depth consumption for the proposed algorithms are less than those for any methods that use a composite polynomial of component polynomials with odd degree terms approximating the sign function, respectively. In addition, an optimal polynomial-time algorithm for the proposed homomorphic comparison operation is proposed by using dynamic programming. As a result of numerical analysis, for the case that we want to minimize the number of non-scalar multiplications, the proposed algorithm reduces the required number of non-scalar multiplications and depth consumption by about 33\% and 35\%, respectively, compared to those for the previous work. In addition, for the case that we want to minimize the depth consumption, the proposed algorithm reduces the required number of non-scalar multiplications and depth consumption by about 10\% and 47\%, respectively, compared to those for the previous work.