Ich habe dieses Beispiel während einer der Gastvorträge in meiner Graduiertenschule gehört. Ich denke, es ist einfach genug, da ich es selbst oft benutzt habe, um Leuten mit fast null Kenntnissen über Krypto / Mathematik ZKP zu erklären.

Nehmen wir an, ich möchte Sie davon überzeugen, dass ich eine Supermacht habe, um innerhalb weniger Sekunden die genaue Anzahl Blätter eines Baumes zu zählen. Ich möchte Sie überzeugen, ohne diese genaue Zahl preiszugeben und ohne zu verraten, wie meine Supermacht funktioniert. Ich kann ein einfaches Protokoll erstellen:

Ich werde meine Augen schließen und Ihnen die Wahl geben, ein Blatt von diesem Baum abzuziehen. Da es nur eine Wahl ist, werden Sie es entweder abziehen oder Sie werden es nicht tun. Ich habe keine andere Möglichkeit zu wissen, ob Sie es getan haben oder nicht, als die Blätter mit meiner Supermacht schnell wieder zu zählen. Wenn ich mir jetzt den Baum anschaue, wirst du mich fragen, ob du ihn tatsächlich abgezogen hast oder nicht.

Wenn ich dir eine falsche Antwort gebe, wirst du sofort wissen, dass meine Supermacht ist falsch und mein Wissen auch. Wenn meine Antwort jedoch richtig ist, könnten Sie denken, dass ich gerade Glück hatte. In diesem Fall können wir die obigen Schritte wiederholen. Wir können diese Schritte bis zu dem Punkt wiederholen, an dem Sie mit der Tatsache zufrieden sind, dass ich tatsächlich die Supermacht besitze und die genaue Anzahl kenne.

Die beste Demonstration von wissensfreien Beweisen, auf die ich gestoßen bin, ist "Angewandte Kinderkryptographie oder wie Sie Ihre Kinder davon überzeugen können, dass Sie nicht betrügen" von Moni Naor, Yael Naor und Omer Reingold. Sie untersuchen ein einfaches, aber reales kryptografisches Problem: Wie kann man Menschen davon überzeugen, dass man die Lösung für ein Wo ist Waldo -Puzzlespiel kennt, ohne Informationen über seinen Standort preiszugeben. Wie der Titel des Papiers andeutet, soll die Erklärung so einfach sein, dass ein Kind sie verstehen kann.

Die gute Antwort lautet wie folgt: Der bemerkenswerte Fall ist die Metapher „Ali Babas Höhle“, mit der die grundlegenden Mechanismen eines wissensfreien Beweises veranschaulicht werden: Der Prüfer muss den Prüfer über ein interaktives Protokoll von seinem Wissen überzeugen. Gleichzeitig darf ein gelegentlicher Betrachter keine Informationen über das geheime Wissen erhalten.

• Aus dem Buch: Algorithmen mit Metaphern erklären, Michal Forišek · Monika Steinová, 2013
• Die Referenz des Buches ist dieser Artikel für 1990: Wie Sie Ihren Kindern Zero-Knowledge-Protokolle erklären.

Ein großes Lob für die RSA-Mischanalogie. Ein großartiger Fund.

Das zkp hängt hauptsächlich von einer Operation ab, wobei die überprüfende Partei einige Begriffe diktieren kann, die die gegnerische Partei verwenden kann. Dies hängt natürlich sehr davon ab, welche Frage überhaupt gestellt wird.

Die Kombination aus Peggy-Victor-Geheimtür würde nicht funktionieren, wenn die Frage so formuliert würde, dass Victor wissen möchte, ob Peggy nach links gelangen kann / rechte Seite des Tunnels im Gegensatz zur Kenntnis des Passworts, um durch die Tür zu gelangen.

Die Frage im wirklichen Leben könnte also möglicherweise für Kinder wie folgt zusammengefasst werden:

Ich würde Ich möchte gerne wissen, ob Sie verstehen, wie A / B / C funktioniert, oder ob Sie mit einem Wissen vertraut sind, das besagt, dass Sie es tun. Der Beweis dafür könnte eine Form von Test sein, die möglicherweise zu einer wörtlichen Darstellung der akzeptierten Antwort oder einem physischen Ausdruck des Wissens führen könnte (dh wissen Sie, wie der Verbrennungsmotor funktioniert, und ja, hier ist die Wohnung 8 mit zwei Kohlenhydraten, die ich mit bloßen Händen mit dem aus den Tiefen einer Mine gehauenen Stahl irgendwo im Norden Russlands gemacht habe). Das Knifflige an ZKP, und dies erstreckt sich auch auf viele andere Bereiche, ist, ob es bei Vorlage des Beweises an sich die Art und Weise offenbart, wie die Antwort abgeleitet werden kann.

Und es scheint im wirklichen Leben, dass sich dies in der Zeit niederschlägt, die die überprüfende Partei benötigt, um den Beweis rückzuentwickeln, um die darin enthaltenen Machenschaften zu bestimmen. Ich behaupte also, dass es bei ZKP auch darum geht, diese Zeit auf ein Maß zu erhöhen, bei dem es keinen Sinn macht, dies herauszufinden.

Und damit können Sie dies auf eine ganze Reihe von Beispielen aus der Praxis anwenden.

Angenommen, es gibt zwei Arten von Getränken, von denen allgemein angenommen wird, dass sie gleich, aber in unterschiedlichen Verpackungen sind. Aber wenn man weiß, dass sie gleich sind, versucht man, einen Test zu finden, um zwischen den beiden zu unterscheiden. Als nächstes möchte A B davon überzeugen, dass zwei Getränke nicht gleich sind.

a) Ein trivialer Weg, um zu beweisen, dass A die Details ihres Tests an B sendet und B den Test durchführen lässt. b) Angenommen, A möchte nichts über den durchgeführten Test preisgeben. Dann könnte A B immer noch mit dem folgenden Protokoll überzeugen.

Es geht so: B nimmt eine Dose Getränk jeder Marke und wählt zufällig eine Dose aus, gießt etwas Getränk daraus ein (alles privat) und gibt es an A. A testet dann die Probe und teilt B mit, zu welcher Marke die Probe gehört. Sie wiederholen diesen Vorgang mehrmals. Wenn A jedes Mal richtig antwortet, akzeptiert B die Behauptung, dass die Getränke nicht identisch sind.

In diesem Protokoll erstens, wenn die Getränke unterschiedlich sind und A einen zuverlässigen Test hat, um zwischen ihnen zu unterscheiden A kann B immer überzeugen. Wenn andererseits die Getränke aus beiden Dosen identisch sind, kann A sie nicht unterscheiden.