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

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.

• What is a "signature proof of knowledge"? $\:$ – user991 Mar 8 '13 at 21:05
• A signature of knowledge means to use the Fiat-Shamir heuristic to make a ZK proof protocol non-interactive. It uses the output of a hash function as the challenge. Security is then also based on the random oracle model. – user4811 Mar 8 '13 at 21:20

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.