Lexikon der Mathematik: Null-Wissen-Beweis
Methode des Nachweisens des Vorhandenseins von bestimmtem Wissen, ohne das Wissen selbst preiszugeben.
Solche Beweise werden meist in Form eines Frage-Antwort-Protokolls bei Authentifikationen von Personen benutzt, um zu verhindern, daß danach die dabei verwendeten persönlichen Informationen, wie etwa ein Paßwort, von anderen miß-braucht werden können.
So läßt sich, beispielsweise wie im Fiat-Shamir-Protokoll, leicht (mit beliebig kleiner Fehlerrate) feststellen, ob jemand die Lösung einer quadratischen Kongruenz x2 ≡ a ≢ 0 mod n kennt, wobei n = pq das Produkt zweier großer unbekannter Primzahlen ist. (Die Komplexität der Bestimmung aller vier Lösungen ist äquivalent zur Zerlegung von n in die beiden Faktoren: Weil \({x}_{1}^{2}\equiv {x}_{2}^{2}\) mod n für zwei Lösungen x1 ≢±x2 mod n gilt, ist
Durch Bestimmung des größten gemeinsamen Teilers ggT(pq, x1 − x2) findet man schnell einen Faktor von n.)
Alice wählt zufällig eine Zahl 1 < r< n und sendet
an Bob, der prüfen will, ob Alice eine Lösung x0 der quadratischen Kongruenz x2 ≡ a mod n kennt. Bob entscheidet sich zufällig für eine der beiden folgenden Möglichkeiten und fordert Alice auf, entweder die Zahl r oder die Zahl rx0 mod n zu senden. Bob prüft dann entsprechend, ob die ihm gesandte Zahl c2 die Bedingung \({c}_{2}^{2}\equiv {c}_{1}\) mod n oder \({c}_{2}^{2}\equiv {c}_{1}a\) mod n erfüllt. Ohne Wissen über die Lö-sung x0 zu erhalten, kann Bob diese Prüfung vornehmen.
Alice ist mit Kenntnis einer Lösung in der Lage, auf beide Anforderungen von Bob mit dem passenden Wert zu antworten. Kennt sie jedoch die Lösung nicht, sinkt nach k Runden die Wahrscheinlichkeit eines Betruges durch Alice auf 1/2k.
Bob erhält aus diesem Protokoll keine zusätzlichen Informationen, er kann sich solche Protokolle auch allein, ohne Mithilfe von Alice, beliebig erstellen. Diese wären nicht einmal von echten Protokollen zu unterscheiden.
Jedes NP-vollständige Problem kann als Grundlage eines Null-Wissen-Beweises dienen. Alice kann dann mit beliebiger Wahrscheinlichkeit beweisen, daß sie eine Lösung des Problems kennt, ohne diese zu verraten.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.