# Is this Zero Knowledge interactive proof for Quadratic non-residuosity proper?

This is from Alan Rosen's video on Interactive proofs - https://youtu.be/6uGimDYZPMw?t=1754

Here the proof is that

• the Verifier gets a random bit $$b$$ .

• If $$b = 0$$, then Verifier gets a random $$y \in Z^*_n$$ & sends $$z = y^2$$ to the Prover.

• if $$b=1$$, then the Verifier sends $$z = xy^2$$ to the Prover.

• Now if $$z$$ is a Quadratic Residue, then the Prover sends back $$0$$, else $$1$$

Now, doesn't this depend on the Prover knowing a way to figuring out if $$z$$ is a QR or not? This goes beyond what is needed - i.e. the Prover should not only know if $$x$$ is a QR or not but he also needs to know if any number is a QR or not.

So how is this a proper proof?

First, this is not supposed to be a proof of knowledge, so any references to "knowledge" are largely irrelevant. The prover is merely required to convince the verifier that $$x$$ is in fact a quadratic non-residue.
Second, the definition of an interactive proof does not restrict the prover to be efficient. It is therefore trivial for the prover to check whether $$z$$ is a quadratic residue, e.g. by exhaustive search.