# The Guillou-Quisquater protocol

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:

1. 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).
2. Bob chooses at random an element $c \in \{0,\dots,e-1\}$ (called the challenge) and sends it to Alice.
3. Alice computes $t = rB^c$ and sends it to Bob.
4. 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$.

This site uses Akismet to reduce spam. Learn how your comment data is processed.