Suppose I have a mystery number $m$ modulo $p$ that I wish to find. I know the value of $m+x^2$ where $x$ is randomly chosen modulo $p$ for some large number $N >> \log(p)$.

Is it possible to deduce the value of $m$?

I believe the answer should be yes, 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+Kx$ where, lets say the first bit of $x$ is known modulo $p$ with probability $\epsilon > 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.