Paper 2022/1679

Integer Polynomial Recovery from Outputs and its Application to Cryptanalysis of a Protocol for Secure Sorting

Abstract

{We investigate the problem of recovering integer inputs (up to an affine scaling) when given only the integer monotonic polynomial outputs. Given $n$ integer outputs of a degree-$d$ integer monotonic polynomial whose coefficients and inputs are integers within known bounds and $n \gg d$, we give an algorithm to recover the polynomial and the integer inputs (up to an affine scaling). A heuristic expected time complexity analysis of our method shows that it is exponential in the size of the degree of the polynomial but polynomial in the size of the polynomial coefficients. We conduct experiments with real-world data as well as randomly chosen parameters and demonstrate the effectiveness of our algorithm over a wide range of parameters. Using only the polynomial evaluations at specific integer points, the apparent hardness of recovering the input data served as the basis of security of a recent protocol proposed by Kesarwani et al. for secure $k$-nearest neighbour computation on encrypted data that involved secure sorting. The protocol uses the outputs of randomly chosen monotonic integer polynomial to hide its inputs except to only reveal the ordering of input data. Using our integer polynomial recovery algorithm, we show that we can recover the polynomial and the inputs within a few seconds, thereby demonstrating an attack on the protocol of Kesarwani et al.

Note: The final published version of this paper appears in the Journal of Mathematical Cryptology, Volume 16 Issue 1, with DOI : 10.1515/jmc-2021-0054. An earlier version of this work was titled "Cryptanalysis of a Protocol for Efficient Sorting on SHE Encrypted Data", and appeared in the Proceedings of 17th IMACC, 2019. The current work subsumes the earlier work and provides new results.