Sigma-Protokolle und Schnorr-Identifikation

Ein Sigma-Protokoll besteht aus drei Nachrichten: (1) Commitment: Der Prover sendet ein Commitment für einen zufälligen Wert. (2) Challenge: Der Verifier sendet eine zufällige Challenge. (3) Response: Der Prover sendet eine aus der Challenge und dem Geheimnis berechnete Response. Der Verifier akzeptiert oder verwirft den Beweis.

Der Prover kennt das Geheimnis x (den privaten Schlüssel); der öffentliche Schlüssel ist = g^x mod p (oder der Punkt X = x*G auf einer elliptischen Kurve). Ziel ist es, die Kenntnis von x nachzuweisen, ohne x offenzulegen. Dies ist ein Wissensbeweis für den diskreten Logarithmus.

(1) Der Prover wählt ein zufälliges r und sendet das Commitment R = r*G. (2) Der Verifier sendet die Challenge c (eine zufällige Ganzzahl). (3) Der Prover sendet die Response s = r + c*x. (4) Der Verifier prüft s*G == R + c*X. Falls die Prüfung erfolgreich ist, wird der Beweis akzeptiert. Der Prover kennt x; die Response s kann nur mit x berechnet werden.

Vollständigkeit: Ein ehrlicher Prover erfüllt immer s*G = r*G + c*x*G = R + c*X. Korrektheit: Zwei Transkripte mit demselben R, aber unterschiedlichen Challenges c und c' liefern s und s', aus denen sich x = (s-s')/(c-c') zurückgewinnen lässt — ein Betrüger kann also nicht zwei gültige Responses für dasselbe R erzeugen.

Simulator (ohne Kenntnis von x): Wählen Sie ein zufälliges s und c und setzen Sie R = s*G - c*X. Das Tripel (R, c, s) hat dann die Verteilung eines gültigen Transkripts. Der Verifier kann echte Transkripte nicht von simulierten unterscheiden — Schnorr ist Zero-Knowledge gegenüber einem ehrlichen Verifier.

Das Schnorr-Protokoll wird nicht interaktiv, indem die Challenge des Verifiers durch c = Hash(R || message) ersetzt wird. Der Prover berechnet c selbst und sendet anschließend die Response. Das Ergebnis ist ein aus zwei Elementen bestehender Beweis (R, s), den jede Person verifizieren kann. Dies ist das Schnorr-Signaturschema.

Sign(x, m): r ← zufällig; 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 für P-256), stapelweise verifizierbar und im ROM beweisbar sicher. In Bitcoin Taproot (BIP-340) eingesetzt.

C = r*G + v*H, wobei H ein zweiter unabhängiger Generator ist. Damit wird der Wert v mit der Zufälligkeit r festgelegt. Bindend: Das Commitment kann nicht für einen anderen Wert v geöffnet werden (diskreter Logarithmus). Verbergend: C ist gleichverteilt. Wird in schnorrbasierten Bereichsbeweisen und Bulletproofs verwendet.

Um die Kenntnis von x1 UND x2 gleichzeitig nachzuweisen, werden zwei Schnorr-Protokolle mit derselben Challenge ausgeführt (die Challenge wird über Fiat-Shamir geteilt). Der Verifier akzeptiert den Beweis nur, wenn beide Teilbeweise gültig sind. Dadurch lassen sich mehrere Aussagen in einer Interaktion nachweisen.

Um die Kenntnis von x1 ODER x2 nachzuweisen, ohne offenzulegen, welches Geheimnis bekannt ist, wird für einen Zweig der Simulator verwendet, um ein gefälschtes Transkript zu berechnen; anschließend wird die Challenge auf beide Zweige aufgeteilt. Der Verifier sieht zwei gültig aussehende Transkripte, deren Challenges sich zur echten Challenge addieren. Diese Beweise werden als „ring signatures“ bezeichnet.

Schnorr-Identifikationen: elektronische Reisepässe (PACE-Protokoll). Schnorr-Signaturen: Bitcoin Taproot, Monero (RingCT verwendet Schnorr-OR-Beweise), Signal Protocol (X3DH-Schlüsselaustausch). Pedersen-Commitments: Confidential Transactions, Bulletproofs, Zcash-Sapling-Notizverschlüsselung.

Was prüft der Verifier im letzten Schritt des Schnorr-Identifikationsprotokolls?

Sigma-Protokolle folgen dem Ablauf Commitment–Challenge–Response. Schnorr weist die Kenntnis eines diskreten Logarithmus nach. Fiat-Shamir macht das Protokoll nicht interaktiv (Schnorr-Signatur). Als Nächstes folgen zk-SNARKs für kompakte nicht interaktive Beweise.