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

Metadata
Available format(s)
PDF
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
2019-10-21: received
See all versions
Short URL
https://ia.cr/2019/1234
License
Creative Commons Attribution
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.