Paper 2018/283

Homomorphic Rank Sort Using Surrogate Polynomials

Gizem S. Çetin and Berk Sunar


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)$.

Available format(s)
Publication info
Published elsewhere. Latincrypt 2017
Private computationencrypted computingfully homomorphic encryptionhomomorphic sorting
Contact author(s)
gscetin @ wpi edu
2018-03-23: received
Short URL
Creative Commons Attribution


      author = {Gizem S.  Çetin and Berk Sunar},
      title = {Homomorphic Rank Sort Using Surrogate Polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2018/283},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.