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

Leave a Reply

Your email address will not be published. Required fields are marked *