Paper 2021/551

Efficient Sorting of Homomorphic Encrypted Data with $k$-way Sorting Network

Seungwan Hong, Seunghong Kim, Jiheon Choi, Younho Lee, and Jung Hee Cheon


In this study, we propose an efficient sorting method for encrypted data using fully homomorphic encryption (FHE). The proposed method extends the existing 2-way sorting method by applying the $k$-way sorting network for any prime $k$ to reduce the depth in terms of comparison operation from $O(\log_2^2 n)$ to $O(k\log_k^2 n)$, thereby improving performance for $k$ slightly larger than $2$, such as $k=5$. We apply this method to approximate FHE which is widely used due to its efficiency of homomorphic arithmetic operations. In order to build up the $k$-way sorting network, the $k$-sorter, which sorts $k$-numbers with a minimal comparison depth, is used as a building block. The approximate homomorphic comparison, which is the only type of comparison working on approximate FHE, cannot be used for the construction of the $k$-sorter as it is because the result of the comparison is not binary, unlike the comparison in conventional bit-wise FHEs. To overcome this problem, we propose an efficient $k$-sorter construction utilizing the features of approximate homomorphic comparison. Also, we propose an efficient construction of a $k$-way sorting network using cryptographic SIMD operations. To use the proposed method most efficiently, we propose an estimation formula that finds the appropriate $k$ that is expected to reduce the total time cost when the parameters of the approximating comparisons and the performance of the operations provided by the approximate FHE are given. We also show the implementation results of the proposed method, and it shows that sorting $5^6=15625$ data using $5$-way sorting network can be about $23.3\%$ faster than sorting $2^{14}=16384$ data using $2$-way.

Available format(s)
Publication info
Published elsewhere. IEEE Transactions on Information Forensics and Security
Approximate Homomorphic EncryptionSorting NetworkParallel Algorithm
Contact author(s)
swanhong @ snu ac kr
2021-09-16: revised
2021-04-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Seungwan Hong and Seunghong Kim and Jiheon Choi and Younho Lee and Jung Hee Cheon},
      title = {Efficient Sorting of Homomorphic Encrypted Data with $k$-way Sorting Network},
      howpublished = {Cryptology ePrint Archive, Paper 2021/551},
      year = {2021},
      doi = {10.1109/TIFS.2021.3106167},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.