Paper 2019/1234
Efficient Homomorphic Comparison Methods with Optimal Complexity
Jung Hee Cheon, Dongwoo Kim, and 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 largebit 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 constantdegree 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 $ab\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.
Metadata
 Available format(s)
 Category
 Applications
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2020
 Keywords
 Homomorphic EncryptionComparisonMinMaxComposite polynomial approximation
 Contact author(s)

doodoo1204 @ snu ac kr
dwkim606 @ snu ac kr
jhcheon @ snu ac kr  History
 20200818: last of 5 revisions
 20191021: received
 See all versions
 Short URL
 https://ia.cr/2019/1234
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/1234, author = {Jung Hee Cheon and Dongwoo Kim and Duhyeong Kim}, title = {Efficient Homomorphic Comparison Methods with Optimal Complexity}, howpublished = {Cryptology ePrint Archive, Paper 2019/1234}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/1234}}, url = {https://eprint.iacr.org/2019/1234} }