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  abhängt, wird die Sicherheit des Algorithmus kompromittiert, da ein böswilliger Beweiser den Wert  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.

 Alice will Bob beweisen, dass sie  kennt, den diskreten Logarithmus von  zur Basis .
 Sie wählt ein , berechnet  und schickt  an Bob.
 Bob wählt ein zufälliges  und schickt es an Alice.
 Alice berechnet  und schickt  an Bob.
 Bob überprüft, ob  (diese Aussage ist wahr, da ).

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.

 Alice will Bob beweisen, dass sie  kennt, den diskreten Logarithmus von  zur Basis .
 Sie wählt ein  und berechnet .
 Alice berechnet , mit einer kryptographischen Hashfunktion .
 Sie berechnet . Der Beweis ist das Paar . Da  ein Exponent von  ist, ist der Modulus .
 Jeder kann überprüfen, ob .

Siehe auch 

 Zufallsorakel
 Interaktives Beweissystem

Einzelnachweise 

Kryptologie