Paper 2019/1087

Cryptanalysis of a Protocol for Efficient Sorting on SHE Encrypted Data

Shyam Murthy and Srinivas Vivek


Sorting on encrypted data using Somewhat Homomorphic Encryption (SHE) schemes is currently inefficient in practice when the number of elements to be sorted is very large. Hence alternate protocols that can efficiently perform computation and sorting on encrypted data is of interest. Recently, Kesarwani et al. (EDBT 2018) proposed a protocol for efficient sorting on data encrypted using an SHE scheme in a model where one of the two non-colluding servers is holding the decryption key. The encrypted data to be sorted is transformed homomorphically by the first server using a randomly chosen monotonic polynomial with possibly large coefficients, and then the non-colluding server holding the decryption key decrypts, sorts, and conveys back the sorted order to the first server without learning the actual values except possibly for the order. In this work we demonstrate an attack on the above protocol that allows the non-colluding server holding the decryption key to recover the original plaintext inputs (up to a constant difference). Though our attack runs in time exponential in the size of plaintext inputs and degree of the polynomial but polynomial in the size of coefficients, we show that our attack is feasible for 32-bit inputs, hence accounting for several real world scenarios. Of independent interest is our algorithm for recovering the integer inputs (up to a constant difference) by observing only the integer polynomial outputs.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. 17th IMA International Conference on Cryptography and Coding
SortingPolynomial ReconstructionLow-depth Circuit
Contact author(s)
shyam sm @ iiitb org
srinivas vivek @ iiitb ac in
2019-09-25: received
Short URL
Creative Commons Attribution


      author = {Shyam Murthy and Srinivas Vivek},
      title = {Cryptanalysis of a Protocol for Efficient Sorting on SHE Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1087},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.