Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|improve this question
up vote 6 down vote accepted

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.

share|improve this answer
There is an obvious attack if he (the verifier) accepts even if $\: a\equiv 0 \;$. $\;\;\;$ – Ricky Demer Aug 2 '13 at 4:00
@RickyDemer Thanks. The protocol should reject the case that $a \equiv 0 \pmod{x}$. – xagawa Aug 2 '13 at 4:06
Thank you, that was very clear. – healthycola Aug 2 '13 at 4:12

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\;$ .

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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