Sigma-protokoller og Schnorr-identifikation

En Sigma-protokol har 3 meddelelser: (1) Forpligtelse: beviseren sender en forpligtelse til en tilfældig værdi. (2) Udfordring: verifikatoren sender en tilfældig udfordring. (3) Svar: beviseren sender et svar, der beregnes ud fra udfordringen og hemmeligheden. Verifikatoren accepterer eller afviser.

Beviseren kender hemmeligheden x (privat nøgle); offentlig nøgle = g^x mod p (eller punktet X = x*G på en elliptisk kurve). Målet er at bevise kendskab til x uden at afsløre den. Dette er et bevis på kendskab til en diskret logaritme.

(1) Beviseren vælger en tilfældig r-værdi og sender forpligtelsen R = r*G. (2) Verifikatoren sender udfordringen c (et tilfældigt heltal). (3) Beviseren sender svaret s = r + c*x. (4) Verifikatoren kontrollerer s*G == R + c*X. Hvis det passer, accepterer verifikatoren. Beviseren kender x; svaret s kan kun beregnes med x.

Fuldstændighed: en ærlig beviser opfylder altid s*G = r*G + c*x*G = R + c*X. Sundhed: to protokoludskrifter med samme R, men forskellige udfordringer c og c', giver s og s', hvorfra x = (s-s')/(c-c') kan genskabes — derfor kan en snyder ikke producere to gyldige svar for samme R.

Simulator (uden kendskab til x): vælg et tilfældigt s og c, og sæt R = s*G - c*X. (R, c, s) har dermed fordelingen for en gyldig protokoludskrift. Verifikatoren kan ikke skelne virkelige protokoludskrifter fra simulerede — Schnorr giver nulviden over for en ærlig verifikator.

Gør Schnorr ikke-interaktiv: erstat verifikatorens udfordring med c = Hash(R || message). Beviseren beregner selv c og sender svaret. Resultatet er et bevis med 2 elementer (R, s), som alle kan verificere. Dette er Schnorr-signatursystemet.

Sign(x, m): r ← random; R = r*G; c = Hash(R||m); s = r + c*x. Signatur = (R, s). Verify: s*G == R + Hash(R||m)*X. Kompakt (64 bytes for P-256), kan verificeres samlet og er bevist sikkert i ROM. Anvendt i Bitcoin Taproot (BIP-340).

C = r*G + v*H, hvor H er en anden uafhængig generator. Forpligter sig til værdien v med tilfældigheden r. Bindende egenskab: kan ikke åbnes til en anden v-værdi (diskret logaritme). Skjuleegenskab: C er uniformt fordelt. Bruges i intervalbeviser baseret på Schnorr og i Bulletproofs.

Bevis kendskab til x1 OG x2 samtidigt: kør to Schnorr-protokoller med samme udfordring (del udfordringen via Fiat-Shamir). Verifikatoren accepterer kun, hvis begge delbeviser er gyldige. Gør det muligt at bevise flere udsagn i én interaktion.

Bevis kendskab til x1 ELLER x2 uden at afsløre hvilket: brug simulatoren for den ene gren til at beregne en falsk protokoludskrift, og fordel derefter udfordringen mellem begge grene. Verifikatoren ser to gyldige protokoludskrifter, hvis udfordringer tilsammen giver den virkelige udfordring. Kaldes "ringsignaturer".

Schnorr-identifikationer: elektroniske pas (PACE-protokollen). Schnorr-signaturer: Bitcoin Taproot, Monero (RingCT bruger Schnorr-ELLER-beviser), Signal Protocol (X3DH-nøgleaftale). Pedersen-forpligtelser: fortrolige transaktioner, Bulletproofs, Zcash Sapling-note-kryptering.

Sigma-protokoller: forpligtelse–udfordring–svar. Schnorr beviser kendskab til en diskret logaritme. Fiat-Shamir gør protokollen ikke-interaktiv (Schnorr-signaturen). Næste emne: zk-SNARK'er til korte ikke-interaktive beviser.