Fiat-Shamir-Protokoll

Das Fiat-Shamir-Protokoll ist ein Protokoll aus dem Gebiet der Kryptografie, mit dem man sich jemandem gegenüber authentisieren kann. Dazu zeigt man, dass man eine Quadratwurzel (privater Schlüssel) einer vorher veröffentlichten Quadratzahl (öffentlicher Schlüssel) kennt. Bei dem Verfahren wird nur ein einziges Bit des privaten Schlüssels preisgegeben, nämlich das Vorzeichen. Eine Variante ist das Feige-Fiat-Shamir-Protokoll, bei dem keine Information über den privaten Schlüssel preisgegeben wird. Man spricht deswegen von einem Zero-Knowledge-Protokoll. Insbesondere ist das Protokoll perfekt zero-knowledge. Das heißt, es gibt einen Simulations-Algorithmus, der in polynomieller Zeit eine Mitschrift erzeugt, die von einer echten Interaktion nicht zu unterscheiden ist.

Das Fiat-Shamir-Protokoll wurde im Jahr 1986 von Amos Fiat und Adi Shamir vorgestellt. An der Entwicklung des Feige-Fiat-Shamir-Protokolls war auch Uriel Feige beteiligt.

Das Verfahren arbeitet interaktiv, das heißt, es finden mehrere Runden zwischen Geheimnisträger und dem Prüfer statt. In jeder Runde kann die Kenntnis der Zahl zu 50 % bewiesen werden. Nach zwei Runden bleibt eine Unsicherheit von 25 %, nach der dritten Runde nur noch 12,5 % usw. Nach ${\displaystyle n}$ Runden beträgt die Unsicherheit ${\displaystyle 2^{-n}}$.

Die Sicherheit des Fiat-Shamir-Protokolls beruht auf der Schwierigkeit, Quadratwurzeln im Restklassenring ${\displaystyle \mathbb {Z} _{n}}$ zu berechnen. Diese Berechnung ist genauso schwierig, wie die Zahl ${\displaystyle n=p\cdot q}$ (${\displaystyle p}$ und ${\displaystyle q}$ sind Primzahlen) zu faktorisieren und damit praktisch nicht durchführbar, wenn die Zahlen hinreichend groß sind.