Guillou Quisquater Protocol

The Guillou-Quisquater-Protocol (abbreviation: GQ) is a protocol from the field of cryptography with which you can authenticate yourself to someone . The protocol was developed by Louis Guillou and Jean-Jacques Quisquater and is based on the problem of prime factorization .

functionality

Peggy wants to authenticate herself to Victor . A trustworthy third party provides you with a number that is the product of two large prime numbers. The two prime numbers are secret and only known to the third party itself. ${\displaystyle n}$

Peggy chooses a number with a public certificate and gets a private certificate from the trusted third party assigned. Peggy wants to prove to Victor that she has the private certificate without Victor receiving the certificate. ${\displaystyle J}$ ${\displaystyle 0\leq J<n}$ ${\displaystyle S_{\text{A}}=J^{-s}\mod n}$

The procedure uses the following parameters:

• A number as a public key with ${\displaystyle v}$ ${\displaystyle \operatorname {ggT} (v,\varphi (n))=1~}$
• A number as a private key with ${\displaystyle s}$ ${\displaystyle sv=1\mod \varphi (n)~}$

Protocol steps

1. Peggy chooses a random number with ${\displaystyle r}$ ${\displaystyle 1<r<n-1}$
2. Peggy calculates ${\displaystyle x=r^{v}\mod n}$
3. Peggy sends and to Victor ${\displaystyle x}$ ${\displaystyle J}$
4. Victor chooses a random number with ${\displaystyle d}$ ${\displaystyle 0<d<v-1}$
5. Victor sends to Peggy ${\displaystyle d}$
6. Peggy charges a witness ${\displaystyle t=r\cdot S_{A}^{d}\mod n}$
7. Peggy sends the witness to Victor ${\displaystyle t}$
8. Victor calculates and verifies whether the result is the same . ${\displaystyle J^{d}\cdot t^{v}}$ ${\displaystyle x}$

literature

• Douglas R. Stinson: Cryptography. Theory and Practice. 3. Edition. Chapman & Hall / CRC, 2005, ISBN 1-58488-508-4 , pages 383-387
• Louis Guillou, Jean-Jacques Quisquater: A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In: Lecture Notes in Computer Science Vol. 330. Advances in Cryptology - EUROCRYPT'88 Proceedings. Springer-Verlag, 1998, ISBN 0-387-50251-3 , pages 123-128
• Mihir Bellare , Adriana Palacio: GQ and Schnor identification schemes: proofs of security against impersonation under active and concurrent attacks. In: Lecture Notes in Computer Science Volume 2442. Advances in Cryptology - CRYPTO 2002 Proceedings. Springer-Verlag, 2002, ISBN 978-3-540-44050-5 , pp. 149-162