Sigma-protocollen en Schnorr-identificatie

Een sigmaprotocol heeft 3 berichten: (1) Vastlegging: de bewijzer stuurt een vastlegging van een willekeurige waarde. (2) Uitdaging: de verificateur stuurt een willekeurige uitdaging. (3) Antwoord: de bewijzer stuurt een antwoord dat is berekend op basis van de uitdaging en het geheim. De verificateur accepteert of weigert.

De bewijzer kent het geheim x (de privésleutel); openbare sleutel = g^x mod p (of punt X = x*G op een elliptische kromme). Het doel is kennis van x te bewijzen zonder x bekend te maken. Dit is een bewijs van kennis van een discrete logaritme.

(1) De bewijzer kiest een willekeurige r en stuurt de vastlegging R = r*G. (2) De verificateur stuurt uitdaging c (een willekeurig geheel getal). (3) De bewijzer stuurt antwoord s = r + c*x. (4) De verificateur controleert s*G == R + c*X. Als dat zo is, accepteert de verificateur het. De bewijzer kent x; antwoord s kan alleen met x worden berekend.

Volledigheid: een eerlijke bewijzer voldoet altijd aan s*G = r*G + c*x*G = R + c*X. Deugdelijkheid: twee protocolverlopen met dezelfde R maar verschillende uitdagingen c, c' leveren s, s' op, waaruit x = (s-s')/(c-c') kan worden teruggewonnen — een valsspeler kan dus geen twee geldige antwoorden voor dezelfde R produceren.

Simulator (zonder kennis van x): kies willekeurige s en c en stel R = s*G - c*X in. Dit (R, c, s) vormt een geldige verdeling van protocolverlopen. De verificateur kan echte protocolverlopen niet onderscheiden van gesimuleerde — Schnorr is zero-knowledge voor eerlijke verificateurs.

Maak Schnorr niet-interactief: vervang de uitdaging van de verificateur door c = Hash(R || message). De bewijzer berekent c zelf en stuurt het antwoord. Het resultaat: een bewijs met 2 elementen (R, s) dat iedereen kan verifiëren. Dit is het Schnorr-handtekeningschema.

Sign(x, m): r ← willekeurig; R = r*G; c = Hash(R||m); s = r + c*x. Handtekening = (R, s). Verify: s*G == R + Hash(R||m)*X. Compact (64 bytes voor P-256), in bundels te verifiëren en aantoonbaar veilig in ROM. Toegepast in Bitcoin Taproot (BIP-340).

C = r*G + v*H waarbij H een tweede onafhankelijke generator is. Legt waarde v vast met willekeur r. Bindend: je kunt de vastlegging niet openen naar een andere v (discrete logaritme). Verhulling: C is uniform verdeeld. Wordt gebruikt in op Schnorr gebaseerde bereikbewijzen en Bulletproofs.

Bewijs tegelijkertijd kennis van x1 EN x2: voer twee Schnorr-protocollen uit met dezelfde uitdaging (deel de uitdaging via Fiat-Shamir). De verificateur accepteert het bewijs alleen als beide deelbewijzen geldig zijn. Hiermee kun je meerdere beweringen in één interactie bewijzen.

Bewijs kennis van x1 OF x2 zonder bekend te maken welke: gebruik de simulator voor één tak om een vals protocolverloop te berekenen en splits de uitdaging vervolgens over beide takken. De verificateur ziet twee geldig ogende protocolverlopen die samen de echte uitdaging vormen. Dit worden ringhandtekeningen genoemd.

Schnorr-identificaties: elektronische paspoorten (PACE-protocol). Schnorr-handtekeningen: Bitcoin Taproot, Monero (RingCT gebruikt Schnorr-OF-bewijzen), Signal Protocol (X3DH-sleutelovereenkomst). Pedersen-vastleggingen: Confidential Transactions, Bulletproofs en versleuteling van Zcash Sapling-notities.

Sigmaprotocollen: vastleggen-uitdagen-antwoorden. Schnorr bewijst kennis van een discrete logaritme. Fiat-Shamir maakt het niet-interactief (Schnorr-handtekening). Hierna: zk-SNARKs voor beknopte niet-interactieve bewijzen.