Depth optimized efficient homomorphic sorting

Çetin, Gizem Selcan and Doröz, Yarkın and Sunar, Berk and Savaş, Erkay (2015) Depth optimized efficient homomorphic sorting. In: 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico

[thumbnail of conf02_main.pdf] PDF

Download (405kB)


We introduce a sorting scheme which is capable of efficiently sorting encrypted data without the secret key. The technique is obtained by focusing on the multiplicative depth of the sorting circuit alongside the more traditional metrics such as number of comparisons and number of iterations. The reduced depth allows much reduced noise growth and thereby makes it possible to select smaller parameter sizes in somewhat homomorphic encryption instantiations resulting in greater efficiency savings. We first consider a number of well known comparison based sorting algorithms as well as some sorting networks, and analyze their circuit implementations with respect to multiplicative depth. In what follows, we introduce a new ranking based sorting scheme and rigorously analyze the multiplicative depth complexity as O(log(N) + log(l)), where N is the size of the array to be sorted and l is the bit size of the array elements. Finally, we simulate our sorting scheme using a leveled/batched instantiation of a SWHE library. Our sorting scheme performs favorably over the analyzed classical sorting algorithms.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: Homomorphic sorting; Circuit depth; Somewhat homomorphic encryption
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Q Science > QA Mathematics > QA076 Computer software
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Erkay Savaş
Date Deposited: 22 Dec 2015 15:14
Last Modified: 26 Apr 2022 09:20

Actions (login required)

View Item
View Item