Paper 2018/283
Homomorphic Rank Sort Using Surrogate Polynomials
Gizem S. Çetin and Berk Sunar
Abstract
In this paper we propose a rank based algorithm for sorting encrypted data using monomials. Greedy Sort is a sorting technique that achieves to minimize the depth of the homomorphic evaluations. It is a costly algorithm due to excessive ciphertext multiplications and its implementation is cumbersome. Another method Direct Sort has a slightly deeper circuit than Greedy Sort, nevertheless it is simpler to implement and scales better with the size of the input array. Our proposed method minimizes both the circuit depth and the number of ciphertext multiplications. In addition to its performance, its simple design makes it more favorable compared to the alternative methods which are hard to parallelize, e.g. not suitable for fast GPU implementations. Furthermore, we improve the performance of homomorphic sorting algorithm by adapting the SIMD operations alongside message slot rotation techniques. This method allow us to pack $N$ integers into a single ciphertext and compute $N$ comparisons at once, thus reducing $\mathcal{O}(N^2)$ comparisons to $\mathcal{O}(N)$.
Metadata
- Available format(s)
- Category
- Applications
- Publication info
- Published elsewhere. Latincrypt 2017
- Keywords
- Private computationencrypted computingfully homomorphic encryptionhomomorphic sorting
- Contact author(s)
- gscetin @ wpi edu
- History
- 2018-03-23: received
- Short URL
- https://ia.cr/2018/283
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/283, author = {Gizem S. Çetin and Berk Sunar}, title = {Homomorphic Rank Sort Using Surrogate Polynomials}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/283}, year = {2018}, url = {https://eprint.iacr.org/2018/283} }