Efficient Homomorphic Comparison Methods with Optimal Complexity

摘要

Comparison of two numbers is one of the most frequently used operations, but it has been a challenging task to efficiently compute the comparison function in homomorphic encryption (HE) which basically supports addition and multiplication. Recently, Cheon et al. (Asi-acrypt 2019) introduced a new approximate representation of the comparison function with a rational function, and showed that this rational function can be evaluated by an iterative algorithm. Due to this iterative feature, their method achieves a logarithmic computational complexity compared to previous polynomial approximation methods; however, the computational complexity is still not optimal, and the algorithm is quite slow for large-bit inputs in HE implementation. In this work, we propose new comparison methods with optimal asymptotic complexity based on composite polynomial approximation. The main idea is to systematically design a constant-degree polynomial f by identifying the core properties to make a composite polynomial f o f o … o f get close to the sign function (equivalent to the comparison function) as the number of compositions increases. We additionally introduce an acceleration method applying a mixed polynomial composition f o…o f o g o…o g for some other polynomial g with different properties instead of f o f o…o f. Utilizing the devised polynomials f and g, our new comparison algorithms only require Θ(log(1/ε)) + Θ(log α) computational complexity to obtain an approximate comparison result of a, b ∈ [0,1] satisfying |a-b| ≥ ∈ within 2~(-α) error. The asymptotic optimality results in substantial performance enhancement: our comparison algorithm on 16-bit encrypted integers for α = 16 takes 1.22 ms in amortized running time based on an approximate HE scheme HEAAN, which is 18 times faster than the previous work.