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

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

Srinivas Vivek, Shyam Murthy, Deepak Kumaraswamy

{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 …

application cryptanalysis eprint report protocol recovery