The Guillou-Quisquater (GQ) Identification Scheme for Zero Knowledge Proof

We give anyway too much of our data and we need move to a world where we prove that we know something, and without revealing the original…
Photo by Maria Ziegler on Unsplash

The Guillou-Quisquater (GQ) Identification Scheme for Zero Knowledge Proof

We give anyway too much of our data and we need move to a world where we prove that we know something, and without revealing the original data. The method I will use in this article is defined here.

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 ᵉ(mod N). x is the secret value that the prover (Peggy) must prove (x∈ℤ∗N) [What is ℤ∗N? Find out here]. After Peggy generates his public proving key, she will then be challenged by Victor (the verifier) to produce the correct result.

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ᵉ (mod N)

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

Y←yᵉ (mod 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←yxᶜ (mod N)

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

val1=YXᶜ (mod N)

val2=Xᵉ (mod N)

If the values are the same (val1≡val2), Peggy has proven that she knows x. This works because:

YXᶜ=yᵉ(xᵉ)ᶜ=yᵉxᵉᶜ

zᵉ=(yxᶜ)ᵉ=yᵉxᵉᶜ

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

In the following we define a secret value (x), an exponent (e) and a modulus value (N) [here]:

Peggy (the Prover) generates these values:
x(secret)= 3
N=  101
X=  27
Peggy generates a random value (y):
y= 20
Peggy computes Y = y^e (mod N) and passes to Victor:
Y= 21
Victor generates a random value (c) and passes to Peggy:
c= 85
Peggy calculates z = y.x^c (mod N) and send to Victor (the Verifier):
Victor now computes val=z^e (mod N) and (y x^c (mod N)) and determines if they are the same
val1= 48  val2= 48
Peggy has proven that he knows x

What do the symbols means?

The following:

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 of this here.

For Y←yᵉ (mod N) we create Y by raising the value of y to the power of e and then take (mod N).

The following:

defines that we generate c from a random number with the number of bits of a length of x.

Coding

The coding to implement the simple demo is:

Conclusions

System designers need to look closely at their systems, and look to redesign in order to preserve privacy. The passing of a password over the network is already putting someone’s privacy at risk, so companies need to look toward zero-knowledge methods in order prove knowledge.

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]