Zero-knowledge proof that a group element is a quadratic residue?

Question

In a paper it says: "To convince a verifier that a group element is a quadratic residue, the prover executes the following proof with the verifier":

$PK \left\{ (\alpha) : y = \pm g^\alpha \right\}$

Does someone know how such proof is implemented by a signature proof of knowledge? The group is an RSA group $\mathrm{G} = \mathrm{QR}_n$ with $n = p \cdot q$ and two safe primes $p$ and $q$. I have found an implementation as part of a bigger protocol but although the $\pm$ was in the $\mathrm{PK}$ statement, they ignore it in the implementation. Now I am a little bit confused.

Answer 1

First let's develop a zero knowledge interactive proof. The verifier doesn't know $p,q$ as otherwise he could just take the roots. Let $a$ be the putative residue, and have $P$ know a square root $t$. So P will take a random number $r$ and send $r^2$ to V. V will send a bit, either $0$ or $1$. If $0$ P sends $r$ to V. If $1$ P sends $rt$ to V. This is zero-knowledge by a standard simulated transcript argument. It is a proof of knowledge because P must assure that $r^2a$ is a quadratic residue, and it is enforced that he must send a square.