# [Resource Topic] 2019/1234: Efficient Homomorphic Comparison Methods with Optimal Complexity

Welcome to the resource topic for 2019/1234

Title:
Efficient Homomorphic Comparison Methods with Optimal Complexity

Authors: Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim

Abstract:

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 support addition and multiplication. Recently, Cheon et al. (Asiacrypt 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 \emph{core properties} to make a composite polynomial f\circ f \circ \cdots \circ 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\circ \cdots \circ f\circ g \circ \cdots \circ g for some other polynomial g with different properties instead of f\circ f \circ \cdots \circ f. Utilizing the devised polynomials f and g, our new comparison algorithms only require \Theta(\log(1/\epsilon)) + \Theta(\log\alpha) computational complexity to obtain an approximate comparison result of a,b\in[0,1] satisfying |a-b|\ge \epsilon within 2^{-\alpha} error. The asymptotic optimality results in substantial performance enhancement: our comparison algorithm on encrypted 20-bit integers for \alpha = 20 takes 1.43 milliseconds in amortized running time, which is 30 times faster than the previous work.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.