Quadratic Residue Protocol

A Cut-and-Choose protocol for proving that a number is a square mod $N$. $\mathcal{R}=\{((N,y),w)\mid y\in {\mathbb{Z}}_N^{\ast }\text{ and }{w}^2=y\mathrm{mod}N\}$ The $y\in {\mathbb{Z}}_N^{\ast }$ part is trivial to check efficiently by any verifier itself. The interesting part is $w^2=y$, i.e. that $y$ has a square root. This is an interesting statement because if $N$ is the product of two large random primes, then it’s difficult to decide whether any given $y$ has a square root or not.

Notation

We drop the "$\mathrm{mod}N$" from expressions below, but any computation involving elements from ${\mathbb{Z}}_N$ is understood to be $\mathrm{mod}N$.

This protocol is very similar to Graph Isomorphism Protocol.

The main idea

Following the Cut-and-Choose paradigm, the protocol splits $x=(N,y)$ and square root $w$ into

• $x_0=(N,r^2),w_0=r$
• $x_1=(N,r^2\cdot y),w_1=r\cdot w$ for a random value $r\leftarrow {\mathbb{Z}}_N^{\ast }$.

Intuition

The two parts read as

• $r^2$ is a square (with random square root $r$)
• $r^2\cdot y$ is a square (with random square root $r\cdot w$)

Then we get the two required properties (see Splitting the statement into parts):

• Neither $w_0=r$ nor $w_1=r\cdot w$ on their own reveal anything about $\sigma$ (given that $r$ is a random group element from ${\mathbb{Z}}_N^{\ast }$)
• Together, $w_0=r$ and $w_1=r\cdot w$ reveal $w$.

The protocol

Following the The protocol template:

Protocol between $P(N,y,w)$ and $V(N,y)$

• Announcement: Prover chooses a random $r\leftarrow {\mathbb{Z}}_N^{\ast }$ and sends announcement $a=r^2$.
• Challenge: The verifier chooses a random challenge $c\leftarrow \{0,1\}$ (challenging the prover to reveal the square root of $a\cdot y^c$).
• Response: The prover reveals $z=\{\begin{array}{ll}r& c=0\\ r\cdot w& c=1\end{array}$
• The verifier checks that $y\in {\mathbb{Z}}_N^{\ast }$ and $z^2=a\cdot y^c$.

Optimization of the Cut-and-Choose template

Instead of sending both “split” instances $x_0=(N,r^2)$ and $x_1=(N,r^{2}y)$, we simply send $r^2$, given that the verifier already knows $N,y$. In the verification equation, the verifier adds the "$\cdot y$" itself, if needed.

The ZK property

This follows Typical simulator outline.

The Zero Knowledge (Classical) simulator $S(x)$ for (malicious) verifier $V^{\ast }$ works as follows:

Simulator $S(G_1,G_2)$

1. $S$ computes a random transcript of the protocol:

• $S$ chooses a random challenge $c\leftarrow \{0,1\}$
• $S$ chooses a random response $z\leftarrow {\mathbb{Z}}_N^{\ast }$
• $S$ computes the unique fitting announcement $a=z^2\cdot y^{-c}$

2. $S$ rejects challenges $c$ not consistent with what $V^{\ast }$ would output:

• $S$ chooses randomness $R$ and computes $c^{\prime }=V^{\ast }(G_1,G_2;R;a)$
• If $c^{\prime }=c$, then output the view $(x,R,a,z)$ Otherwise, start from the beginning and try again.

The PoK property

For simplicity, we assume that the prover has probability 1 to convince an honest verifier, which puts us into the A simplified toy definition scenario. The extractor for prover $P^{\ast }$ works as follows:

Extractor $E^{P^{\ast }}(N,y)$

• $E$ retrieves the prover’s announcement $a=P^{\ast }(G_0,G_1;R)$ (for some random $R$)
• $E$ retrieves the prover’s response for both challenges $c\in \{0,1\}$ as $z_c=P^{\ast }(N,y;R;c)$
  • From the verification equations, we get $z_0^2=a$ and $z_1^2=a\cdot y$
• $E$ outputs the witness $w=z_1/z_0$

Formally, the witness is correct because $w^2=z_1^2/z_0^2=ay/a=y$.

Non-simplified scenario

Theorem: the quadratic residue protocol is a Proof of Knowledge (Classical) with knowledge error $\kappa =1/2$.

For a prover that may not answer all challenges correctly always (but convinces the verifier with probability $>1/2$), it may happen that when $E$ gets the two responses in the second step, one or more of them is actually invalid, i.e. fails the verification equation. In that case, the response is useless for the extractor. In that scenario, $E$ will have to restart and try different prover randomness $R$. Using a counting argument, one can show that for some $R$, the prover has to be able to answer both challenges (otherwise it cannot be convincing with probability larger than $1/2$). The extractor then tries different $R$ until it finds one for which both challenges can be answered.