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]