**Cryptanalysis of a Protocol for Efficient Sorting on SHE Encrypted Data **

*Shyam Murthy and Srinivas Vivek*

**Abstract: **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.

**Category / Keywords: **cryptographic protocols / Somewhat Homomorphic Encryption and Comparison, Sorting, Polynomial Reconstruction, Low-depth Circuit

**Original Publication**** (with minor differences): **17th IMA International Conference on Cryptography and Coding

**Date: **received 23 Sep 2019, last revised 24 Sep 2019

**Contact author: **shyam sm at iiitb org, srinivas vivek at iiitb ac in

**Available format(s): **PDF | BibTeX Citation

**Version: **20190925:133334 (All versions of this report)

**Short URL: **ia.cr/2019/1087

[ Cryptology ePrint archive ]