## CryptoDB

### Hun Hee Lee

#### Publications

Year
Venue
Title
2019
ASIACRYPT
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 $\varTheta (\alpha )$ and $\varTheta (\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 $\varTheta (2^{\alpha /2})$ and $\varTheta (\sqrt{\alpha }\cdot 2^{\alpha /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 $\ell$-bit integers encrypted by HEAAN, up to error $2^{\ell -10}$, takes only 1.14 ms in amortized running time, which is comparable to the result based on bit-wise HEs.

#### Coauthors

Jung Hee Cheon (1)
Dongwoo Kim (1)
Duhyeong Kim (1)
Keewoo Lee (1)