Direkt zum Inhalt

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 x2a ≢ 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 \begin{eqnarray}pq|({x}_{1}-{x}_{2})(x{1}_{}+{x}_{2}).\end{eqnarray}

Durch Bestimmung des größten gemeinsamen Teilers ggT(pq, x1x2) findet man schnell einen Faktor von n.)

Alice wählt zufällig eine Zahl 1 < r< n und sendet \begin{eqnarray}{c}_{1}={r}^{2}\,\mathrm{mod}\,n\end{eqnarray}

an Bob, der prüfen will, ob Alice eine Lösung x0 der quadratischen Kongruenz x2a 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.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.