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:
