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

Welcome to the resource topic for 2019/1234

Efficient Homomorphic Comparison Methods with Optimal Complexity

Authors: Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim


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.

ePrint: https://eprint.iacr.org/2019/1234

Talk: https://www.youtube.com/watch?v=FEmRhFC6z38

Slides: https://iacr.org/submit/files/slides/2020/asiacrypt/ac2020/179/slides.pdf

See all topics related to this paper.

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.

For more information, see the rules for Resource Topics .