Paper 2019/1497

Analysis of Modified Shell Sort for Fully Homomorphic Encryption

Joon-Woo Lee, Young-Sik Kim, and Jong-Seon No

Abstract

The Shell sort algorithm is one of the most practically effective sorting algorithms. However, it is difficult to execute this algorithm with its intended running time complexity on data encrypted using fully homomorphic encryption (FHE), because the insertion sort in Shell sort has to be performed by considering the worst-case input data. In this paper, in order for the sorting algorithm to be used on FHE data, we modify the Shell sort with an additional parameter $\alpha$ and a gap sequence of powers of two. The modified Shell sort is found to have the trade-off between the running time complexity of $O(n^{3/2}\sqrt{\alpha+\log\log n})$ and the sorting failure probability of $2^{-\alpha}$. Its running time complexity is close to the intended running time complexity of $O(n^{3/2})$ and the sorting failure probability can be made very low with slightly increased running time. Further, the optimal window length of the modified Shell sort is also derived via convex optimization. The proposed analysis of the modified Shell sort is numerically confirmed by using randomly generated arrays. Further, the performance of the modified Shell sort is numerically compared with the case of Ciura's optimal gap sequence and the case of the optimal window length obtained through the convex optimization.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. Minor revision.
Keywords
Fully Homomorphic EncryptionSorting Algorithm
Contact author(s)
joonwoo3511 @ ccl snu ac kr
History
2019-12-30: received
Short URL
https://ia.cr/2019/1497
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1497,
      author = {Joon-Woo Lee and Young-Sik Kim and Jong-Seon No},
      title = {Analysis of Modified Shell Sort for Fully Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1497},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1497}},
      url = {https://eprint.iacr.org/2019/1497}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.