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
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
-
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}, url = {https://eprint.iacr.org/2019/1234} }