sb-wettbewerb_kleinDieser Artikel ist Teil des ScienceBlogs Blog-Schreibwettbewerb 2017. Informationen zum Ablauf gibt es hier. Leserinnen und Leser können die Artikel bewerten und bei der Abstimmung einen Preis gewinnen – Details dazu gibt es hier. Eine Übersicht über alle am Bewerb teilnehmenden Artikel gibt es hier. Informationen zu den Autoren der Wettbewerbsartikel finden sich in den jeweiligen Texten.
——————————————————————————————————————
Kryptologie jenseits der Verschlüsselung

von Christian Henrich

Seitdem ich das Buch Geheime Botschaften von Simon Singh gelesen habe, bin ich von der Kryptologie fasziniert. Ich habe am Karlsruher Institut für Technologie (KIT) als Doktorand im Bereich kryptographische Wahlverfahren promoviert und gehöre zu der Arbeitsgruppe, die 2008 mit dem Deutschen IT-Sicherheitspreis für das kryptographische Wahlverfahren Bingo Voting ausgezeichnet wurden.

Die moderne Kryptologie hat viel mehr zu bieten als nur Geheimschriften. Zwei wichtige Werkzeuge der modernen Kryptologie möchte ich hier präsentieren. Commitments legen eine Zahl fest, ohne sie zu verraten. Zero-Knowledge-Beweise überzeugen jemanden von der Korrektheit einer Aussage, ohne irgendetwas anderes zu enthüllen.

Kryptologie lässt die meisten an Geheimschriften und Verschlüsselungsverfahren denken. Und bis weit in das letzte Jahrhundert hinein war das Bild damit auch (fast) vollständig. Inzwischen hat sich die Kryptologie weiterentwickelt und bietet mehr als Verschlüsselungsverfahren, die nur ein Teilgebiet der Kryptologie darstellen. Alle Gebiete nutzen Mathematik, was den interessierten Laien leider oft abschreckt, so dass die moderne Kryptologie nicht die Aufmerksamkeit erhält, die sie meiner Meinung nach verdient. Viele kennen bestimmt digitale Signaturen, die Dokumente gegen unbemerkte Veränderung schützen. Recht bekannt sind noch Kryptowährungen wie Bitcoin.
Wenige kennen jedoch sichere Mehrparteienberechnungen, die in diesem YouTube-Video an einem einfachen Beispiel erklärt werden.
Aber selbst das ist noch nicht alles, was die moderne Kryptologie vermag. Mit diesem Text möchte ich zwei erstaunliche Werkzeuge vorstellen und daran aufzeigen, was die Kryptologie noch zu bieten hat.

Commitments
Als Motivation für die beiden Werkzeuge der modernen Kryptologie schauen wir uns folgendes Problem an: Alice ist Bürgermeisterin einer mittelgroßen Stadt und möchte den Auftrag für den Bau des neuen Rathauses vergeben. Dazu führt sie ein Bieterverfahren durch, bei dem ein Gebot aus einer einzigen Zahl, den Kosten für den Bau, besteht. Für Alice ist natürlich das günstigste das beste Angebot. Die Firmen von Bob, Carol und Dave sind an dem Auftrag interessiert und möchten ein Gebot abgeben. Damit die anderen Interessenten das Gebot nicht erfahren, will jeder sein Gebot verschlüsselt abgeben, so dass nur Alice und ihre Mitarbeiter die Gebote erfahren.

Es gibt jedoch eine Komplikation. Eve ist die Nichte von Dave und arbeitet für Alice in der Abteilung, die den Bauauftrag vergibt. Um einen möglichen Einfluss auf das Bieterverfahren zu verhindern (indem Eve die Gebote der Mitbewerber an Dave verrät) verwendet Alice statt Verschlüsselung ein anderes Werkzeug der Kryptologie, nämlich Commitments.

Ein Commitment, zu deutsch etwa Festlegung, erlaubt es einem Sender, sich bei einem Empfänger auf einen Wert festzulegen, ohne dem Empfänger den Wert mitzuteilen. Ein solches Commitment-Verfahren besitzt zwei Eigenschaften: Es ist verbergend, der Empfänger sieht dem Commitment also nicht an, welcher Wert darin steckt, und es ist verbindlich, der Sender hat sich mit Abgabe des Commitments festgelegt und kann sich nicht nachträglich umentscheiden. Wir schauen uns hier ein konkretes Verfahren an, das zusätzliche Eigenschaften besitzt, die wir später noch brauchen. Das Verfahren trägt den etwas unhandlichen Namen unconditionally hiding discrete logarithm commitment, kurz UHDLC, und wird auch als Pedersen-Commitment bezeichnet.

Da wir die Funktionsweise im Detail verstehen wollen, schauen wir uns das Verfahren an, wie es mit Farben funktionieren würde. Stellen wir uns vor, Alice besitzt einen Farbkasten mit vielen Farben. Von diesen Farben ist ein Teil jedem möglichen Wert eines Gebots zugeordnet. Die übrigen Farben sind nicht zugeordnet. Aus diesen Farben mischt jeder Bieter einen Farbton und gibt diesen als Commitment ab.

So sieht der Farbkasten für unser Beispiel aus. In der oberen Reihe sind alle Farben einem Angebot, also einer Geldsumme, zugeordnet. Die Farben in der unteren Reihe sind nicht zugeordnet.
So sieht der Farbkasten für unser Beispiel aus. In der oberen Reihe sind alle Farben einem Angebot, also einer Geldsumme, zugeordnet. Die Farben in der unteren Reihe sind nicht zugeordnet.

Für die Abgabe seines Gebots erzeugt Bob ein Commitment mit seinem Gebot als Inhalt. Dazu mischt er die Farbe, die seinem Gebot zugeordnet ist, mit ein paar von den nicht zugeordneten Farben. Der Farbe, die Bob dann erhält, sieht man nicht mehr an, welche der zugeordneten Farben er verwendet hat. Wer schon einmal einen Farbton nachmischen wollte, um die fehlende Wand in einem in Pastellgrün gestrichenes Zimmer zu streichen, kann bestätigen, wie schwierig es ist, aus einer Farbe das exakte Mischungsverhältnis der Grundfarben zu bestimmen. Damit ist das Commitment, also die von Bob gemischte Farbe, schon einmal verbergend.

Bob erstellt sein Commitment. Dazu mischt er die Farbe, die seinem Gebot von 1,2 Mio. EUR zugeordnet ist, mit drei nicht zugeordneten Farben mischt.
Bob erstellt sein Commitment. Dazu mischt er die Farbe, die seinem Gebot von 1,2 Mio. EUR zugeordnet ist, mit drei nicht zugeordneten Farben mischt.

Mit der Abgabe des Commitments liegt das Gebot fest. Nachdem alle Bieter ihre Commitments abgegeben haben und damit alle Gebote festliegen, sendet jeder Bieter sein Gebot direkt an Alice, damit diese das beste Gebot auswählen kann. Um zu verhindern, dass die Gebote bekannt werden, nutzen sie dazu Verschlüsselungsverfahren. Da die Gebote jetzt festliegen, kann Eve keinen Einfluss auf das Verfahren mehr nehmen.

Alle drei Bieter geben ein Commitment mit ihrem Gebot als Inhalt ab.
Alle drei Bieter geben ein Commitment mit ihrem Gebot als Inhalt ab.

In unserem Beispiel hat Bob das beste Angebot abgegeben und das Bieterverfahren gewonnen. Alice gibt diese Entscheidung bekannt und Bob öffnet sein Commitment. Dazu nennt Bob sein Gebot und damit auch die zugeordnete Farbe, sowie die hinzugemischten nicht zugeordneten Farben. Nun prüft jeder der anderen Bieter zwei Dinge: Erstens mischt jeder die Farben von Bob zusammen und prüft, ob die resultierende Farbe das Commitment von Bob ergibt. Und zweitens sieht jeder Bieter sofort, ob das Gebot von Bob wirklich besser als das eigene war. Schauen wir uns beides im Detail an.

Bob hat sein Commitment geöffnet und die Farben genannt, aus denen er sein Commitment gemischt hat. Alice als Auftraggeberin sowie die Mitbewerber Carol und Dave prüfen, ob die von Bob angegeben Farben gemischt den gleichen Farbton ergeben, wie ihn sein Commitment hatte. Das menschliche Auge ist sehr gut darin festzustellen, ob zwei Farben gleich oder auch nur leicht unterschiedlich sind. Außerdem prüfen sie, ob Bob korrekt die zu seinem Gebot zugeordnete Farbe verwendet und keine andere einer anderen Zahl zugeordnete Farbe verwendet hat. Dies ist wichtig damit das Commitment-Verfahren verbindlich ist. Für Bob ist es praktisch unmöglich, zwei Farbkombinationen zu finden, die unterschiedliche (und jeweils eine) zugeordnete Farben beinhalten, aber trotzdem am Ende den gleichen Farbton als Commitment ergeben. Das aber bräuchte Bob, um ein Commitment auf zwei verschiedene Weisen öffnen zu können. Damit ist das Commitment für Bob, und analog für jeden anderen, verbindlich. Oben haben wir bereits gesagt, dass das Commitment-Verfahren verbergend ist, also besitzt das Commitment-Verfahren beide geforderten Eigenschaften.

Die Tatsache, dass das Commitment-Verfahren verbindlich, hilft uns auch beim nächsten Aspekt. Nachdem Bob sein Commitment geöffnet und damit sein Gebot bekannt gegeben hat, sehen Carol und Dave als Mitbewerber sofort, ob ihr eigenes Gebot besser war oder nicht. Im Streitfall helfen ihnen die Commitments, die Vergabe anzufechten. Falls Carol beispielsweise ein besseres Gebot abgegeben hätte, kann sie ihrerseits ihr Commitment öffnen und damit beweise, dass ihr Gebot besser war als das von Bob, und zwar bevor sie das Gebot von Bob erfahren hat. Da sie ihr Commitment abgegeben hatte, bevor Bob sein Gebot genannt hat, kann sie ihr Gebot nicht nachträglich verändert haben.

Die Eigenschaften der Farben in unserem Beispiel klingen vielleicht etwas weit hergeholt.
In der Welt der Mathematik müssen wir nicht auf Farben zurückgreifen, sondern benutzen spezielle mathematische Strukturen, nämlich zyklische Gruppen, in denen das Problem des diskreten Logarithmus schwer zu lösen ist. Die gleichen Strukturen werden von einigen Verschlüsselungs- und Signaturverfahren benutzt, bieten genau die Eigenschaften, die wir hier für das Commitment-Verfahren benötigen, und sind gut untersucht. Ein anderes berühmtes Verfahren, das diese Strukturen nutzt, ist der Diffie-Hellman-Schlüsselaustausch. Es gibt ein YouTube-Video und einen Artikel dazu (beides auf Englisch), bei denen ebenfalls das Verfahren mit Farben erklärt wird.
Aber zurück zu unseren Farben.

Das Beimischen der nicht zugeordneten Farben dient nicht nur dazu, den Inhalt des Commitments zu verbergen. Es erlaubt uns auch das Dazumischen weiterer nicht zugeordneter Farben zu einem bestehendem Commitment. Das Ergebnis ist ein neues Commitment, das den gleichen Inhalt hat wie das ursprüngliche (die zugeordnete Farbe hat sich ja nicht geändert), aber anders aussieht. Das Dazumischen lässt sich überprüfen. Wenn man weiß, welche nicht zugeordneten Farben dem ursprünglichen Commitment hinzugemischt wurden, kann man durch Nachmischen nachprüfen, dass beide Commitments den gleichen Inhalt haben. Um das neue Commitment zu öffnen, muss man lediglich der Liste der nicht zugeordneten Farben die dazugemischte Farbe hinzufügen. Diese zusätzliche Eigenschaft spielt eine zentrale Rolle für das zweiten Werkzeug der Kryptologie, das wir hier kennen lernen.

Zero-Knowledge-Beweise
Vera ist eine junge und aufstrebende Journalistin und möchte über den Bau des neuen Rathauses berichten und vor allem die Vergabe transparent machen. Dazu fragt sie Alice nach den Geboten, die die Firmen abgegeben haben. Um die Interessen der Bieter zu schützen kann Alice allerdings nicht verraten, welcher Bieter welches Gebot abgegeben hat. Sie hat jedoch von den Bietern die Erlaubnis bekommen, die Liste der abgegebenen Gebote zu veröffentlichen, wenn nicht ersichtlich ist, wer welches Gebot abgegeben hat. Vera nimmt die Liste der Commitments, die im Rahmen des Bieterverfahrens veröffentlicht wurden, und die Liste der Gebote dankend entgegen, zusammen mit der Versicherung von Alice, dass jedes Gebot in einem der Commitments enthalten sei.

Als gute Journalistin glaubt Vera diese Aussage nicht einfach sondern überprüft sie. Alice darf jedoch die Zuordnung zwischen Commitment und Gebot nicht verraten, denn sonst wäre klar, welcher Bieter welches Gebot abgegeben hat. Die speziellen Commitments, die die Bieter bei dem Bieterverfahren für ihre Gebote verwendet haben, erlauben aber einen sehr eleganten Ausweg, nämlich die Verwendung eines Zero-Knowledge-Beweises.

Bevor wir anfangen, müssen wir noch kurz eine Kleinigkeit klären. Alice möchte Vera "beweisen", dass die Inhalte der Liste der Commitments mit der Liste der Gebote übereinstimmt. Da stellt sich die Frage, was ist hier mit einem "Beweis" gemeint. Juristen und Mathematiker beispielsweise benutzen den Begriff, haben aber etwas unterschiedliche Vorstellungen davon, was ein Beweis genau ist. Gemein hat jedoch allen die Vorstellung, dass ein Beweis etwas ist, was mich überzeugt. Warum ein Zero-Knowledge-Beweis überzeugend ist sehen wir gleich. Zero-Knowledge-Beweise sind interaktive Beweis-Systeme mit ein paar kontraintuitiven Eigenschaften, die ich erstaunlich finde und die wir uns hier näher anschauen wollen.

Zunächst ist ein Zero-Knowledge-Beweis nicht einfach ein statischer Text, sondern ein Gespräch zwischen dem Beweiser, hier Alice, und einem Verifizierer, hier Vera, das über mehrere Runden geht. Alice möchte Vera überzeugen, dass ihre Behauptung korrekt ist und dass Alice ein bestimmtes Geheimnis kennt, aus dem sich die Behauptung direkt ergibt. Zu Zero-Knowledge-Beweisen hat Matthew Green eine gute Erklärung auf Englisch geschrieben, die ein Zero-Knowledge-Beweissysten mit Graph-3-Färbbarkeit beschreibt. Das oben beschriebenen Commitment-Verfahren ermöglicht einen anderen Zero-Knowledge-Beweis, den wir im Folgenden betrachten.

Schauen wir uns zuerst genauer an, was Alice beweisen will: Öffentlich bekannt sind eine Liste von Commitments von den Bietern sowie eine (gleich lange) Liste von Zahlen. Alice behauptet, dass es sich dabei um die Gebote handelt, die in den Commitments enthalten sind. Die Listen sind nicht geordnet, das erste Commitment hat also nicht die erste Zahl als Inhalt. Tatsächlich soll geheim bleiben, welches Commitment welche Zahl als Inhalt hat. Alice Geheimnis besteht aus der Zuordnung zwischen Commitment und Inhalt sowie den Informationen zum Öffnen der Commitments, also den für das Mischen verwendeten Farben. Das Ziel des Zero-Knowledge-Beweises ist es, Vera davon zu überzeugen, dass Alices Behauptung stimmt, ohne dass sie irgendwelche Kenntnis über Alices Geheimnis erlangt.

Um Vera zu überzeugen, erzeugt Alice zunächst neue Commitments und zeigt diese Vera. Dabei behauptet Alice, dass sie jedes der neuen Commitments durch Hinzumischen einer Farbe zu einem ursprünglichen Commitments erzeugt hat und die neuen Commitments damit den gleichen Inhalt haben wie die ursprünglichen. Anstatt die ursprünglichen Commitments direkt zu öffnen hat Alice mit der Erzeugung der neuen Commitments einen Zwischenschritt eingefügt und damit die zu beweisende Aussage in zwei Hälften zerlegt. Beide Hälften zusammen, also sowohl die Erzeugung der neuen Commitments aus den ursprünglichen als auch die Inhalte der neuen Commitments, verraten das Geheimnis von Alice. Jede Hälfte für sich aber ist wertlos.

Der erste Teil einer Runde des Zero-Knowledge-Beweises: Die Liste mit ursprünglichen Commitments (ganz links) und die Liste mit den Geboten (ganz rechts) sind bekannt. Alice erstellt die neuen Commitments (in der Mitte) und zeigt diese Vera.
Der erste Teil einer Runde des Zero-Knowledge-Beweises: Die Liste mit ursprünglichen Commitments (ganz links) und die Liste mit den Geboten (ganz rechts) sind bekannt. Alice erstellt die neuen Commitments (in der Mitte) und zeigt diese Vera.

Vera wählt, ob Alice die neuen Commitments öffnet oder ob sie ihr verrät, wie sie die neuen Commitments erzeugt hat. Wenn die Behauptung stimmt und Alice das Geheimnis kennt, kann sie beide Fragen beantworten. Kennt Alice das Geheimnis nicht, dann kann sie eine der beiden Fragen nicht beantworten. Damit hat Vera eine Chance von 50%, Alice zu erwischen, falls sie lügt. Vera allerdings empfindet eine 50%-ige Wahrscheinlichkeit, dass Alice sie anlügt, als zu hoch. Daher wiederholen Vera und Alice die Beweisschritte in einer neuen Runde. Alice erzeugt erneut eine Liste von neuen Commitments, und Vera wählt erneut, ob Alice die Erzeugung der neuen Commitments zeigt oder ob sie die neuen Commitments öffnet. Vera hat also wieder eine 50%-ige Chance, Alice beim Lügen zu erwischen. Bei zwei Wiederholungen liegt damit die Chance einen unehrlichen Beweiser zu erwischen schon bei 75%. Nach zehn Wiederholungen liegt die Chance bereits bei 99,9% Prozent. Durch weitere Wiederholungen lässt sich diese Chance beliebig nahe an 100% bringen. Vera kann die Beweisschritte so lange wiederholen, bis sie überzeugt ist, dass Alice das Geheimnis kennt und die fraglichen Inhalte tatsächlich in den Commitments enthalten sind.

Der zweite Teil einer Runde des Zero-Knowledge-Beweises: Nachdem Alice die neuen Commitments erstellt hat, trifft Vera eine Wahl. Entweder Vera lässt sich von Alice zeigen, wie sie die neuen Commitments aus den ursprünglichen Commitments erstellt hat (links) oder Alice öffnet die neuen Commitments und zeigt, dass die neuen Commitments tatsächlich den behaupteten Inhalt haben.
Der zweite Teil einer Runde des Zero-Knowledge-Beweises: Nachdem Alice die neuen Commitments erstellt hat, trifft Vera eine Wahl. Entweder Vera lässt sich von Alice zeigen, wie sie die neuen Commitments aus den ursprünglichen Commitments erstellt hat (links) oder Alice öffnet die neuen Commitments und zeigt, dass die neuen Commitments tatsächlich den behaupteten Inhalt haben.

Dieses Verfahren heißt Beweis, weil Vera am Ende überzeugt ist, dass die Behauptung stimmt. Aber warum nennt man es Zero-Knowledge? Ich habe behauptet, dass Vera als Verifizierer aus dem Gespräch mit Alice nicht mehr lernt als dass die Behauptung stimmt. Die Argumentation dafür ist ein bisschen abgefahren. Im Grunde dreht sich alles um die Frage, ob Vera ihren Lesern zusätzliche Informationen gibt, wenn sie das Gespräch mit Alice vollständig abdruckt, in dem Alice Vera beweist, dass die Inhalte der Liste der Commitment mit den später veröffentlichten Geboten übereinstimmt.

Betrachten wir dazu Walter, einen weiteren jungen und aufstrebenden Journalisten. Walter hat gehört, dass Vera über den Bau des neuen Rathauses berichtet und möchte ihr mit seiner Story zuvorkommen. Er nimmt sich aber nicht die Zeit, mit Alice zu sprechen und sich die Korrektheit ihrer Behauptung beweisen zu lassen. Stattdessen will sich Walter eine Unterhaltung mit Alice ausdenken, in der Alice ihn von der Korrektheit ihrer Behauptung überzeugt. Er stellt fest, dass dies ganz einfach ist. In der echten Unterhaltung zwischen Alice und Vera legt Alice zuerst eine Liste neuer Commitments vor, und Vera wählt dann, ob Alice die Entstehung der neuen Commitments aus den Originalen zeigt oder die neuen Commitments öffnet. Für seine ausgedachte Unterhaltung fängt Walter einfach mit der Frage an, die er als Verifizierer an die imaginäre Alice stellen will, und erzeugt dann die neuen Commitments entsprechend. Entscheidet er sich also für die Entstehung der neuen Commitments so erzeugt er einfach neue Commitments aus den alten. Entscheidet er sich hingegen für das Öffnen der neuen Commitments, so erzeugt er völlig neue Commitments, die die Gebote als Inhalt haben. Dann lässt Walter die imaginäre Alice die neuen Commitments präsentieren, stellt dann seine Frage und lässt die imaginäre Alice entsprechend antworten. Da seine Frage vorher feststand und Walter die neuen Commitments entsprechend erzeugt hat, kann er eine zur Frage passende Antwort angeben. Wie beim echten Beweis lässt sich dies beliebig wiederholen.

Eine von Walter erstellte Aufzeichnung einer Unterhaltung ist von der Aufzeichnung einer echten Unterhaltung nicht zu unterscheiden. Walter hat aber keine Ahnung, in welchem der Commitments, die die Bieter veröffentlicht haben, welches Gebot steckt. Also kann in der ausgedachten Aufzeichnung der Unterhaltung also auch keine Information darüber enthalten sein. Und wenn es nicht möglich ist, die Aufzeichnung einer ausgedachten Unterhaltung von einer echten zu unterscheiden, so ist auch in der echten Aufzeichnung keine Information über das Geheimnis enthalten. Die Aufzeichnung enthält alles, was der Verifizierer (in unserem Beispiel Vera) sieht, und daraus folgt, dass der Verifizierer zwar von der Korrektheit der Behauptung überzeugt ist, aber keine Informationen über das Geheimnis erhält.

An dieser Stelle muss ich zugeben, dass mir erst bei der Erstellung der Bilder aufgefallen ist, dass für den Zero-Knowledge-Beweis das Beispiel mit den Farben nicht funktioniert. Mich würde wirklich brennend interessieren, wer von den Lesern es ebenfalls gemerkt hat. Da ich aber leider kein besseres verständliches Beispiel für die Commitments habe, möchte ich hier stattdessen diskutieren, warum es nicht funktioniert, denn bekanntlich lernt man aus Fehlern ja am meisten (und es müssen nicht immer die eigenen sein). Schauen wir uns noch einmal genau an, wie die Antwort von Alice aussieht, wenn sich Vera für das Öffnen der neuen Commitments entscheidet. Alice nennt für jedes Commitment die zugeordnete Farbe sowie die Liste der nicht zugeordneten Farben, mit denen das Commitment erstellt wurde. Vera weiß jetzt aber, dass eine der nicht zugeordneten Farben nachträglich hinzugemischt wurde, um das neue Commitment zu erstellen. Sie kann einfach das Commitment nachmischen und dabei nacheinander jeweils eine der nicht zugeordneten Farben weglassen, bis sie eines der ursprünglichen Commitments erhält. Damit ist der Beweis auch kein Zero-Knowledge-Beweis, denn natürlich funktioniert dies nicht bei einer Aufzeichnung, die sich Walter ausgedacht hat.

Mein erster Gedanke war, dass sich dieses Problem lösen lässt, indem beim Öffnen eines Commitments nicht die Liste der nicht zugeordneten Farben genannt wird, sondern lediglich das Ergebnis, wenn man alle nicht zugeordneten Farben zusammenmischt. Dann könnte man nicht mehr durch Ausprobieren und Weglassen einzelner Farben beim Nachmischen ein ursprüngliches Commitment erhalten. Das würde zwar die Zero-Knowledge-Eigenschaft des Beweises retten, aber leider wäre damit das Commitment nicht mehr verbindlich. Denn beim Öffnen ließe sich nicht mehr überprüfen, ob Bob tatsächlich nur genau eine zugeordnete Farbe verwendet hat. Dies ist aber die Voraussetzung für die Verbindlichkeit des Commitments. Kleine Änderungen am Verfahren haben also drastische Auswirkungen auf die Sicherheit des Verfahrens. Dies ist bei vielen Verfahren der Kryptologie der Fall, und das macht die IT-Sicherheit so schwierig.

Ich habe bereits weiter oben gesagt, dass die mathematischen Strukturen, die für diese Commitments verwendet werden, die Eigenschaften besitzen, die ich für die Farben in unserem Beispiel postuliert habe. Hier tritt auch das beschriebene Problem mit dem Zero-Knowledge-Beweis nicht auf. Tatsächlich sind die realen Commitments bedingungslos verbergend (daher heißt das Verfahren "unconditionally hiding"), nicht einmal jemand mit unbegrenzter Rechenleistung oder einem Quantencomputer kann einem Commitment ansehen, was der Inhalt ist.

Wir haben gesehen, woher der Begriff Zero-Knowledge-Beweis kommt und warum ich es ein interaktives Beweis-System genannt habe.
Eine mögliche Anwendung für Zero-Knowledge-Beweise ist die Authentifizierung. In den meisten Fällen authentifiziert sich ein Computer (Client) bei einem anderen (Server), indem der Client ein Passwort an den Server übersendet und der Server dies mit einem gespeicherten Wert abgleicht. Verschlüsselung schützt das Passwort bei der Übertragung und eine Hashfunktion verhindert, dass der Server das Passwort direkt speichert (um es vor Diebstahl zu schützen). Diese Schutzmaßnahmen werden hinfällig, wenn statt eines Passworts ein Zero-Knowledge-Beweis verwendet wird. Der Client beweist dem Server, dass er ein bestimmtes Passwort kennt, und durch den Zero-Knowledge-Beweis ist sicher gestellt, dass niemand (nicht einmal der Server) das Geheimnis erfährt.

Die Authentifizierung ist aber bei Weitem nicht die einzige Anwendungsmöglichkeit für Zero-Knowledge-Beweise. Tatsächlich sind sie ein mächtiges Werkzeug der Kryptologie und ermöglichen viele weitere erstaunliche Leistungen. Zusammen mit dem Commitment-Verfahren, das wir oben kennen gelernt haben, bilden die hier beschriebenen, speziellen Zero-Knowledge-Beweise beispielsweise die Grundbausteine von Bingo Voting. Bingo Voting ist ein Wahlverfahren, bei dem der Wähler seine Stimme an einem Wahlcomputer abgibt und einen Beleg erhält. Mit diesem Beleg kann der Wähler kontrollieren, dass seine Stimme korrekt gezählt wurde, sogar wenn der Wahlcomputer manipuliert wurde und versucht, die Wahl zu verfälschen. Wer mehr zu Bingo Voting erfahren möchte, dem empfehle ich die Wikipedia-Seite von Bingo Voting als Einstieg.

20 Gedanken zu „Kryptologie jenseits der Verschlüsselung“
  1. …. ein buch mit 7 siegeln?
    so ein wenig erahne ich, was es an bedeutung mit sich bringt, auch wenn ich den ‚verschlüsselungsprozess‘ selbst nicht genau nachvollziehen kann, oder nur ein bißchen davon, im ersten teil des textes.
    aber allein, dass es doch andere lösungen als ein versiegelter umschlag gibt, hat natürlich vorteile. unveränderbar + nachprüfbar = wunderbar!
    vermutlich geht die richtung dann auch dahin, dass nachrichten einen persönlichen und einen für alle zugänglichen schlüssel haben, mit dem dann jeweils geprüft werden kann, dass eine bestimmte info enthalten ist, deren inhalt aber nur mit dem geeigneten schlüssel gelesen werden kann.
    das thema ist sehr interessant, besonders in der elektronischen datenwelt, aber sollte ich damit mal konfrontiert werden, dann lieber nur als anwender der mit seinem bunten farben noch bunteres entwerfen kann

  2. Höchst interessant. Klasse idee/Ergebnis dass man tatsächlich ohne inhaltsoffenlegung die Korrektheit einer Übermittlung beweisen kann. Bingo-Voting gucke ich mir gleich an. 🙂

  3. Bingo-Voting ist in Deutschland politisch nicht gewollt. Stell dir vor du kannst alle Wahllokale überprüfen, da gruselt’s den Politiker der gerne die Wahlurnen aus bekannten gegnerischen Wahlkreisen verschwinden lassen will.

    Das mit den Commitments sieht tatsächlich sehr interessant aus. Ich sehe allerdings zwei Schwachstellen:

    – Es muss aktives interesse an einer nicht-fälschbaren Ausschreibung vorliegen. (Ja das ist genauso schlimm gemeint wie es geschrieben ist)
    – Die Bürgermeister/Firmenchefs, die etwas ausschreiben, müssten sich mit solchen Verfahren auskennen. Naja. Sie müssten mehrheitlich wenigstens wissen dass so etwas existiert. Ich halte das für zu viel verlangt. Im Einzelfall wird so etwas bekannt sein, aber längst nicht weit genug verbreitet.

    Da wäre eine Android- oder Windows-App, welche so ein Verfahren einfach und Endnutzerfähig sogar für Schackeline aus Marzahn anbietet ein echter Durchbruch.

    Natürlich müsste die App politisch begleitet werden: Entwickeln, vertrauen in das Verfahren aufbauen, Werbung treiben und von oben herab vorschreiben sind vier Dinge die da Hand in Hand gehen müssten.

    Das einfachste daran ist wahrscheinlich die Entwicklung.

  4. Ad 5 – Andreas. Ach – immer diese verschwörungsideen. Nun gut. Egal ob Interesse oder Wissen über diese Methoden bestehen, kann ganz einfach das per Ausschreibungsregeln das gesetzlich vorgeschrieben werden.

    Ich bin allerdings der Meinung, dass „elektronisches“ Wählen unsinnig ist – egal wie klasse die Methode ist.
    Das „analoge“ wählen mit Papier und Stift ist klar auch manipulierbar – aber viel einleuchtender und nachvollziehbarer für die Bürger.
    Möglicherweise könnte man als sicherungsmaßnahme ausgewählten Bürger „erlauben“ , Fotos von ihrem Wahlzettel zu machen (wahlgeheimnis soll ja den Bürger schützen – nicht den Staat.).
    Dann werden Foto mit datum und Aussage des Bürgers von unterschiedlichen Notaren verwahrt und bei stichproben-Kontrolle oder Verdacht „gezogen“.
    🙂

  5. Harter Stoff, aber gut erklärt soweit, finde ich. Dass ich es jetzt nicht bis ins Detail durchdrungen habe, liegt da eher an meiner Trägheit.

    An dieser Stelle muss ich zugeben, dass mir erst bei der Erstellung der Bilder aufgefallen ist, dass für den Zero-Knowledge-Beweis das Beispiel mit den Farben nicht funktioniert. (…) Da ich aber leider kein besseres verständliches Beispiel für die Commitments habe, möchte ich hier stattdessen diskutieren, warum es nicht funktioniert,

    Schön die Kurve gekriegt :]

    (Abgesehen davon würde die Misch-Arie nach sehr kurzer Zeit nur noch graubraune Pampe ergeben, aber als Beispiel reicht es natürlich).

  6. @Andreas (#5) Das Haupthindernis für Bingo Voting ist das Urteil des BVerfG zu Wahlmaschinen. In der Urteilsbegründung wird aus dem Wahlgrundsatz der Öffentlichkeit gefolgert, dass alle wesentliche Schritte der Wahl öffentlich nachvollziehbar sein müssen, und zwar ohne Spezialkenntnisse. Und das schließt auch ein kryptologisches Verfahren wie Bingo Voting aus, da man das Verfahren auch nur mit entsprechenden Kenntnissen vollständig nachvollziehen kann. (Die Überprüfung der korrekten Berücksichtigung der eigenen Stimme geht übrigens auch ohne Spezialkenntnisse.) Ich verstehe nur nicht, warum das Sitzzuteilungsverfahren nach der Bundestagswahl dem Grundsatz der Öffentlichkeit entspricht, denn wenn das Hare-Niemeyer-Verfahren kein Spezialwissen ist, dann weiß ich auch nicht. Aber das ist ein anderes Thema.

    Den politischen Willen zu Ausschreibungen mit Commitments kann ich natürlich nicht heraufbeschwören. Ich finde es aber schade, dass kaum jeman die vorhandenen Möglichkeiten kennt. Und Commitments sind wirklich einfach, jedes digitale Signaturverfahren ist komplizierter. Daher fände ich es sehr schön, wenn sie verbreiteter wären. Ausschreibungen habe ich nur als Motivation und zur Veranschaulichung gewählt, es gibt noch viele andere Anwendungen.

  7. Ok, dieses Urteil kann ich aber nachvollziehen – wer weiß schon ob der Computer Kryptodinge tut oder eher das Ergebnis fälscht.
    Ich bin übrigens ein großer Fan der Stimmenkontrolle durch den Wähler – mir fällt aber kein Verfahren ein wie das erreicht werden kann ohne die Stimmzettel selbst zu chiffrieren. Sonst kann dir ja jeder den Zettel wegnehmen und im Internet nachschauen was du gewählt hast.

    Gibt es eine App die „commitments for dummies“ anbietet?

  8. Wenn Vera ihr (echtes) Gesprächsprotokoll mit Alice veröffentlicht, warum sollte ihr dann der Leser glauben? Immerhin ist es ein Feature, daß Walter mit seinem erfundenen Protokoll genauso überzeugend ist.

  9. @Anderas (#9) Bingo Voting ist so gemacht, dass man es immer merkt, wenn der Wahlcomputer die Wahl fälscht. Genauer gesagt: Wenn sich der Computer an das Bingo-Voting-Protokoll hält, ist das Wahlergebnis korrekt, und wenn der Computer davon abweicht, dann merkt man es. Es gibt eine ganze Reihe von kryptologischen Wahlverfahren, die dem Wähler einen Beleg geben, auf dem seine Stimme in irgendeiner Art chiffriert ist. Ein Beleg, auf dem die Stimme (mit eindeutiger Stimmzettelnummer) im Klartext steht, ist natürlich am einfachsten. Aber wie du richtig angemerkt hast, öffnet das Stimmenkauf und Erpressung Tür und Tor. Die Frage bei den kryptologischen Wahlverfahren ist immer, wie der Stimmzettel die Stimme chiffriert, so dass der Wähler überzeugt ist, dass seine Stimme tatsächlich korrekt repräsentiert ist, ohne dass ein Dritter etwas über die Stimme herauslesen kann. Da denkt man jetzt vielleicht an Zero-Knowledge-Beweise, und tatsächlich haben Moran und Naor ein solchen Wahlverfahren 2006 vorgeschlagen (Tal Moran, Moni Naor: RECEIPT-FREE UNIVERSALLY-VERIFIABLE VOTING WITH EVERLASTING PRIVACY (PDF)).

    Ich kenne keine App, die Commitments in irgendeiner Form anbietet. Ich habe aber ehrlich gesagt noch nie danach gesucht.

    @Chemiker (#10) Genau richtig erkannt: Es bringt Vera überhaupt nichts, das echte Gesprächsprotokoll zu veröffentlichen, da ein erfundenes genauso aussieht (man sagt, das echte und das erfundene Protokoll sind ununterscheidbar). Und das ist das Argument, warum das Protokoll Zero-Knowledge heißt: Wenn man dem Protokoll nicht ansieht, ob es echt ist oder erfunden wurde von jemanden, der das Geheimnis nicht kennt, dann kann das Protokoll auch keine Information über das Geheimnis enthalten.

  10. @Cornelia S. Gliem (#6) Ich habe nichts gegen die Wahl mit Papier und Stift, auch wenn einige Argumente für Wahlcomputer sprechen (Barrierefreiheit, Unterstützung der Wähler bei komplexen Wahlen, schnelle Auszählung, …). Ich finde es nur befremdlich, wenn die Papierwahl glorifiziert wird. Wie du sagst hat die Papierwahl auch Schwächen. Für mich ist die Entscheidung nicht so eindeutig.

    Die Idee mit dem Hinterlegen von Fotos beim Notar finde ich interessant. Allerdings birgt jedes Foto die Gefahr des Stimmenkaufs bzw. der Erpressung. Kann der Wähler nachweisen, wie er gewählt hat, kann er seine Stimme auch verkaufen. Das verletzt den Grundsatz der Gleichheit der Stimme (Einzelne können sich zusätzliche Stimmen kaufen). Daher ist auch bei der Papierwahl ein markierter Stimmzettel ungültig.

  11. hmmm, ein interessanter aspekt
    aber die schwerste hürde ist sicher die stimme des einzelnen. kein system kann einen kauf oder einen einfluss VOR abgabe der stimme sichern.
    aber wenn dann die stimme abgegeben wird, hat das papier für mich 2 vorteile:
    es lässt sich gut archivieren, falls nochmal geprüft werden muss, und eine komplexe änderung ist nur mit viel aufwand möglich – anders bei der elektronischen erfassung. dort könnten mit gleichsam weniger aufwand mehr stimmen geändert werden.
    auch wenn der einwand der derzeitigen weitergabe von ergebnissen auch schon anfällig genug ist.

    evt lässt sich mit dem o.g. thema doch noch in dieser richtung eine sicherheit einbauen.
    aber das müssen andere erforschen ….

  12. @Mars: Der Gedanke beim Stimenkauf ist glaube ich, dass der erst richtig attraktiv wird, wenn er sich auch beweisen lässt. Wenn ich meine Stimme verkaufe, wird der Käufer wohl auch gerne sehen, dass ich dann wirklich für ihn gestimmt habe (und nicht z.B. meine Stimme mehrfach verkauft habe). Wären markierte Wahlzettel gültig, könnte derjenige zum Beispiel einfach bei der (ja theoretisch öffentlichen) Auszählung zuschauen und überprüfen, dass es wirklich einen Wahlzettel mit dem vorher verabredeten Zeichen gibt, der für den richtigen stimmt. Gleiches für Erpressungen u.Ä.

    Was das nachträgliche Verändern angeht, das ist so eine der Hauptdomänen der Kryptologie. Da dürfte es bei jedem sinnvollen Verfahren eigentlich praktisch unmöglich sein, auch nur eine Stimme zu ändern oder zu entfernen, ohne dass es auffällt.

  13. Hm. Im Grunde bedeutet das, dass nur direkte Abstimmungen eindeutig für den Wähler ist. Natürlich ist diese dann auch nicht geheim – und Stimmenkauf und Erpressung ist auch nicht ausgeschlossen. .. Übrigens ein kaum gehörtes Argument gegen direkte Demokratie :-).

  14. @Cornelia
    bei 60 Mio stimmen sehe ich da erst mal kein grossen belang.
    was aber bei – sagen wir mal bei einer elitären gruppe – von 709 stimmberechtigten im hintergrund abläuft, wenn gedrückt, gekauft, geschoben werden darf …weil die auswirkung der einzelnen stimme viel mehr ausmacht, lässt mich eher schaudern.

  15. Den Teil mit den Commitments habe ich verstanden, schön erklärt und bebildert, volle Punktzahl von mir. Aber bei den Zero-Knowledge-Beweisen hast Du mich abgehängt, ich habe noch nicht verstanden, wieso Vera bei der Wahl, das Commitment offen zu legen, nicht die Information erhält, wer wieviel geboten hat (das ist doch gerade die Offenlegung). Dafür nur 3 von 5 Punkten. Macht insgesamt 4.

  16. @Alderamin (#17) Bevor Vera sich entscheidet, kennt sie

    die alten Commitments,
    die Information, welches alte Commitment von welchem Bieter stammt,
    die neuen Commitments (die sind jede Runde neu), und
    die Liste mit Geboten.

    Vor der Entscheidung weiß Vera nicht, welches alte Commitment zu welchem neuen Commitment gehört, oder welches neue Commitment zu welchem Gebot gehört. Ver darf sich für eine der beiden Informationen entscheiden, die sie dann von Alice erhält. Entscheidet Vera sich für die Zuordnung der neuen Commitments zu den Geboten, verrät Alice ihr, welches neuen Commitment zu welchem Gebot gehört, indem Alice die neuen Commitments öffnet (nicht die alten, die von den Bietern tatsächlich abgegeben wurden). Aber da Vera immer noch nicht weiß, welches neue Commitment zu welchem alten Commitment gehört, kennt sie damit noch nicht die Zuordnung von alten Commitments zu Geboten.

  17. Wahlen elektronisch durchzuführen ist sicher eine gute Grundlage für Verschwörungstheorien. Ob ein elektronisches Verfahren fälschungssicher ist, kann die Mehrheit der Wähler nur glauben. Ein elektronischer Wahlvorgang würde das Vertrauen in die Richtigkeit des Ergebnisses untergraben.

  18. Prinzipiell ein interessantes Thema und auch gut geschrieben, ich glaube ich habe sowohl das Prinzip der Commitments als auch der Zero Knowledge-Beweise verstanden, aber irgendwie hab ich das Gefühl, dass das nur zum Teil an den Erklärungen liegt.
    Die Beispiele waren für meinen Geschmack etwas zu kompliziert aufgebaut, die Ebene mit den ganzen Personen hätte man meines Erachtens auch weglassen können.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.