Preisgekröntes Nichtwissen

19 September 2013 by Benjamin Hiller, posted in Computer Science, Deutscher Blog

„Pssst! Ich weiß etwas, das Du nicht weißt und ich verrate es Dir nicht. Glaubst Du mir?“ – „Wieso sollte ich? Davon musst Du mich erstmal überzeugen.“ Dieses fiktive Gespräch klingt absurd, aber dahinter steckt ein Problem, für dessen Aufwerfen und Lösen Leute die angesehensten Informatik-Preise bekommen haben. Am ersten Heidelberg Laureate Forum nehmen sogar drei Preisträger teil, die an diesem Thema arbeiteten: Shafi Goldwasser, Silvio Micali und Avi Wigderson.

Shafrira Goldwasser
Foto © Klaus Tschira Stiftung / Peter Badge

 

 

 

Silvio Micali
Foto © Klaus Tschira Stiftung / Peter Badge

Avi Wigderson
Foto © Klaus Tschira Stiftung / Peter Badge

Von der Kenntnis eines Geheimnisses zu überzeugen, ohne irgend etwas darüber preiszugeben – dieses Problem und dessen elegante Lösung habe ich während des Studiums in einem Seminar kennengelernt. Es hat mich einige Mühe gekostet, die mathematischen Details zu verstehen, aber die Idee hat mich sehr fasziniert. Der Trick ist, sich den Zufall zu nutze zu machen, um kein „Wissen“ zu offenbaren. Und – ganz wichtig! –  eine clevere Definition von „kein Wissen offenbaren“.

Um das besser verstehen zu können, geben wir den beiden fiktiven Gesprächspartnern Namen: Peggy kennt ein Geheimnis und Victor möchte sich davon überzeugen, dass sie es kennt. Allerdings soll Victor weder das Geheimnis noch Teile davon erfahren. Beide suchen also ein Kommunikations-Verfahren, das sicher stellt, dass keiner den anderen betrügt. Mehr noch: Selbst wenn sich einer der beiden nicht an die Regeln des Verfahrens hält, soll derjenige nicht in der Lage sein, den anderen zu betrügen. Diese Bedingung sorgt dafür, dass Dritte das Verfahren nicht zu ihrem Vorteil nutzen können.

In einem solchen Kommunikations-Verfahren stellt Victor Peggy Fragen, die sie beantworten muss. Diese Fragen müssen so gewählt sein, dass Peggy sie nur mit Kenntnis des Geheimnisses richtig beantworten kann. Und Victor muss diese Richtigkeit überprüfen können, ohne selbst das Geheimnis zu kennen. Da Victor und Peggy alle Details des Verfahrens kennen, müssen Victors Fragen unvorhersehbar sein. Sonst kann Peggy (oder jemand, der sich als Peggy ausgibt) die Fragen von Victor vorhersagen und sich Antworten überlegen, die zueinander passen und Victors Tests standhalten. Die Lösung für dieses Problem ist, dass Victor zufällige Fragen stellt und Peggy nur glaubt, wenn sie alle richtig beantwortet. Stellt Victor genügend Fragen, ist es sehr unwahrscheinlich, dass Peggy den Test besteht, ohne das Geheimnis zu kennen.

Dennoch könnte Victor durch gezieltes Fragen aus Peggies Antworten etwas über das Geheimnis erfahren. Wie kann Peggy sicher sein, dass egal wie Victor (oder jemand, der sich als Victor ausgibt) seine Fragen stellt, er keine Informationen über das Geheimnis bekommt? Hier geht es also um die mathematisch exakte Erfassung von „Nichtwissen“. Die Lösung ist für mich der eigentliche Clou: Victor lernt genau dann nichts aus seinen Fragen, wenn er Peggies Antworten nicht von solchen Antworten unterscheiden kann, die er selbst ohne Kommunikation mit Peggy erzeugen kann.

Soweit ist das alles noch ziemlich abstrakt und vage. Eigentlich hatte ich vor, mir ein schönes Beispiel auszudenken, um dies alles ganz konkret zu erklären. Bei meinen Recherchen zur Auffrischung meiner Studienkenntnisse habe ich aber bereits das perfekte Beispiel (in Englisch) gefunden, auf das ich jetzt einfach zurückgreife.

Also: Peggy und Victor kennen eine Höhle mit zwei Eingängen A und B, die auf den ersten Blick Sackgassen sind. Peggy behauptet nun, ein Geheimwort zu kennen, das eine versteckte Tür öffnet und damit eine Verbindung der beiden Eingänge herstellt. Sie möchte dies Victor beweisen, ohne das Geheimwort zu verraten. Dazu könnte Peggy, von Victor beobachtet, auf der einen Seite hinein und auf der anderen Seite wieder hinaus gehen. Victor ist nun sicher, dass Peggy das Geheimwort kennt. Außerdem gewinnt er zusätzliches Wissen: Wenn er die Ereignisse „Peggy geht zu Eingang A hinein; Victor wünscht, dass sie zu Eingang B herauskommt; Peggy kommt zu Eingang B heraus“ fälschungssicher aufzeichnet, kann er anderen nachweisen, dass Peggy das Geheimwort kennt. Diese Aufzeichnung kann er nicht ohne Peggy erstellen, da er dafür wissen muss, mit welchem Eingang Peggy die Höhle betritt.

Die Höhle mit dem Geheimgang. Victor wartet draußen, während Peggy in der Höhle ist.
Bild Wikimedia CC-BY-2.5 Illustrator: Dake

Peggy möchte ausschließlich Victor überzeugen, ohne dass dieser etwas weitergeben kann. Dazu schlägt sie folgendes Verfahren vor: Sie verschwindet zufällig in einem der Eingänge, wobei Victor nicht sieht, in welchem. Victor wählt zufällig einen Eingang, aus dem Peggy wieder herauskommen soll. Da Peggy den von Victor gewählten Eingang nicht kennt und auch nicht beeinflussen kann, kann sie nur sicher aus dem gewünschten Eingang herauskommen, wenn sie die Verbindung der beiden Eingänge nutzt. Victor kann also prüfen, ob es eine solche Verbindung gibt, ohne sie selbst zu sehen.

Da Peggy immerhin eine 50%-Chance hat, den von Victor gewählten Eingang zu erraten, wiederholt Victor dieses Spiel z.B. 20-mal. Wenn es keine Verbindung gibt, hat Peggy dann eine Chance von weniger als eins zu einer Million, immer aus dem richtigen Eingang herauszukommen. Eine „beweisende“ Aufzeichnung hält dann Wiederholungen der Ereignisse „Victor wünscht sich einen Ausgang; Peggy kommt aus diesem Ausgang heraus“ fest. Entscheidend ist, dass Victor nicht aufzeichnen kann, durch welchen Eingang Peggy die Höhle betritt. Daher kann er solche Aufzeichnungen auch ohne Peggy erzeugen. Er ist anhand seiner Aufzeichnung überzeugt, weil er (und nur er!) zusätzlich weiß, dass er sich die Ausgänge wirklich zufällig gewünscht hat. Jeder andere sieht nur, dass die Ausgänge übereinstimmen. Das allein beweist nichts, da sich Peggy und Victor auch abgesprochen haben könnten, um eine solche Aufzeichnung zu fälschen.

Das ist genau die Formalisierung von „kein zusätzliches Wissen“, die ich so genial finde: Victor könnte sich die Antworten von Peggy (richtiger Ausgang) auch aus seinen Fragen (vorgegebener Ausgang) selbst erzeugen. Wichtig ist, dass dies völlig unabhängig davon ist, ob Victor seine Fragen zufällig oder nach irgendeinem System erzeugt. Selbst bei einem noch so ausgeklügeltem Fragesystem folgen die Aufzeichnungen dem obigen Schema und sind wegen ihrer Vorhersagbarkeit keine neue Information für Victor.

Ist diese Spielerei wirklich einen oder gar mehrere renommierte Informatik-Preise wert? Ja, denn die entsprechende Theorie hat eine Reihe interessanter Konsequenzen. Die offensichtlichste ist die Anwendung, die das Problem motiviert hat: Authentifizierung. Dabei will jemand (Peggy) gegenüber einem System (Victor) nachweisen, dass sie zugangsberechtigt ist. Allerdings sollen die Zugangsdaten nicht preisgegeben werden, damit diese nicht von Dritten missbraucht werden können. Bei den gegenwärtig im Internet verwendeten Authentifizierungsverfahren ist das nicht der Fall: Sie müssen Ihre Kreditkartennummer oder TAN preisgeben und jeder andere kann damit genau wie Sie (und mit Ihrem Geld!) bezahlen, sobald er die Zugangsdaten abgefangen hat. Bei den beschriebenen sogenannten Zero-Knowledge-Beweissystemen ist das anders. Hier kann niemand aus der abgehörten Kommunikation, ja noch nicht einmal aus einer manipulierten Verbindung, irgendetwas über die Zugangsdaten lernen. Die anderen Anwendungen sind vor allem theoretischer Natur, z.B. für die Komplexitätstheorie. Aber das ist ein anderer Blogbeitrag.


3 Responses to “Preisgekröntes Nichtwissen”

  1. Benjamin Reply | Permalink

    Sehr interessante Theorie, von der ich ehrlich gesagt davor noch nie gehört habe. Sehr gut gefällt mir, wie einfach dieses komplexe Thema in diesem Blogbeitrag beschrieben wurde!

  2. John Doe Reply | Permalink

    Mit PKI wird die Anforderung (beweisen, dass ich im Besitz des private key bin, ohne diesen zu Offenbaren) doch schon lange praktiziert. Und hiermit geht es ganz ohne "Spielerei". Was ist denn bei der Authentifizierung auf Basis von ZKP der Mehrwert gegenüber PKI?

    • Benjamin Hiller Reply | Permalink

      Bei Public-Key-Kryptographie erfährt der Überprüfer der Authentifizierung per Definition den öffentlichen Schlüssel. Im Prinzip ist es denkbar, dass aus dem öffentlichen Schlüssel und dem verwendeten Verschlüsselungsverfahren Rückschlüsse auf den privaten Schlüssel gezogen werden können. Das ist bei Zero-Knowledge-Systemen wie beschrieben grundsätzlich anders, da der Überprüfer über den Schlüssel (also das Geheimnis) nichts erfährt.

Leave a Reply


six − = 0