In the zero knowledge proof using QR, why do we even bother with the server sending us $b = 0$ back? As I understand it, the server selects $b = 0$ or $b = 1$. If $b = 0$, then the client (Alice) generates a random number $r$ and sends back $r^2 \bmod x$, while if $b = 1$, then Alice sends back $r^2 \, y \bmod x$. How is $b = 0$ of any value though? Why can't we just stick with $b = 1$?


2 Answers 2


Let me attack if you (the verifier) always select $b = 1$ as a random challenge.

The zero-knowledge proof for QR.

Let us recall the zero-knowledge proof for QR. The common inputs are $y$ and $x$ and the prover possesses a witness $w$ which satisfies $w^2 \equiv y \pmod{x}$.

  1. The prover generates a randomness $r \gets \mathbb{Z}_x$ and sends $a = r^2 \bmod{x}$.
  2. The verifier rejects if $a \equiv 0 \pmod{x}$; Otherwise, the verifier sends a random challenge $b \gets \{0,1\}$.
  3. The prover sends a response $z = w^b \cdot r \bmod{x}$.
  4. The verifier checks if $z^2 \equiv y^b \cdot a \bmod{x}$.

An attack for a fixed challenge $b$

If you always select $b = 1$, I can deceive you while I do not know $w$.

  1. I choose a random value $\tilde{z} \gets \mathbb{Z}$ and compute $\tilde{a} = \tilde{z}^2 \cdot y^{-1} \bmod{x}$. I send $\tilde{a}$ to you.
  2. You select a "random" value $b = 1$ and send it to me.
  3. I send $\tilde{z}$ as a response.
  4. You finally obtain $\tilde{z}^2 \equiv y \cdot \tilde{a} \bmod{x}$, since I select $\tilde{a}$ to satisfy this equation.

This attack shows that the protocol cannot be sound if the challenge is unique. Hence, the verifier should flip at least one coin.

Why $b \in \{0,1\}$

In the soundness proof, we retrieve a witness as follows: Running the (cheating) prover twice with distinct challenges, we obtain two accepting transcripts $$(a, b_0, z_0) \text{ and } (a, b_1, z_1).$$ Since they pass the verification, we have $z_0^2 \equiv y^{b_0} \cdot a \pmod{x}$ and $ z_1^2 \equiv y^{b_1} \cdot a \pmod{x}$. Therefore, we have $z_0^2 \cdot y^{-b_0} \equiv a \equiv z_1^2 \cdot y^{-b_1} \pmod{x}$ and $(z_1/z_0)^{2} \equiv y^{b_1-b_0} \pmod{x}$. If we select a challenge from $\{0,1\}$, the difference $b_1 - b_0$ is $1$ or $-1$. Hence, we obtain $z_1/z_0$ (or $z_0/z_1$) as a quadratic residue of $y$.

The point is that the difference $b_1 - b_0$ is always $\pm 1$. This means that you can choose $b$ from another set, say, $\{2,3\}$ or $\{3,4\}$.

You can read explanations in the textbooks, e.g., Barak's lecture note.

  • $\begingroup$ There is an obvious attack if he (the verifier) accepts even if $\: a\equiv 0 \;$. $\;\;\;$ $\endgroup$
    – user991
    Aug 2, 2013 at 4:00
  • $\begingroup$ @RickyDemer Thanks. The protocol should reject the case that $a \equiv 0 \pmod{x}$. $\endgroup$
    – xagawa
    Aug 2, 2013 at 4:06

What "zero knowledge proof using QR" are you talking about?

In this one, "we bother with" Bob sending Alice $\:b=0\:$ so that if $\:\: y\not\equiv 0 \;$ and
for both possible values of $b$, there exists a response which would cause Bob to accept
then $x$ is a quadratic residue $\:\pmod n\;$ .


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.