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)
PDF
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2018/283}},
      url = {https://eprint.iacr.org/2018/283}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.