Depth optimized efficient homomorphic sorting

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

doi:10.1007/978-3-319-22174-8_4

Depth optimized efficient homomorphic sorting

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

35 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 language	English (US)
Title of host publication	Progress in Cryptology – LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Proceedings
Editors	Francisco Rodríguez-Henríquez, Kristin Lauter
Publisher	Springer Verlag
Pages	61-80
Number of pages	20
ISBN (Print)	9783319221731
DOIs	https://doi.org/10.1007/978-3-319-22174-8_4
State	Published - 2015
Externally published	Yes
Event	4th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2015 - Guadalajara, Mexico Duration: Aug 23 2015 → Aug 26 2015

Publication series

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

Other

Other	4th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2015
Country/Territory	Mexico
City	Guadalajara
Period	8/23/15 → 8/26/15

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Keywords

Circuit depth
Homomorphic sorting
Somewhat homomorphic encryption

Access to Document

10.1007/978-3-319-22174-8_4

Cite this

Çetin, G. S., Doröz, Y., Sunar, B., & Savaş, E. (2015). Depth optimized efficient homomorphic sorting. In F. Rodríguez-Henríquez, & K. Lauter (Eds.), Progress in Cryptology – LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Proceedings (pp. 61-80). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9230). Springer Verlag. https://doi.org/10.1007/978-3-319-22174-8_4

Çetin, Gizem S. ; Doröz, Yarkın ; Sunar, Berk et al. / Depth optimized efficient homomorphic sorting. Progress in Cryptology – LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Proceedings. editor / Francisco Rodríguez-Henríquez ; Kristin Lauter. Springer Verlag, 2015. pp. 61-80 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9afd4e6c2b894c98a471e14c782bf322,

title = "Depth optimized efficient homomorphic sorting",

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.",

keywords = "Circuit depth, Homomorphic sorting, Somewhat homomorphic encryption",

author = "{\c C}etin, {Gizem S.} and Yarkın Dor{\"o}z and Berk Sunar and Erkay Sava{\c s}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 4th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2015 ; Conference date: 23-08-2015 Through 26-08-2015",

year = "2015",

doi = "10.1007/978-3-319-22174-8_4",

language = "English (US)",

isbn = "9783319221731",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "61--80",

editor = "Francisco Rodr{\'i}guez-Henr{\'i}quez and Kristin Lauter",

booktitle = "Progress in Cryptology – LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Proceedings",

address = "Germany",

}

Çetin, GS, Doröz, Y, Sunar, B & Savaş, E 2015, Depth optimized efficient homomorphic sorting. in F Rodríguez-Henríquez & K Lauter (eds), Progress in Cryptology – LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9230, Springer Verlag, pp. 61-80, 4th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2015, Guadalajara, Mexico, 8/23/15. https://doi.org/10.1007/978-3-319-22174-8_4

Depth optimized efficient homomorphic sorting. / Çetin, Gizem S.; Doröz, Yarkın; Sunar, Berk et al.
Progress in Cryptology – LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Proceedings. ed. / Francisco Rodríguez-Henríquez; Kristin Lauter. Springer Verlag, 2015. p. 61-80 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9230).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Depth optimized efficient homomorphic sorting

AU - Çetin, Gizem S.

AU - Doröz, Yarkın

AU - Sunar, Berk

AU - Savaş, Erkay

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Circuit depth

KW - Homomorphic sorting

KW - Somewhat homomorphic encryption

UR - http://www.scopus.com/inward/record.url?scp=84944686248&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84944686248&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-22174-8_4

DO - 10.1007/978-3-319-22174-8_4

M3 - Conference contribution

AN - SCOPUS:84944686248

SN - 9783319221731

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 61

EP - 80

BT - Progress in Cryptology – LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Proceedings

A2 - Rodríguez-Henríquez, Francisco

A2 - Lauter, Kristin

PB - Springer Verlag

T2 - 4th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2015

Y2 - 23 August 2015 through 26 August 2015

ER -

Çetin GS, Doröz Y, Sunar B, Savaş E. Depth optimized efficient homomorphic sorting. In Rodríguez-Henríquez F, Lauter K, editors, Progress in Cryptology – LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Proceedings. Springer Verlag. 2015. p. 61-80. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-22174-8_4

Depth optimized efficient homomorphic sorting

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this