### Numerical Method for Comparison on Homomorphically Encrypted Numbers

Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Hun Hee Lee, and Keewoo Lee

##### Abstract

We propose a new method to compare numbers which are encrypted by Homomorphic Encryption (HE). Previously, comparison and min/max functions were evaluated using Boolean functions where input numbers are encrypted bit-wisely. However, the bit-wise encryption methods require relatively expensive computation of basic arithmetic operations such as addition and multiplication. In this paper, we introduce iterative algorithms that approximately compute the min/max and comparison operations of several numbers which are encrypted word-wisely. From the concrete error analyses, we show that our min/max and comparison algorithms have $\Theta(\alpha)$ and $\Theta(\alpha\log\alpha)$ computational complexity to obtain approximate values within an error rate $2^{-\alpha}$, while the previous minimax polynomial approximation method requires the exponential complexity $\Theta(2^{\alpha/2})$ and $\Theta(\sqrt{\alpha}\cdot 2^{\alpha/2})$, respectively. We also show the (sub-)optimality of our min/max and comparison algorithms in terms of asymptotic computational complexity among polynomial evaluations to obtain approximate min/max and comparison results. Our comparison algorithm is extended to several applications such as computing the top-$k$ elements and counting numbers over the threshold in encrypted state. Our new method enables word-wise HEs to enjoy comparable performance in practice with bit-wise HEs for comparison operations while showing much better performance on polynomial operations. Computing an approximate maximum value of any two $\ell$-bit integers encrypted by HEAAN, up to error $2^{\ell-10}$, takes only $1.14$ milliseconds in amortized running time, which is comparable to the result based on bit-wise HEs.

Available format(s)
Category
Applications
Publication info
A minor revision of an IACR publication in ASIACRYPT 2019
Keywords
Homomorphic EncryptionComparisonMinMaxIterative Method
Contact author(s)
doodoo1204 @ snu ac kr
dwkim606 @ snu ac kr
History
2019-11-11: last of 5 revisions
See all versions
Short URL
https://ia.cr/2019/417

CC BY

BibTeX

@misc{cryptoeprint:2019/417,
author = {Jung Hee Cheon and Dongwoo Kim and Duhyeong Kim and Hun Hee Lee and Keewoo Lee},
title = {Numerical Method for Comparison on Homomorphically Encrypted Numbers},
howpublished = {Cryptology ePrint Archive, Paper 2019/417},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/417}},
url = {https://eprint.iacr.org/2019/417}
}

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