Fiat-Shamir-Heuristik

Die Fiat-Shamir-Heuristik ist eine kryptographische Technik, mit deren Hilfe man aus einem interaktiven Beweis eine Digitale Signatur erzeugen kann. Auf diese Weise kann eine bestimmte Tatsache (zum Beispiel das Wissen über eine bestimmte Zahl) bewiesen werden, ohne dass die zugrundeliegende Information erkennbar wird. Diese Technik wurde 1986 von Amos Fiat und Adi Shamir entwickelt. Der ursprüngliche interaktive Beweis muss die Öffentliche-Münze-Eigenschaft haben, damit die Methode greift. Für den unten angegebenen Algorithmus sollte der Leser mit modularer Arithmetik vertraut sein, besonders mit jener in den so genannten P-Gruppen.

Die Heuristik wurde ursprünglich ohne Sicherheitsbeweis präsentiert, später zeigten Pointcheval und Stern ihre Sicherheit gegenüber dem Chosen-Plaintext-Angriff im Zufallsorakel-Modell, das bedeutet, unter der Annahme, dass solche Zufallsorakel existieren. Für den Fall, dass diese nicht existieren, wurde die Fiat-Shamir-Heuristik durch Goldwasser und Kalai als unsicher bewiesen. Wenn der unten berechnete Hashwert nicht vom (öffentlichen) Wert von $y$ abhängt, wird die Sicherheit des Algorithmus kompromittiert, da ein böswilliger Beweiser den Wert $c$ in einem gewissen Rahmen festlegen könnte.

Allgemein kann man die Fiat-Shamir-Heuristik als einen Weg betrachten, einen interaktiven Beweis mit öffentlichen Münzen in einen nicht-interaktiven null-Wissen-Beweis umzuwandeln. Wenn der interaktive Beweis ein Identifikationsprotokoll ist, kann die nicht-interaktive Version als digitale Signatur verwendet werden.

Beispiel

Dies ist ein interaktiver Beweis des Wissens eines diskreten Logarithmus.

1. Alice will Bob beweisen, dass sie $x$ kennt, den diskreten Logarithmus von $y=g^{x}$ zur Basis $g$.
2. Sie wählt ein $v\in \mathbb {Z} _{q}$, berechnet $t=g^{v}$ und schickt $t$ an Bob.
3. Bob wählt ein zufälliges $c\in \mathbb {Z} _{q}^{*}$ und schickt es an Alice.
4. Alice berechnet $r=v-cx$ und schickt $r$ an Bob.
5. Bob überprüft, ob $t\equiv g^{r}y^{c}$ (diese Aussage ist wahr, da $g^{r}y^{c}=g^{v-cx}g^{xc}=g^{v}=t$).

Die Fiat-Shamir-Heuristik besteht daraus, Schritt 3 durch einen nicht-interaktiven Zugriff auf ein Zufallsorakel zu ersetzen. In der Praxis wird stattdessen eine kryptographische Hash-Funktion verwendet.

1. Alice will Bob beweisen, dass sie $x$ kennt, den diskreten Logarithmus von $y=g^{x}$ zur Basis $g$.
2. Sie wählt ein $v\in \mathbb {Z} _{q}$ und berechnet $t=g^{v}$.
3. Alice berechnet $c=H(g,y,t)$, mit einer kryptographischen Hashfunktion $H()$.
4. Sie berechnet $r=v-cx$. Der Beweis ist das Paar $(t,r)$. Da $r$ ein Exponent von $g$ ist, ist der Modulus $q-1$.
5. Jeder kann überprüfen, ob $t\equiv g^{r}y^{c}$.

Siehe auch

• Zufallsorakel
• Interaktives Beweissystem