Suppose I have a mystery number $m$ modulo $p$ that I wish to find. I know the value of $m+x_i^2$ where $x_i$ is randomly chosen modulo $p$ for some large number of different $x_i$, $N$ many, $N \gg \log(p)$.
Is it possible to deduce the value of $m$?
If we replace $m+x_i^2$ with $m+C_i*x_i^2$ for known $C_i$, can we find $m$?
I believe the answer should be yes in both cases, there are roughly $p/2$ quadratic residues so each question gives around $1$ bit of information. There are lattice and Fourier based solutions on the linear version of the problem with $m+K_ix_i$ where, lets say the first bit of $x$ is known modulo $p$ with probability $\varepsilon > 0$. (Bleichenbacher’s algorithm).
https://eprint.iacr.org/2013/346.pdf
I was thinking you can use Gauss sums or something to tease out the value of $m$ slowly from $x^2+m$. Something like computing an average of $e(m+x^2)$ where $e(x)$ is the complex exponential and having it converge to $m$. But I don't know enough about Gauss sums.
