Welcome to the resource topic for 2019/1497
Title:
Analysis of Modified Shell Sort for Fully Homomorphic Encryption
Authors: Joon-Woo Lee, Young-Sik Kim, 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.
ePrint: https://eprint.iacr.org/2019/1497
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .