### 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 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.

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
2020-08-18: last of 5 revisions
See all versions
Short URL
https://ia.cr/2019/1234

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.