Welcome to the resource topic for 2022/1679
Title:
Integer Polynomial Recovery from Outputs and its Application to Cryptanalysis of a Protocol for Secure Sorting
Authors: Srinivas Vivek, Shyam Murthy, Deepak Kumaraswamy
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.
ePrint: https://eprint.iacr.org/2022/1679
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .