Protocoles Sigma et identification de Schnorr

Un protocole Sigma comporte 3 messages : (1) Engagement : le prouveur envoie un engagement envers une valeur aléatoire. (2) Défi : le vérificateur envoie un défi aléatoire. (3) Réponse : le prouveur envoie une réponse calculée à partir du défi et du secret. Le vérificateur accepte ou rejette.

Le prouveur connaît le secret x (la clé privée) ; la clé publique = g^x mod p (ou le point X = x*G sur une courbe elliptique). Objectif : prouver la connaissance de x sans le révéler. Il s'agit d'une preuve de connaissance du logarithme discret.

(1) Le prouveur choisit un r aléatoire et envoie l'engagement R = r*G. (2) Le vérificateur envoie le défi c (un entier aléatoire). (3) Le prouveur envoie la réponse s = r + c*x. (4) Le vérificateur vérifie s*G == R + c*X. Si c'est le cas, il accepte. Le prouveur connaît x ; la réponse s ne peut être calculée qu'avec x.

Complétude : un prouveur honnête respecte toujours s*G = r*G + c*x*G = R + c*X. Solidité : deux transcriptions ayant le même R mais des défis différents c et c' donnent s et s', à partir desquels x = (s-s')/(c-c') peut être retrouvé — un tricheur ne peut donc pas produire deux réponses valides pour le même R.

Simulateur (sans connaître x) : choisir s et c aléatoires, puis définir R = s*G - c*X. Le triplet (R, c, s) suit une distribution de transcriptions valides. Le vérificateur ne peut pas distinguer les transcriptions réelles des transcriptions simulées — Schnorr est à divulgation nulle de connaissance pour un vérificateur honnête.

Rendre Schnorr non interactif : remplacer le défi du vérificateur par c = Hash(R || message). Le prouveur calcule lui-même c et envoie la réponse. Résultat : une preuve composée de deux éléments (R, s), que n'importe qui peut vérifier. Il s'agit du schéma de signature de Schnorr.

Sign(x, m) : r ← aléatoire ; R = r*G ; c = Hash(R||m) ; s = r + c*x. Signature = (R, s). Vérification : s*G == R + Hash(R||m)*X. Compacte (64 octets pour P-256), vérifiable par lots et prouvée sûre dans ROM. Adoptée dans Taproot de Bitcoin (BIP-340).

C = r*G + v*H, où H est un second générateur indépendant. Cet engagement associe la valeur v au hasard r. Liaison : impossible de l'ouvrir pour une autre valeur v (logarithme discret). Dissimulation : C suit une distribution uniforme. Utilisé dans les preuves d'appartenance à un intervalle fondées sur Schnorr et dans les Bulletproofs.

Prouver simultanément la connaissance de x1 AND x2 : exécuter deux protocoles de Schnorr avec le même défi (partager le défi via Fiat-Shamir). Le vérificateur n'accepte que si les deux sous-preuves sont valides. Cela permet de prouver plusieurs affirmations lors d'une seule interaction.

Prouver la connaissance de x1 OR x2 sans révéler lequel : utiliser le simulateur pour une branche afin de calculer une transcription factice, puis répartir le défi entre les deux branches. Le vérificateur voit deux transcriptions qui semblent valides et dont la somme correspond au défi réel. On appelle cela des « signatures en anneau ».

Identifications Schnorr : passeports électroniques (protocole PACE). Signatures Schnorr : Taproot de Bitcoin, Monero (RingCT utilise des preuves OR de Schnorr), protocole Signal (accord de clés X3DH). Engagements de Pedersen : transactions confidentielles, Bulletproofs, chiffrement des notes de Zcash Sapling.

Dans le protocole d'identification de Schnorr, que vérifie le vérificateur lors de l'étape finale ?

Protocoles Sigma : engagement-défi-réponse. Schnorr prouve la connaissance d'un logarithme discret. Fiat-Shamir le rend non interactif (signature de Schnorr). Ensuite : les zk-SNARK pour les preuves non interactives concises.