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

Proof on Quadratic non-residuosity

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?


1 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.

  • $\begingroup$ Why is this not a proof of knowledge? $\endgroup$
    – user93353
    Mar 7, 2023 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.