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.

  • $\begingroup$ What is a "signature proof of knowledge"? $\:$ $\endgroup$
    – user991
    Commented Mar 8, 2013 at 21:05
  • $\begingroup$ 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. $\endgroup$
    – user4811
    Commented Mar 8, 2013 at 21:20

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


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.