TY - GEN
T1 - Numerical Method for Comparison on Homomorphically Encrypted Numbers
AU - Cheon, Jung Hee
AU - Kim, Dongwoo
AU - Kim, Duhyeong
AU - Lee, Hun Hee
AU - Lee, Keewoo
N1 - Publisher Copyright:
© 2019, International Association for Cryptologic Research.
PY - 2019
Y1 - 2019
N2 - 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-wise. However, the bit-wise encryption methods require relatively expensive computations for 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-wise. From the concrete error analyses, we show that our min/max and comparison algorithms have (formula presented) computational complexity to obtain approximate values within an error rate (formula presented), while the previous minimax polynomial approximation method requires the exponential complexity (formula presented), respectively. Our algorithms achieve (quasi-)optimality in terms of asymptotic computational complexity among polynomial approximations for min/max and comparison operations. The comparison algorithm is extended to several applications such as computing the top-k elements and counting numbers over the threshold in encrypted state. Our 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 (formula presented)-bit integers encrypted by HEAAN, up to error (formula presented), takes only 1.14 ms in amortized running time, which is comparable to the result based on bit-wise HEs.
AB - 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-wise. However, the bit-wise encryption methods require relatively expensive computations for 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-wise. From the concrete error analyses, we show that our min/max and comparison algorithms have (formula presented) computational complexity to obtain approximate values within an error rate (formula presented), while the previous minimax polynomial approximation method requires the exponential complexity (formula presented), respectively. Our algorithms achieve (quasi-)optimality in terms of asymptotic computational complexity among polynomial approximations for min/max and comparison operations. The comparison algorithm is extended to several applications such as computing the top-k elements and counting numbers over the threshold in encrypted state. Our 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 (formula presented)-bit integers encrypted by HEAAN, up to error (formula presented), takes only 1.14 ms in amortized running time, which is comparable to the result based on bit-wise HEs.
KW - Comparison
KW - Homomorphic Encryption
KW - Iterative method
KW - Min/Max
UR - http://www.scopus.com/inward/record.url?scp=85076956755&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-34621-8_15
DO - 10.1007/978-3-030-34621-8_15
M3 - Conference contribution
AN - SCOPUS:85076956755
SN - 9783030346201
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 415
EP - 445
BT - Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
A2 - Galbraith, Steven D.
A2 - Moriai, Shiho
PB - Springer Science and Business Media Deutschland GmbH
T2 - 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
Y2 - 8 December 2019 through 12 December 2019
ER -