Windowing technique for Lazy Sorting of Encrypted data

In computer science literature, sorting is an age-old theoretically interesting problem with great practical importance. In this paper, we discuss the effect on sorting when the comparisons are erroneous. Such an analysis would be in particular effective for secured cloud data which is Fully Homomorphically Encrypted (FHE) and the sorting is intended to be applied on the encrypted data. Although theoretically feasible, FHE is costly due to the underlying Recrypt operation, removal of which leads to erroneous computations. In this context, we consider a two-stage sorting called Lazysort. In this sort, the first phase is a layer of Bubble sort with reduced Recrypts, thus leading to erroneous comparisons. We provide analysis to show the effect of this error on the eventual window in which the correct location of an element lies. Assuming such a window in which the probability of an element to lie is almost one, we apply a second pass of insertion sort, which has an linear complexity for an almost sorted array. In this paper, we discuss about practical challenges of implementing such encrypted sorting while working with underlying encrypted processor. Finally, we show how our proposed method makes this sorting technique actually feasible and provide practical results to accompany the theoretical claims made to justify the windowed technique for implementing the LazySort algorithm on FHE data.