Paper 2015/274

Low Depth Circuits for Efficient Homomorphic Sorting

Gizem S. Çetin, Yarkın Doröz, Berk Sunar, and Erkay Savaş

Abstract

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(\ell))$, where $N$ is the size of the array to be sorted and $\ell$ 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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. MINOR revision.
Keywords
Homomorphic sortingcircuit depthsomewhat homomorphic encryption.
Contact author(s)
sunar @ wpi edu
History
2015-03-25: received
Short URL
https://ia.cr/2015/274
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/274,
      author = {Gizem S.  Çetin and Yarkın Doröz and Berk Sunar and Erkay Savaş},
      title = {Low Depth Circuits for Efficient Homomorphic Sorting},
      howpublished = {Cryptology ePrint Archive, Paper 2015/274},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/274}},
      url = {https://eprint.iacr.org/2015/274}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.