Zero-Knowledge-Beweis

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein Zero-Knowledge-Beweis (auch kenntnisfreier Beweis) oder Zero-Knowledge-Protokoll (auch kenntnisfreies Protokoll) ist ein Protokoll aus dem Bereich der Kryptografie. Bei einem Zero-Knowledge-Protokoll kommunizieren zwei Parteien (der Beweiser und der Verifizierer) miteinander. Der Beweiser überzeugt dabei den Verifizierer mit einer gewissen Wahrscheinlichkeit davon, dass er ein Geheimnis kennt, ohne dabei Informationen über das Geheimnis selbst bekannt zu geben. Ein bekanntes Verfahren ist das Feige-Fiat-Shamir-Protokoll.

Angelehnt an den Zero-Knowledge-Beweis bezeichnet Zero Knowledge im Cloud Computing eine Selbstbeschränkung der Anbieter, um keinen Einblick in die gespeicherten Dateien der Nutzer erhalten zu können.

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Zero-Knowledge-Protokolle dienen u. a. der Authentifizierung. In der Praxis werden sie jedoch kaum verwendet, da sie in der Regel für ein ausreichendes Sicherheitsniveau ein hohes Maß an Interaktion, d. h. den Austausch vieler Nachrichten, erfordern. Die in praktischen Anwendungen eingesetzten und standardisierten Authentifizierungsprotokolle basieren stattdessen auf digitalen Signaturen. Allerdings gibt es auch Konstruktionen, welche bestimmte Zero-Knowledge Protokolle in nicht-interaktive Varianten überführen.

Zero-Knowledge-Protokolle stellen eine Erweiterung von interaktiven Beweissystemen dar. Zu den Bedingungen Vollständigkeit und Zuverlässigkeit der interaktiven Beweissysteme tritt noch die Zero-Knowledge-Eigenschaft, die dafür sorgt, dass der Verifizierer keine Information über das Geheimnis erlangt.

Bei einem Zero-Knowledge-Protokoll soll immer gezeigt werden, dass eine Eingabe einer formalen Sprache angehört. Dazu muss ein Zero-Knowledge-Protokoll drei Bedingungen erfüllen:

Vollständigkeit
Ist die Eingabe ein Element der Sprache , dann soll ein Verifizierer nach Ablauf des Protokolls fast immer akzeptieren.
Zuverlässigkeit
Ist die Eingabe kein Element der Sprache , also der Beweiser unehrlich, dann soll der Verifizierer nach Ablauf des Protokolls ablehnen. Dabei ist jedoch eine geringe Fehlerwahrscheinlichkeit erlaubt.
Zero-Knowledge-Eigenschaft
Aus der Interaktion zwischen dem Beweiser und dem Verifizierer darf nicht mehr Wissen als die (Un-)Gültigkeit der zu beweisenden Aussage gewonnen werden. Ein Dritter, der die Interaktion zwischen Beweiser und Verifizierer verfolgt, erfährt nicht einmal, ob der Beweiser überhaupt das Geheimnis kennt (oder die Interaktion zwischen B und V abgesprochen war).

Klassisches Beispiel[Bearbeiten | Quelltext bearbeiten]

Das nachfolgende anschauliche Beispiel für ein Zero-Knowledge-Protokoll wurde von Jean-Jacques Quisquater et al. (s. Literatur) entworfen.

Zero knowledge cave 1.svg

Peggy möchte Viktor beweisen, dass sie ein Geheimnis kennt, mit dem sich eine Tür in einer Höhle öffnen lässt, ohne dass sie vor seinen Augen die Tür öffnet (und somit ihm und Dritten zeigt, wie die Tür zu öffnen ist).

Viktor steht bei 4 und sieht Peggy in die Höhle gehen. Er sieht nicht, ob Peggy nach 1 oder 2 geht. Dann geht Viktor zu 3 und verlangt von Peggy, dass sie auf der von ihm festgelegten Seite aus der Höhle kommt. Wenn Peggy nicht auf der richtigen Seite steht, muss sie dafür die rote Tür öffnen. Kann Peggy die Tür öffnen, kann sie stets auf der von Viktor verlangten Seite herauskommen. Kann sie die Tür nicht öffnen, muss sie in 50 % der Fälle auf der falschen Seite zurückkommen.

Kommt Peggy nach n Versuchen jedes Mal auf der von Viktor verlangten Seite aus der Höhle, kann Viktor mit einer Wahrscheinlichkeit von davon ausgehen, dass Peggy das Geheimnis der Tür kennt, hat aber dennoch kein neues Wissen über die Tür erlangt, etwa wie genau sie zu öffnet ist, ob sie nur von einer Seite zu öffnen ist etc.

Dieser Beweis funktioniert allerdings nur gegenüber Viktor: Beobachtet ein Dritter den Vorgang, ist er nicht davon überzeugt, dass Peggy das Geheimnis der Tür kennt, da sich Viktor und Peggy abgesprochen haben könnten, welche Seite Viktor in jedem der Durchgänge verlangen wird.

Beispiel für ein Zero-Knowledge-Protokoll[Bearbeiten | Quelltext bearbeiten]

Ein Zero-Knowledge-Protokoll mit ISOGRAPH

Eine Zero-Knowledge-Authentifizierung zwischen zwei Instanzen kann mit Hilfe des Graphenisomorphieproblems stattfinden. Dazu muss vom Beweiser zunächst einmalig ein öffentliches Schlüsselpaar erstellt werden:

  • Der Beweiser erzeugt einen sehr großen Graphen .
  • nummeriert mit einer zufällig und gleichförmig gewählten Permutationsfunktion um. Der resultierende Graph sei also .
  • Das Paar wird veröffentlicht, die Permutation hält geheim.

Angenommen, eine Person, genannt „Verifizierer“, möchte die Identität von überprüfen, d. h. feststellen, ob tatsächlich im Besitz des zum öffentlichen Schlüssel gehörigen privaten Schlüssels ist. Dann kann diese Tatsache mit Hilfe des nachfolgenden Zero-Knowledge-Protokolls beweisen, ohne dem Verifizierer oder einer dritten Person den privaten Schlüssel mitzuteilen:

  1. Der Beweiser wählt zufällig ein . Außerdem wird der Graph durch die zufällig gewählte Permutationsfunktion umnummeriert. Der resultierende Graph sei . sendet schließlich an den Verifizierer . In diesem Schritt legt sich der Beweiser also auf einen der Graphen fest (Commitment bzw. Witness).
  2. Der Verifizierer empfängt den Graphen und wählt zufällig ein . Dann fordert er auf, ihm eine Permutation mit der Eigenschaft zu senden (Challenge).
  3. Nun muss zwischen drei Fällen unterschieden werden:
    schickt die entsprechend konstruierte Permutation an zurück (Response).
  4. empfängt das von gesendete und prüft, ob wirklich gilt.

Wir betrachten nun die drei notwendigen Bedingungen für ein Zero-Knowledge Protokoll:

  • Das obige Protokoll ist offensichtlich vollständig, weil gerade so konstruiert wird, dass es die geforderte Gleichung erfüllt.
  • Ein unehrlicher Beweiser bzw. eine dritte Person, die sich als ausgeben möchte, kann ohne Kenntnis von den Verifizierer nur mit einer Wahrscheinlichkeit von 0,5 (durch richtiges Raten des Wertes im ersten Schritt) überzeugen. Falls das Protokoll hinreichend oft wiederholt wird und unter der Annahme, dass die Bestimmung von aus schwer ist, ist das Protokoll also zuverlässig.
  • Die Kommunikation zwischen Beweiser und Verifizierer in einer Runde (Schritt 1 bis 4) ist von der Form . Erzeugt nun ein Simulator zufällig und gleichförmig und und berechnet damit den Graphen , dann ist die resultierende Wahrscheinlichkeitsverteilung identisch mit der Verteilung, welche durch die echten Protokollinstanzen impliziert wird. Folglich kann kein geheimes Wissen (hier die Permutation ) übertragen worden sein (Zero-Knowledge).

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Jean-Jacques Quisquater, Louis Guillou: How to explain zero-knowledge protocols to your children. Advances in Cryptology - CRYPTO '89, Lecture Notes in Computer Science 435, pp. 628-631, 1990. (PDF)
    Kommentar: Äußerst unterhaltsame und theoriearme Einführung anhand eines mittlerweile klassischen Beispiels.
  • Ivan Damgard, Jesper Buus Nielsen: Commitment Schemes and Zero-Knowledge Protocols, 2008, PDF
  • Albrecht Beutelspacher, Jörg Schwenk, Klaus-Dieter Wolfenstetter: Moderne Verfahren der Kryptographie, 7. Auflage, S. 43ff, 2010, ISBN 978-3-8348-1228-5

Weblinks[Bearbeiten | Quelltext bearbeiten]