[Back] The Guillou-Quisquater (GQ) identification scheme was defined in 1988 [1] and supports a zero knowledge proof method. The prover (Peggy) has a proving public key of \((N,e,X)\) where \(N\) is the modulus, \(e\) is the exponent, and \(X= x^e \pmod N \). \(x\) is the secret value that the prover (Peggy) must prove (\(x \in \mathbb{Z}^*_N)\) [What is \(\mathbb{Z}^*_N\)? Find out here]. After Peggy generates his public proving key, she will then be challenged by Victor to produce the correct result. In the following we define a secret value (\(x\)), an exponent (\(e\)) and a modulus value (\(N\)):

## GQ identification scheme |

## Method

With the GQ method, Peggy (the prover) has a proving public key of \((N,e,X)\) and a proving secret key of \((N,x)\). \(N\) is a prime number for the modulus operation. In this case \(x\) is the secret, and where:

\(X = x^e \pmod N\)

On the registration of the secret, Peggy generates a random value (\(y\)), and then computes \(Y\):

\(Y \leftarrow y^e \pmod N\)

This value is sent to Victor (who is the verifier). Victor then generates a random value \((c)\) and sends this to Peggy. This is a challenge to Peggy to produce the correct result. Peggy then computes:

\(z \leftarrow y x^c \pmod N\)

She then sends this to Victor in order to prove that she knows \(x\). Victor then computes two values:

\(val_1 = Y X^c \pmod N\)

\(val_2 =X^e \pmod N\)

If the values are the same (\(val_1 \equiv val_2\)), Peggy has proven that she knows \(x\).

This works because:

\(Y X^c = y^e (x^e)^c = y^e x^{ec}\)

\(z^e = (y x^c)^e = y^e x^{ec}\)

In a formal definition (taken from this paper) [2], the method is:

## What do the symbols means?

The following:

\(y \overset{R}{\leftarrow} \mathbb{Z}^*_N\)

defines that we generate a **random number** which does not share any factors with \(N\) (and is defined as relative prime), there is an overview here.

For:

\(Y \leftarrow y^e \pmod N\)

we create \(Y\) by raising the value of \(y\) to the power of \(e\) and then take\(\pmod N\).

The following:

\(c \overset{R}{\leftarrow} \{0,1\}^{l(k)}\)

defines that we generate \(c\) from a random number the number of bits of the length of \(x\).

## Coding

import random import sys e=3 N=101 def gcd(a,b): while b > 0: a, b = b, a % b return a x = random.randint(1,100) X = pow(x,e,N) y = random.randint(1,100) Y = pow(y,e,N) if (gcd(x,N)>1): print "Warning x shares a factor with N" if (gcd(y,N)>1): print "Warning y shares a factor with N" print "Peggy generates these values:" print "x(secret)=\t",x print "N=\t\t",N print "X=\t\t",X print "\nPeggy generates a random value (y):" print "y=",y print "\nPeggy computes Y = y^e (mod N) and passes to Victor:" print "Y=",Y print "\nVictor generates a random value (c) and passes to Peggy:" c = random.randint(1,100) print "c=",c print "\nPeggy calculates z = y.x^c (mod N) and send to Victor:" z = (y* x**c) % N print "\nVictor now computes val=z^e (mod N) and (y x^c (mod N)) and determines if they are the same\n" val1= (z**e) % N val2= (Y* X**c) % N print "val1=\t",val1 print "val2=\t",val2 if (val1==val2): print "Peggy has proven that he knows x" else: print "Failure to prove"

## References

[1] L. Guillou and J. J. Quisquater. A “paradoxical” identity-based signature scheme resulting from zero-knowledge. Advances in Cryptology – CRYPTO ’88, Lecture Notes in Computer Science Vol. 403, S. Goldwasser ed., Springer-Verlag, 1988. [paper]

[2] Bellare, M., & Palacio, A. (2002, August). GQ and Schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks. In Annual International Cryptology Conference (pp. 162-177). Springer, Berlin, Heidelberg. [paper]