Welcome to the resource topic for 2019/417
Title:
Numerical Method for Comparison on Homomorphically Encrypted Numbers
Authors: Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Hun Hee Lee, 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.
ePrint: https://eprint.iacr.org/2019/417
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .