Depth optimized efficient homomorphic sorting

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations

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

Original languageEnglish (US)
Title of host publicationProgress in Cryptology – LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Proceedings
EditorsFrancisco Rodríguez-Henríquez, Kristin Lauter
PublisherSpringer Verlag
Pages61-80
Number of pages20
ISBN (Print)9783319221731
DOIs
StatePublished - 2015
Event4th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2015 - Guadalajara, Mexico
Duration: Aug 23 2015Aug 26 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9230
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2015
Country/TerritoryMexico
CityGuadalajara
Period8/23/158/26/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Circuit depth
  • Homomorphic sorting
  • Somewhat homomorphic encryption

Fingerprint

Dive into the research topics of 'Depth optimized efficient homomorphic sorting'. Together they form a unique fingerprint.

Cite this