International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Numerical Method for Comparison on Homomorphically Encrypted Numbers

Authors:
Jung Hee Cheon
Dongwoo Kim
Duhyeong Kim
Hun Hee Lee
Keewoo Lee
Download:
DOI: 10.1007/978-3-030-34621-8_15
Search ePrint
Search Google
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-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 Θ(α) and Θ(αlog⁡α) computational complexity to obtain approximate values within an error rate 2−α, while the previous minimax polynomial approximation method requires the exponential complexity Θ(2α/2) and Θ(α⋅2α/2), 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 ℓ-bit integers encrypted by HEAAN, up to error 2ℓ−10, takes only 1.14 ms in amortized running time, which is comparable to the result based on bit-wise HEs.
BibTeX
@article{asiacrypt-2019-30046,
  title={Numerical Method for Comparison on Homomorphically Encrypted Numbers},
  booktitle={Advances in Cryptology – ASIACRYPT 2019},
  series={Advances in Cryptology – ASIACRYPT 2019},
  publisher={Springer},
  volume={11922},
  pages={415-445},
  doi={10.1007/978-3-030-34621-8_15},
  author={Jung Hee Cheon and Dongwoo Kim and Duhyeong Kim and Hun Hee Lee and Keewoo Lee},
  year=2019
}