Introduced by Guillou and Quisquater in 1988, it is a zero-knowledge identification protocol.

The scenario is as follows: we first have a trusted authority, whom we will name Trent. Trent is trusted by everyone: what he says is true. Trent distributes to all interested parties a secret based on their identity, that he only can compute. Then, when Alice wants to identify to Bob, she uses a zero-knowledge protocol to demonstrate that she knows the secret associated to her identity, but without revealing it (so that Bob cannot subsequently impersonate her).

First, Trent chooses a RSA integer $n$ (product of two large, distinct primes $p,q$), and a public RSA exponent $e$ (an integer relatively prime with $\varphi(n) = (p-1)(q-1)$, we can assume that $e$ is a small prime, for example $e=3$ is perfectly fine). He then computes the associated private exponent $d$, and as usual publishes $n$ and $e$, keeping $p,q,d$ secret. We suppose that Alice’s identity (for example her name or her e-mail address) is somehow encoded as an element $I \in \mathbf{Z}_n^*$, then Trent gives her the value $B = I^{-d}$, which is Alice’s secret.

In order to identify to Bob, Alice wants to prove to him that she knows $B$, but wthout revealing it. They proceed as follows:

- Alice chooses at random an element $r \in \mathbf{Z}_n^*$, and computes $T = r^e$. She sends $T$ to Bob and keeps $r$ secret (this is RSA encryption).
- Bob chooses at random an element $c \in \{0,\dots,e-1\}$ (called the
*challenge*) and sends it to Alice. - Alice computes $t = rB^c$ and sends it to Bob.
- Bob accepts the identification if and only if $I^ct^e = T$.

This protocol has the three usual properties:

**Completeness:** If Alice really is Alice, then she can always make Bob accept her identification: she just needs to compute $t = rB^c$ as indicated by the protocol. Then

\[ \begin{align*}

I^ct^e

&= I^c(rB^c)^e \\

&= I^cr^eB^{ce} \\

&= I^cr^eI^{-dce} \\

&= I^cr^e(I^{de})^{-c} \\

&= I^cr^eI^{-c} \\

&= r^e \\

&= T,

\end{align*} \]

so Bob will accept.

**Soundness:** If Alice can have her identification accepted by Bob no matter which challenge he sends her, then she must be Alice. Supose that, for a fixed value of $r$, Alice can give the accepted answers $t_1,t_2$ respectively to the challenges $c_1,c_2$. Then we have

\[ I^{c_1}t_1^e = T = I^{c_2}t_2^e, \]

and it follows that

\[ I^{c_1-c_2} = (t_2t_1^{-1})^e. \]

Since we assumed that $e$ is prime and we have $|c_1-c_2| < e$, $c_1-c_2$ and $e$ are relatively prime, and we can obtain a Bézout identity:
\[ a(c_1-c_2)+be = 1. \]
If we now let
\[ z = I^b(t_2t_1^{-1})^a, \]
we obtain
\[ \begin{align*}
z^e
&= I^{be}(t_2t_1^{-1})^{ae} \\
&= I^{be}I^{a(c_1-c_2)} \\
&= I^{be+a(c_1-c_2)} \\
&= I.
\end{align*} \]
This means that if Alice can successfully answer both challenges, then she must know an $e$th root $z$ of $I$ in $\mathbf{Z}_n^*$. The RSA assumption states that this is not possible in any reasonable time with non-negligible probability without knowing the prime factors of $n$. Since Alice does not know them, she must have obtained an $e$th root of $I$ from someone who does, and the only person who does is Trent. So the $e$th root of $I$ is just (the inverse of) her secret $B$, and since of course Trent will only give Alice the secret $B$ corresponding to an identity $I$ if $I$ really is Alice's identity, we see that Alice must be who she claims to be.
**Zero-knowledge:** What information does Bob obtain from the protocol? He first obtains $T = r^e$ for a $r$ randomly chosen by Alice. Since $e$ is public, Bob could just as well have generated a random $r$ himself, so he does not obtain anything new. Then he obtains $t = rB^c$, and since $r$ is random, $t$ must be random also since Bob cannot recover $r$ from $T$ (by the RSA assumption). So Bob does not learn anything about $B$.