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


1 Answer 1


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

This probably means one last final conclusion designed as a homework.

Regarding GQ protocol: prover will be unable to pick an $r$ such that $a = r^e \ne 1$.

  • $\begingroup$ 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? $\endgroup$ Commented Nov 17, 2015 at 13:30
  • $\begingroup$ @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. $\endgroup$ Commented Nov 17, 2015 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.