Guillou-Quisquater

Pour les articles homonymes, voir Guillou.

Le protocole de Guillou-Quisquater ou GQ est une preuve à divulgation nulle de connaissance proposée par Louis Guillou et Jean-Jacques Quisquater^[1] pour prouver la connaissance d'un message clair RSA pour un chiffré public. Cette preuve peut-être dérivée en protocole d'authentification par l'heuristique de Fiat-Shamir.

Alice veut s'authentifier auprès de Bob. Elle est en possession d'un certificat public ${\displaystyle J_{\textrm {A}}~}$ ainsi que d'un certificat privé ${\displaystyle S_{\textrm {A}}=J_{\textrm {A}}^{-s}~mod~n}$. Le but est de prouver la possession du certificat privé.

La signature se fait grâce aux paramètres suivants :

• ${\displaystyle n=pq~}$, de la même manière que dans RSA
• un nombre ${\displaystyle v~}$ qui sert de clé publique tel que ${\displaystyle {\textrm {gcd}}(v,\varphi (n))=1~}$
• un nombre ${\displaystyle s~}$ qui sert de clé privée tel que ${\displaystyle sv=1~mod~\varphi (n)~}$

Le schéma d'identification est construit comme un protocole Σ^[2] en trois parties :

1. L'engagement :
   1. Alice choisit un nombre aléatoire ${\displaystyle r~}$
   2. Alice calcule ${\displaystyle x=r^{v}~mod~n}$
   3. Alice envoie ${\displaystyle x~}$ et ${\displaystyle J_{\textrm {A}}~}$ à Bob
2. Le défi :
   1. Bob choisit un nombre aléatoire ${\displaystyle e~}$ tel que ${\displaystyle 1\leq e\leq v}$
   2. Bob envoie ${\displaystyle e~}$ à Alice
3. La réponse :
   1. Alice calcule ${\displaystyle y=rS_{\textrm {A}}^{e}~mod~n}$ et l'envoie à Bob
   2. Bob calcule ${\displaystyle J_{\textrm {A}}^{e}y^{v}}$ et vérifie que le résultat est égal à ${\displaystyle x~}$ et différent de 0.

• [Guillou et Quisquater 1988] Louis C. Guillou et Jean-Jacques Quisquater, « A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory », Eurocrypt,‎ 1988 (DOI 10.1007/3-540-45961-8_11)
• [Damgård 2010] (en) Ivan Damgård, « On Σ-Protocols », Notes de cours [PDF],‎ 2010

• Digital Signature Algorithm
• Preuve à divulgation nulle de connaissance
• Elliptic curve digital signature algorithm

• Portail de la sécurité informatique
• Portail de la cryptologie