Null-Wissens-Beweis: Abstraktes Beispiel

Also habe ich über ZKP auf Wikipedia gelesen , das abstrakte Beispiel in der Zusammenfassung sieht folgendermaßen aus:

Peggy möchte Victor beweisen, dass sie das Geheimnis einer Tür in einer Höhle kennt, die A und B miteinander verbindet (siehe Abbildung), ohne Victor das geheime Wort preiszugeben.

Peggy nimmt einen zufälligen Eintrag, den Victor nicht kennt

Victor ruft Peggy zu, sie solle den Weg A oder B verlassen (zufällig ausgewählt).

und so folgt, dass sie das geheime Wort kennen muss, um aus dem Weg herauszukommen, den Victor wählt, ohne Victor das geheime Wort zu offenbaren. Victor baut Vertrauen auf, je öfter dies getan wird.

Warum darf Victor jedoch nicht sehen, von welchem Pfad Peggy eintritt? Da dies keine zusätzlichen Informationen über das geheime Wort preisgibt.

Warum kann Victor nicht sehen, in welche Richtung sie eintritt und bittet sie, die 4 Möglichkeiten zu demonstrieren, das heißt:

Betreten Sie von A und verlassen Sie A.
Betreten Sie von A und verlassen Sie B.
Betreten Sie von B und verlassen Sie A.
Geben Sie von B ein und verlassen Sie von B.

algorithms cryptography security authentication Brandon
quelle

Antworten:

Ich glaube, dies wird getan, um zwei Dinge zu veranschaulichen.

(i) Die geringe Wahrscheinlichkeit, dass $P$ eggy ( $P$ Rover) könnte lügen. Wenn sie das Zauberwort wirklich nicht kennt und $V$ ictor ( $V$ erifier) sieht sie Path nehmen $A$ Er bat sie immer, über den Weg zurückzukommen $B$ , also die Wahrscheinlichkeit von $P$ Erfolg beim Betrügen ist $0$ .

Jedoch, $ZKP$ s beinhalten normalerweise eine kleine Chance von $P$ Erfolg beim Betrügen, was durch veranschaulicht wird $V$ den Weg nicht sehen $P$ braucht, um zur magischen Tür zu gelangen.

(ii) $V$ lernt das Geheimnis nicht. Wenn $V$ steht an der Kreuzung der Wege $A$ und $B$ während $P$ geht zur magischen Tür, um ihr magisches Wort zu sagen, für das es denkbar sein könnte $V$ hören können $P$ ihr geheimes Wort sagen. Nur so kann man das sicherstellen $V$ lernt das Zauberwort nicht, soll für ihn außerhalb der Höhle warten, bis $P$ hat einen Weg gewählt.

Riyil
quelle

(i) Warum dürfen wir nicht die Wahrscheinlichkeit haben, dass P erfolgreich ist, wenn wir auf 0 schummeln? Wäre das nicht ideal? (ii) Er wird das Geheimnis immer noch nicht kennen, er sieht zu, wie sie hineingeht, schreit, welcher Ausgang herauskommt, und beobachtet dann, wie sie geht. (anstatt ihm den Rücken zu kehren, wenn sie hineingeht und sie herauskommen sieht)

Brandon

(i) Sicher, das wäre ideal. Normalerweise ist dies jedoch nicht der Fall

Z K P

$ZKP$ Systeme. (ii) Es ist nur eine Frage der Semantik, er könnte sie das Zauberwort sagen hören, wenn er an der Kreuzung von Pfaden steht

A

$A$ und

B

$B$ .

P

$P$ will das verhindern und fragt

V

$V$ außerhalb der Höhle warten.

Riyil

(i) Ja, es scheint, dass ZKP-Systeme normalerweise auf kleinen Wahrscheinlichkeiten basieren, aber dies könnte daran liegen, dass es schwierig ist, ein perfektes Null-Wissens-Szenario wie das von mir angegebene zu entwickeln, anstatt selbst eine Eigenschaft von ZKP zu sein. Immerhin verlangt ZKP, dass es vollständig, solide und ohne Wissen ist, aber nichts damit zu tun hat, dass P beim Betrügen erfolgreich ist? es sei denn, mein Verständnis von ZKP ist falsch.

Brandon

(ii) Aber V könnte aus der Ferne zuschauen und dann schreien, ob er von A oder B kommen soll. Wenn Sie sagen wollen, dass V aus dieser Entfernung hören kann, können wir sagen, dass V vorgibt, sich umzudrehen, und sich dann vorwärts schleicht Wann ist Peggy in der Höhle und hört zu? Beide Fälle sind gleich wahrscheinlich und ich bin mir nicht sicher, ob der Zweck der Abkehr, wenn Peggy hereinkommt, darin besteht, das geheime Wort versehentlich oder absichtlich zu hören.

Brandon

Der Artikel versucht die Eigenschaft zu veranschaulichen, dass ein Null-Wissensnachweis nur den Betrachter überzeugt. Mit anderen Worten, der Beobachter könnte später niemanden mehr überzeugen.

Dies geschieht unter Berücksichtigung des Vorhandenseins einer Münze und einer Videokamera:

Beachten Sie außerdem, dass dieses Protokoll seine wissensfreie Eigenschaft verliert, wenn Victor seine A und B durch Umwerfen einer Münze vor der Kamera auswählt. Der Münzwurf vor der Kamera würde wahrscheinlich jeden überzeugen, der sich die Aufnahme später ansieht.

Genau wie bei diesem Münzwurf würde die Aufzeichnung von Peggy, die Seite A betritt und Seite B verlässt, jeden Dritten überzeugen, der sich der Anwesenheit der magischen Tür bewusst ist. Dies würde es eher als deterministischen als als als probabilistischen Beweis betrachten. Dies veranschaulicht weiter Riyils zweiten Punkt: Es gibt eine Wahrscheinlichkeit ungleich Null $P$ so dass der Prüfer betrogen hat.

AlexMayle
quelle