Analysis of Modified Shell Sort for Fully Homomorphic Encryption
The Shell sort algorithm is one of the most practically effective in-place 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 p...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9530524/ |
| _version_ | 1811274193969348608 |
|---|---|
| author | Joon-Woo Lee Young-Sik Kim Jong-Seon No |
| author_facet | Joon-Woo Lee Young-Sik Kim Jong-Seon No |
| author_sort | Joon-Woo Lee |
| collection | DOAJ |
| description | The Shell sort algorithm is one of the most practically effective in-place 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 the FHE data, we modify the Shell sort with an additional parameter <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>, allowing exponentially small sorting failure probability. For a gap sequence of powers of two, the modified Shell sort with input array length <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is found to have the trade-off between the running time complexity of <inline-formula> <tex-math notation="LaTeX">$O(n^{3/2}\sqrt {\alpha +\log \log n})$ </tex-math></inline-formula> and the sorting failure probability of <inline-formula> <tex-math notation="LaTeX">$2^{-\alpha }$ </tex-math></inline-formula>. Its running time complexity is close to the intended running time complexity of <inline-formula> <tex-math notation="LaTeX">$O(n^{3/2})$ </tex-math></inline-formula> and the sorting failure probability can be made very low with slightly increased running time. Further, the near-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. For the practical aspect, our modification can be applied to any gap sequence, and we show that Ciura’s gap sequence, which is known to have good practical performance, is also practically effective when our modified Shell sort is applied. We compare our modified Shell sort with other sorting algorithms with the FHE over the torus (TFHE) library, and it is shown that this modified Shell sort has the best performance in running time among in-place sorting algorithms on homomorphic encryption scheme. |
| first_indexed | 2024-04-12T23:14:33Z |
| format | Article |
| id | doaj.art-06654493f6514d3b875bd616f329f97c |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-12T23:14:33Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-06654493f6514d3b875bd616f329f97c2022-12-22T03:12:43ZengIEEEIEEE Access2169-35362021-01-01912619812621510.1109/ACCESS.2021.31108689530524Analysis of Modified Shell Sort for Fully Homomorphic EncryptionJoon-Woo Lee0https://orcid.org/0000-0002-4125-6331Young-Sik Kim1https://orcid.org/0000-0003-4114-4935Jong-Seon No2https://orcid.org/0000-0002-3946-0958Department of Electrical and Computer Engineering, INMC, Seoul National University, Seoul, Republic of KoreaDepartment of Information and Communication Engineering, Chosun University, Gwangju, Republic of KoreaDepartment of Electrical and Computer Engineering, INMC, Seoul National University, Seoul, Republic of KoreaThe Shell sort algorithm is one of the most practically effective in-place 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 the FHE data, we modify the Shell sort with an additional parameter <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>, allowing exponentially small sorting failure probability. For a gap sequence of powers of two, the modified Shell sort with input array length <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is found to have the trade-off between the running time complexity of <inline-formula> <tex-math notation="LaTeX">$O(n^{3/2}\sqrt {\alpha +\log \log n})$ </tex-math></inline-formula> and the sorting failure probability of <inline-formula> <tex-math notation="LaTeX">$2^{-\alpha }$ </tex-math></inline-formula>. Its running time complexity is close to the intended running time complexity of <inline-formula> <tex-math notation="LaTeX">$O(n^{3/2})$ </tex-math></inline-formula> and the sorting failure probability can be made very low with slightly increased running time. Further, the near-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. For the practical aspect, our modification can be applied to any gap sequence, and we show that Ciura’s gap sequence, which is known to have good practical performance, is also practically effective when our modified Shell sort is applied. We compare our modified Shell sort with other sorting algorithms with the FHE over the torus (TFHE) library, and it is shown that this modified Shell sort has the best performance in running time among in-place sorting algorithms on homomorphic encryption scheme.https://ieeexplore.ieee.org/document/9530524/Fully homomorphic encryption (FHE)fully homomorphic encryption over the torus (TFHE)insertion sortShell sortsorting failure probability |
| spellingShingle | Joon-Woo Lee Young-Sik Kim Jong-Seon No Analysis of Modified Shell Sort for Fully Homomorphic Encryption IEEE Access Fully homomorphic encryption (FHE) fully homomorphic encryption over the torus (TFHE) insertion sort Shell sort sorting failure probability |
| title | Analysis of Modified Shell Sort for Fully Homomorphic Encryption |
| title_full | Analysis of Modified Shell Sort for Fully Homomorphic Encryption |
| title_fullStr | Analysis of Modified Shell Sort for Fully Homomorphic Encryption |
| title_full_unstemmed | Analysis of Modified Shell Sort for Fully Homomorphic Encryption |
| title_short | Analysis of Modified Shell Sort for Fully Homomorphic Encryption |
| title_sort | analysis of modified shell sort for fully homomorphic encryption |
| topic | Fully homomorphic encryption (FHE) fully homomorphic encryption over the torus (TFHE) insertion sort Shell sort sorting failure probability |
| url | https://ieeexplore.ieee.org/document/9530524/ |
| work_keys_str_mv | AT joonwoolee analysisofmodifiedshellsortforfullyhomomorphicencryption AT youngsikkim analysisofmodifiedshellsortforfullyhomomorphicencryption AT jongseonno analysisofmodifiedshellsortforfullyhomomorphicencryption |