# Consequence of a change on the Guillou-Quisquater Protocol

In the Guillou-Quisquater Protocol, the prover convinces the verifier that he knows an $e$-th root of an element $y \in \mathbb{Z}^*_n$ ($p, q, e$ are primes, $n = pq$ and $e$ is coprime with $\varphi(n)$). The protocol between prover $P$ and verifier $V$ (see here for instance) is:

1. $P$ picks $r$ at random in $\mathbb{Z}^*_n$ and sends $a = r^e \mod n$ to $V$.
2. $V$ picks $c$ at random in $\mathbb{Z}_e$ and sends it to $P$.
3. $P$ computes $z = a x^c$ and sends it to $V$.
4. $V$ accepts iff $z^e = a y^c$.

What happens if $e$ divides $\varphi(n)$ and the protocol still succeeds (i.e. $V$ has received an $a$, sent back $c$, and get $z$ s.t. $z^e = a y^c$)? I don't think it still proves that $P$ knows an $e$-th root of $y$... It is even possible that $y$ doesn't have any $e$-th root (since $e$ and $\varphi(n)$ aren't coprime). But does it proves something (new) about $y$?

Yes it proves that $y \ne 1 \pmod{n}$ is not an $e$-th root. That is, no $x$ exists such that $x^e = y \pmod{n}$. In particular, if $e | \phi(n)$ then for any $x$ it holds that $\left( x^{ \frac{\phi(n)} {e}} \right)^e = 1 \ne y$.
Regarding GQ protocol: prover will be unable to pick an $r$ such that $a = r^e \ne 1$.
• You mean that $f(x)=x^{\varphi(n)/e}$ is a permutation over $\mathbb{Z}^*_n$ (since its inverse is $f^{-1}(y) = y^e$), thus $x^e = 1$ for all $x \in \mathbb{Z}^*_n$ (in particular, $y \neq 1$ cannot be an $e$-th root). Thus, we always have $a=1$ and $z^e = 1$ in the protocol. So if the protocol succeeds it means that $y^c = 1$ i.e.$V$ has learnt that $y$ is a $c$-th root of $1$. Am I right? – permanganate Nov 17 '15 at 13:30
• @permanganate Exactly, no $y \ne 1$ could be an $e$-th root in this case, so either $y=1$ or it's not an $e$-th root. And it holds before starting the protocol. – Vadym Fedyukovych Nov 17 '15 at 14:04