Fiat-Shamir-Heuristik

In der Kryptographie ist die Fiat-Shamir-Heuristik (auch Fiat-Shamir-Transformation genannt ) ein Verfahren, um aus einem interaktiven Wissensnachweis eine digitale Signatur zu erstellen . Dadurch lässt sich eine Tatsache (z. B. die Kenntnis einer bestimmten geheimen Zahl) öffentlich beweisen, ohne die zugrundeliegenden Informationen preiszugeben. Das Verfahren geht auf Amos Fiat und Adi Shamir (1986) zurück. ^{[ 1 ]} Damit das Verfahren funktioniert, muss der ursprüngliche interaktive Beweis die Eigenschaft „öffentlich“ besitzen , d. h. die vom Prüfer verwendeten Zufallszahlen müssen während des gesamten Beweisprotokolls öffentlich sein.

Die Heuristik wurde ursprünglich ohne Sicherheitsbeweis vorgestellt. Später bewiesen Pointcheval und Stern ^{[ 2 ]} ihre Sicherheit gegen Angriffe mit gewählter Nachricht im Random-Oracle-Modell , also unter der Annahme, dass Random Oracles existieren. Dieses Ergebnis wurde von Don, Fehr, Majenz und Schaffner ^{[ 3 ]} sowie gleichzeitig von Liu und Zhandry ^{[ 4 ]} auf das quantenzugängliche Random Oracle (QROM) verallgemeinert. Für den Fall, dass keine Random Oracles existieren, wurde die Unsicherheit der Fiat-Shamir-Heuristik von Shafi Goldwasser und Yael Tauman Kalai ^{[ 5 ]} bewiesen . Die Fiat-Shamir-Heuristik demonstriert somit eine wichtige Anwendung von Random Oracles. Allgemeiner kann die Fiat-Shamir-Heuristik auch als Umwandlung eines interaktiven Wissensbeweises mit öffentlichen Coins in einen nicht-interaktiven Wissensbeweis betrachtet werden . Wird der interaktive Beweis als Identifikationswerkzeug verwendet, kann die nicht-interaktive Version direkt als digitale Signatur eingesetzt werden, indem die Nachricht als Teil der Eingabe für das Random Oracle verwendet wird. ^{[ 6 ]}

Für den unten beschriebenen Algorithmus sollten die Leser mit den multiplikativen Gruppen${\displaystyle \mathbb {Z} _{q}^{*}}$ vertraut sein , wobei q eine Primzahl ist, sowie mit dem Eulerschen Phi-Funktionssatz über die Eulersche Phi-Funktion φ .

Hier ist ein interaktiver Beweis für das Wissen über einen diskreten Logarithmus in , basierend auf der Schnorr-Signatur . ^{[ 7 ]} Die öffentlichen Werte sind und ein Generator g von , während der geheime Wert der diskrete Logarithmus von y zur Basis g ist . ${\displaystyle \mathbb {Z} _{q}^{*}}$${\displaystyle y\in \mathbb {Z} _{q}^{*}}$${\displaystyle \mathbb {Z} _{q}^{*}}$

1. Peggy möchte Victor, dem Prüfer, beweisen, dass sie weiß, wie man befriedigt, ohne etwas preiszugeben .${\displaystyle x}$${\displaystyle y\equiv g^{x}}$${\displaystyle x}$
2. Peggy wählt zufällig eine Zahl aus , berechnet das Ergebnis und sendet es an Victor.${\displaystyle v\in \mathbb {Z} _{q}^{*}}$${\displaystyle t=g^{v}}$${\displaystyle t}$
3. Victor wählt zufällig eine Zahl aus und schickt sie an Peggy.${\displaystyle c\in \mathbb {Z} _{q}^{*}}$
4. Peggy berechnet das Ergebnis und meldet es Victor zurück.${\displaystyle r=v-cx{\bmod {\varphi }}(q)}$${\displaystyle r}$
5. Victor prüft, ob . Dies trifft zu, weil und .${\displaystyle t\equiv g^{r}y^{c}}$${\displaystyle g^{r}y^{c}\equiv g^{v-cx}g^{xc}\equiv g^{v}\equiv t}$${\displaystyle g^{\varphi (q)}\equiv 1}$

Die Fiat-Shamir-Heuristik ermöglicht es, den interaktiven Schritt 3 durch einen nicht-interaktiven Zufallsorakelzugriff zu ersetzen . In der Praxis kann stattdessen eine kryptografische Hash-Funktion verwendet werden . ^{[ 8 ]}

1. Peggy möchte beweisen, dass sie so viel weiß, ohne es preiszugeben .${\displaystyle x}$${\displaystyle y\equiv g^{x}}$${\displaystyle x}$
2. Peggy wählt zufällig eine Zahl aus und berechnet sie .${\displaystyle v\in \mathbb {Z} _{q}^{*}}$${\displaystyle t=g^{v}}$
3. Peggy berechnet , wobei eine kryptografische Hash-Funktion ist.${\displaystyle c=H(g,y,t)}$${\displaystyle H}$
4. Peggy berechnet . Der resultierende Beweis ist das Paar .${\displaystyle r=v-cx{\bmod {\varphi }}(q)}$${\displaystyle (t,r)}$
5. Jeder kann diesen Beweis verwenden, um zu berechnen und zu überprüfen, ob .${\displaystyle c}$${\displaystyle t\equiv g^{r}y^{c}}$

Wenn der unten verwendete Hashwert nicht vom (öffentlichen) Wert von y abhängt , wird die Sicherheit des Schemas geschwächt, da ein böswilliger Beweiser dann einen bestimmten Wert t wählen kann , sodass das Produkt cx bekannt ist. ^{[ 9 ]}

Solange mit den beiden Parteien bekannten Daten ein fester Zufallsgenerator konstruiert werden kann, kann jedes interaktive Protokoll in ein nicht-interaktives umgewandelt werden.

• Gabellemma
• Zufallsorakelmodell
• Nicht-interaktiver Zero-Knowledge-Beweis
• eine Anwendung im anonymen Veto-Netzwerk