Cryptology ePrint Archive: Report 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)$.

Category / Keywords: applications / Private computation, encrypted computing, fully homomorphic encryption, homomorphic sorting

Original Publication (in the same form): Latincrypt 2017

Date: received 21 Mar 2018, last revised 22 Mar 2018

Contact author: gscetin at wpi edu

Available format(s): PDF | BibTeX Citation

Version: 20180323:084811 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]