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 x² ≡ 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 x₁ ≢±x₂ 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, x₁ − x₂) 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 x₀ der quadratischen Kongruenz x² ≡ 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 rx₀ mod n zu senden. Bob prüft dann entsprechend, ob die ihm gesandte Zahl c₂ 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 x₀ 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/2^k.

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.