Erläuterung der wissensfreien Beweise Teil 2: Nicht interaktive wissensfreie Beweise

[ware_item id=33][/ware_item]

Beispiel für nicht interaktive Zero Knowledge Proofs: Sudoku und Spielkarten


In Teil 1 unserer Null-Wissens-Beweis-Reihe haben wir erklärt, wie ein Null-Wissens-Beweis funktionieren kann, wenn der Prüfer und der Prüfer miteinander interagieren.

Ein interaktiver Null-Wissensnachweis hat den Vorteil, dass nur der Prüfer absolut davon überzeugt sein kann, dass der Prüfer über das Wissen verfügt. Dies kann aber auch ein Nachteil sein.

Wenn Umstehende und Beobachter die Behauptung nicht überprüfen können, muss der Prüfer mit jedem Prüfer unabhängig interagieren - was Zeit und Ressourcen kostet.

In Teil 2 werden nicht interaktive wissensfreie Beweise betrachtet.

Nicht interaktive wissensfreie Beweise

Der Grund für nicht interaktive wissensfreie Beweise ist, dass eine große Anzahl von Beobachtern den Beweis effizient überprüfen kann.

Wir müssen nicht immer wissensfreie Beweise nicht interaktiv machen. Oft genug ist es möglich, einen vertrauenswürdigen Prüfer zu finden, der für die Integrität des Beweises bürgt.

Nicht interaktives Beispiel für wissensfreie Beweise: Sudoku und Spielkarten

Sudoku ist ein Spiel mit unterschiedlichen Schwierigkeitsgraden, aber relativ einfachen Regeln. Jede der 9 Zeilen, 9 Spalten und 9 Sektoren (angezeigt durch die dicke schwarze Linie) muss jede Zahl von 1 bis 9 genau einmal enthalten.

Stellen Sie sich vor, dass die Lösung eines Sudoku-Puzzles besonders schwer zu bekommen ist und selbst ein Supercomputer Tage braucht, um sie zu berechnen.

Aber jemand (der Prüfer) behauptet, die Lösung für das Rätsel zu haben und ist bereit, sie zu einem Preis zu verkaufen. Wie können sie nachweisen, dass sie die Lösung haben - ohne sie preiszugeben -, sodass der Prüfer bereit ist, Zahlungen zu leisten?

Der Beweis:

Der Prüfer benötigt insgesamt 27 Spielkarten (jeder Farbe) mit den Nummern 1-9—243.

Jetzt legt der Prüfer drei Karten mit der Nummer, die der richtigen Sudoku-Lösung entspricht, in jede Schachtel. Wenn zum Beispiel die richtige Antwort für das Kästchen 7 ist, legt der Prüfer 3 Spielkarten mit dem Wert 7 hinein.

Auf einem Sudoku-Tisch werden einige Antworten angezeigt. Auf diese beantworteten Kästchen werden die Spielkarten gelegt Gesicht nach oben. Auf die leeren Sudoku-Boxen werden die Karten gelegt mit dem Gesicht nach unten.

Um zu beweisen, dass sich alle verdeckten Karten in der richtigen Position befinden (ohne die Lösung preiszugeben), muss der Prüfer:

  • Nehmen Sie die oberste Karte von jedem Reihe und 9 Stapel machen
  • Nehmen Sie die oberste Karte von jedem Säule und 9 Stapel machen
  • Nehmen Sie die restlichen Karten von jedem Sektor und 9 Stapel machen

Anwendungen für wissensfreie Beweise

Jeder Stapel wird dann gemischt und umgedreht.

Jede Zahl zwischen 1 und 9 muss in jeder Sudoku-Zeile, -Spalte und -Sektor erscheinen. Wenn also jeder Stapel der Karten des Bewerbers (aus den Reihen-, Spalten- und Sektorstapeln) jede Spielkarte mit einem Wert von 1 bis 9 enthält, wissen wir, dass sie die Lösung haben müssen.

Anwendungen für wissensfreie Beweise

Zugegebenermaßen hat das relativ junge Gebiet der wissensfreien Beweise noch nicht die Akzeptanz gefunden, die es verdient. Sie könnten sich jedoch als äußerst wertvoll erweisen.

Viele mathematische Probleme ähneln einem Sudoku-Puzzle (zum Beispiel das Graph Coloring-Problem). Wenn wir das obige Prinzip anwenden und erfolgreich auf eine Vielzahl von Problemen anwenden können, können wir möglicherweise Rechenressourcen und mathematische Probleme effizienter nutzen und handeln. Oder vielleicht mathematische Probleme schneller lösen.

Ein großes Lob an Ronen Gradwohl, Moni Naor, Benny Pinkas und Guy Rothblum

Erläuterung der wissensfreien Beweise Teil 2: Nicht interaktive wissensfreie Beweise
admin Author
Sorry! The Author has not filled his profile.