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

Question

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?

Answer 1

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.