Zero-knowledge proof using quadratic residue: why two options?

Question

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

Answer 1

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.

Answer 2

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