Homomorphic sorting with better scalability

Çetin, Gizem S. and Savaş, Erkay and Sunar, Berk (2021) Homomorphic sorting with better scalability. IEEE Transactions on Parallel and Distributed Systems, 32 (4). pp. 760-771. ISSN 1045-9219 (Print) 1558-2183 (Online)

Full text not available from this repository. (Request a copy)


Homomorphic sorting is an operation that blindly sorts a given set of encrypted numbers without decrypting them (thus, there is no need for the secret key). In this article, we propose a new, efficient, and scalable method for homomorphic sorting of numbers: polynomial rank sort algorithm. To put the new algorithm in a comparative perspective, we provide an extensive survey of classical sorting algorithms and networks that are not directly suitable for homomorphic computation. We also include, in our discussions, two of our previous algorithms specifically designed for homomorphic sorting operation: direct and greedy sort, and explain how they evolve from classical sorting networks. We theoretically show that the new algorithm is superior in terms of multiplicative depth when compared with all other algorithms. When batched implementation is used, the number of comparisons is reduced from $\mathcal {O}(N^2)$O(N2) to $\mathcal {O}(N)$O(N) provided that the number of slots is larger than or equal to the number of elements in the set. Our software implementation results confirm that the new algorithm is several orders of magnitude faster than many methods in the literature. Also, the polynomial sort algorithm scales better than the fastest algorithm in the literature to the best our knowledge although for small sets the execution times are comparable. The proposed algorithm is amenable to parallel implementation as most time consuming operations in the algorithm can naturally be performed concurrently.
Item Type: Article
Uncontrolled Keywords: encrypted computing; fully homomorphic encryption; homomorphic sorting; Private computation
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Erkay Savaş
Date Deposited: 16 Aug 2022 16:36
Last Modified: 16 Aug 2022 16:36
URI: https://research.sabanciuniv.edu/id/eprint/43199

Actions (login required)

View Item
View Item