Sigma-protokoll och Schnorr-identifiering

Ett Sigma-protokoll har 3 meddelanden: (1) Åtagande: bevisaren skickar ett åtagande till ett slumpmässigt värde. (2) Utmaning: verifieraren skickar en slumpmässig utmaning. (3) Svar: bevisaren skickar ett svar som beräknats utifrån utmaningen och hemligheten. Verifieraren godkänner eller avvisar.

Bevisaren känner till hemligheten x (den privata nyckeln); den offentliga nyckeln = g^x mod p (eller punkten X = x*G på en elliptisk kurva). Målet är att bevisa kunskap om x utan att avslöja den. Detta är ett kunskapsbevis för diskret logaritm.

(1) Bevisaren väljer ett slumpmässigt r och skickar åtagandet R = r*G. (2) Verifieraren skickar utmaningen c (ett slumpmässigt heltal). (3) Bevisaren skickar svaret s = r + c*x. (4) Verifieraren kontrollerar s*G == R + c*X. Om det stämmer godkänner verifieraren. Bevisaren känner till x; svaret s kan bara beräknas med hjälp av x.

Fullständighet: en ärlig bevisare uppfyller alltid s*G = r*G + c*x*G = R + c*X. Korrekthet: två transkript med samma R men olika utmaningar c och c' ger s och s', varifrån x = (s-s')/(c-c') kan återställas — en fuskare kan alltså inte skapa två giltiga svar för samma R.

Simulator (utan kunskap om x): välj slumpmässiga s och c, och sätt R = s*G - c*X. (R, c, s) följer då fördelningen för ett giltigt transkript. Verifieraren kan inte skilja verkliga transkript från simulerade — Schnorr är zero-knowledge mot en ärlig verifierare.

Gör Schnorr icke-interaktivt: ersätt verifierarens utmaning med c = Hash(R || message). Bevisaren beräknar själv c och skickar svaret. Resultatet är ett bevis med två element (R, s) som vem som helst kan verifiera. Detta är Schnorrs signaturschema.

Sign(x, m): r ← slumpmässigt värde; R = r*G; c = Hash(R||m); s = r + c*x. Signatur = (R, s). Verifiera: s*G == R + Hash(R||m)*X. Kompakt (64 byte för P-256), kan verifieras i batchar och är bevisat säker i ROM. Används i Bitcoin Taproot (BIP-340).

C = r*G + v*H där H är en andra oberoende generator. Ger ett åtagande till värdet v med slumpvärdet r. Bindande: det går inte att öppna åtagandet för ett annat v (diskret logaritm). Döljande: C är likformigt fördelat. Används i intervallbevis baserade på Schnorr och i Bulletproofs.

Bevisa kunskap om x1 OCH x2 samtidigt: kör två Schnorr-protokoll med samma utmaning (dela utmaningen via Fiat-Shamir). Verifieraren godkänner endast om båda delbevisen är giltiga. Detta möjliggör bevis av flera påståenden i en enda interaktion.

Bevisa kunskap om x1 ELLER x2 utan att avslöja vilket: använd simulatorn för den ena grenen för att beräkna ett falskt transkript och dela sedan utmaningen mellan båda. Verifieraren ser två giltiga transkript som tillsammans ger den verkliga utmaningen. Detta kallas "ringsignaturer".

Schnorr-ID:n: elektroniska pass (PACE-protokollet). Schnorr-signaturer: Bitcoin Taproot, Monero (RingCT använder Schnorrs OR-bevis), Signal Protocol (X3DH-nyckelöverenskommelse). Pedersen-åtaganden: Confidential Transactions, Bulletproofs, Zcash Sapling note encryption.

Sigma-protokoll: åtagande–utmaning–svar. Schnorr bevisar kunskap om en diskret logaritm. Fiat-Shamir gör protokollet icke-interaktivt (Schnorr-signatur). Nästa avsnitt: zk-SNARK:er för kortfattade icke-interaktiva bevis.