Proofs, Arguments, and Zero-Knowledge
Diese Monographie befasst sich mit verifizierbarem Rechnen (VC). VC bezieht sich auf kryptographische Protokolle, die als interaktive Beweise (IPs) bezeichnet werden, und auf Argumente, die es einem Beweiser ermöglichen, einem Verifizierer zu garantieren, dass der Beweiser eine angeforderte Berechnung korrekt durchgeführt hat. Diese Monographie behandelt verschiedene Begriffe von mathematischen Beweisen und ihre Anwendungen in der Informatik und Kryptographie. Informell verstehen wir unter einem Beweis alles, was jemanden davon überzeugt, dass eine Aussage wahr ist, und ein "Beweissystem" ist jedes Verfahren, das entscheidet, was ein überzeugender Beweis ist und was nicht.
Die in den 1980er Jahren eingeführten IPs und Argumente stellten eine bedeutende konzeptionelle Erweiterung dessen dar, was einen "Beweis" für die Richtigkeit einer Aussage ausmacht. Traditionell ist ein Beweis ein statisches Objekt, das einfach Schritt für Schritt auf seine Korrektheit überprüft werden kann. Im Gegensatz dazu ermöglichen IPs eine Interaktion zwischen Prover und Verifier sowie eine winzige, aber von Null verschiedene Wahrscheinlichkeit, dass ein ungültiger Beweis die Überprüfung besteht. Argumente (aber nicht IPs) lassen sogar "Beweise" für falsche Aussagen zu, solange diese "Beweise" nur mit exorbitanter Rechenleistung gefunden werden können. Bis zu einem gewissen Grad ahmen diese Begriffe die persönlichen Interaktionen nach, die Mathematiker nutzen, um sich gegenseitig davon zu überzeugen, dass eine Behauptung wahr ist, ohne den mühsamen Prozess des Aufschreibens und Überprüfens eines traditionellen statischen Beweises durchlaufen zu müssen.
Berühmte theoretische Ergebnisse aus den 1980er und 1990er Jahren, wie IP = PSPACE und MIP = NEXP, haben gezeigt, dass im Prinzip auch überraschend komplizierte Aussagen effizient überprüft werden können. Darüber hinaus kann im Prinzip jedes Argument in ein Null-Wissen-Argument umgewandelt werden, was bedeutet, dass Beweise keine anderen Informationen als ihre eigene Gültigkeit preisgeben. Null-Wissen-Argumente finden in der Kryptographie eine Vielzahl von Anwendungen.
In den letzten zehn Jahren haben allgemeine Null-Wissen-Argumente den Sprung von der Theorie zur Praxis geschafft. Dies hat neue Türen bei der Entwicklung kryptographischer Systeme geöffnet und zusätzliche Erkenntnisse über die Leistungsfähigkeit von IPs und Argumenten (mit oder ohne Nullwissen) gebracht. Inzwischen gibt es nicht weniger als fünf vielversprechende Ansätze für den Entwurf effizienter, allgemeiner Null-Wissen-Argumente. Die vorliegende Monographie behandelt diese Ansätze auf einheitliche Weise und betont die Gemeinsamkeiten zwischen ihnen.
| ISBN: | 9781638281245 |
| Autor: | |
| Verlag: | |
| Sprache: | Englisch |
| Einband: | Taschenbuch |
Derzeit verfügbar, auf Lager.
