{"id":24383,"date":"2017-10-28T07:00:17","date_gmt":"2017-10-28T05:00:17","guid":{"rendered":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/2017\/10\/28\/kryptologie-jenseits-der-verschluesselung\/"},"modified":"2025-05-14T16:36:56","modified_gmt":"2025-05-14T14:36:56","slug":"kryptologie-jenseits-der-verschluesselung","status":"publish","type":"post","link":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/2017\/10\/28\/kryptologie-jenseits-der-verschluesselung\/","title":{"rendered":"Kryptologie jenseits der Verschl\u00fcsselung"},"content":{"rendered":"

\"sb-wettbewerb_klein\"<\/a>Dieser Artikel ist Teil des ScienceBlogs Blog-Schreibwettbewerb 2017<\/a>. Informationen zum Ablauf gibt es hier<\/a>. Leserinnen und Leser k\u00f6nnen die Artikel bewerten und bei der Abstimmung einen Preis gewinnen – Details dazu gibt es hier<\/a>. Eine \u00dcbersicht \u00fcber alle am Bewerb teilnehmenden Artikel gibt es hier<\/a>. Informationen zu den Autoren der Wettbewerbsartikel finden sich in den jeweiligen Texten.<\/i>
\n——————————————————————————————————————
\nKryptologie jenseits der Verschl\u00fcsselung<\/b><\/p>\n

von Christian Henrich<\/p>\n

Seitdem ich das Buch Geheime Botschaften<\/i> von Simon Singh gelesen habe, bin ich von der Kryptologie fasziniert. Ich habe am Karlsruher Institut f\u00fcr Technologie (KIT) als Doktorand im Bereich kryptographische Wahlverfahren promoviert und geh\u00f6re zu der Arbeitsgruppe, die 2008 mit dem Deutschen IT-Sicherheitspreis<\/a> f\u00fcr das kryptographische Wahlverfahren Bingo Voting<\/i><\/a> ausgezeichnet wurden.<\/p>\n

Die moderne Kryptologie hat viel mehr zu bieten als nur Geheimschriften. Zwei wichtige Werkzeuge der modernen Kryptologie m\u00f6chte ich hier pr\u00e4sentieren. Commitments<\/b> legen eine Zahl fest, ohne sie zu verraten. Zero-Knowledge-Beweise<\/b> \u00fcberzeugen jemanden von der Korrektheit einer Aussage, ohne irgendetwas anderes zu enth\u00fcllen.<\/p>\n

Kryptologie l\u00e4sst die meisten an Geheimschriften und Verschl\u00fcsselungsverfahren denken. Und bis weit in das letzte Jahrhundert hinein war das Bild damit auch (fast) vollst\u00e4ndig. Inzwischen hat sich die Kryptologie weiterentwickelt und bietet mehr als Verschl\u00fcsselungsverfahren, 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\u00e4lt, die sie meiner Meinung nach verdient. Viele kennen bestimmt digitale Signaturen<\/i>, die Dokumente gegen unbemerkte Ver\u00e4nderung sch\u00fctzen. Recht bekannt sind noch Kryptow\u00e4hrungen<\/i> wie Bitcoin.
\nWenige kennen jedoch sichere Mehrparteienberechnungen<\/i>, die in diesem YouTube-Video<\/a> an einem einfachen Beispiel erkl\u00e4rt werden.
\nAber selbst das ist noch nicht alles, was die moderne Kryptologie vermag. Mit diesem Text m\u00f6chte ich zwei erstaunliche Werkzeuge vorstellen und daran aufzeigen, was die Kryptologie noch zu bieten hat. <\/p>\n

Commitments<\/b>
\nAls Motivation f\u00fcr die beiden Werkzeuge der modernen Kryptologie schauen wir uns folgendes Problem an: Alice ist B\u00fcrgermeisterin einer mittelgro\u00dfen Stadt und m\u00f6chte den Auftrag f\u00fcr den Bau des neuen Rathauses vergeben. Dazu f\u00fchrt sie ein Bieterverfahren durch, bei dem ein Gebot aus einer einzigen Zahl, den Kosten f\u00fcr den Bau, besteht. F\u00fcr Alice ist nat\u00fcrlich das g\u00fcnstigste das beste Angebot. Die Firmen von Bob, Carol und Dave sind an dem Auftrag interessiert und m\u00f6chten ein Gebot abgeben. Damit die anderen Interessenten das Gebot nicht erfahren, will jeder sein Gebot verschl\u00fcsselt abgeben, so dass nur Alice und ihre Mitarbeiter die Gebote erfahren.<\/p>\n

Es gibt jedoch eine Komplikation. Eve ist die Nichte von Dave und arbeitet f\u00fcr Alice in der Abteilung, die den Bauauftrag vergibt. Um einen m\u00f6glichen Einfluss auf das Bieterverfahren zu verhindern (indem Eve die Gebote der Mitbewerber an Dave verr\u00e4t) verwendet Alice statt Verschl\u00fcsselung ein anderes Werkzeug der Kryptologie, n\u00e4mlich Commitments<\/b>.<\/p>\n

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

Da wir die Funktionsweise im Detail verstehen wollen, schauen wir uns das Verfahren an, wie es mit Farben funktionieren w\u00fcrde. Stellen wir uns vor, Alice besitzt einen Farbkasten mit vielen Farben. Von diesen Farben ist ein Teil jedem m\u00f6glichen Wert eines Gebots zugeordnet. Die \u00fcbrigen Farben sind nicht zugeordnet. Aus diesen Farben mischt jeder Bieter einen Farbton und gibt diesen als Commitment ab.<\/p>\n

\"So<\/a>
So sieht der Farbkasten f\u00fcr 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.<\/figcaption><\/figure>\n

F\u00fcr 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\u00e4lt, 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\u00fcn gestrichenes Zimmer zu streichen, kann best\u00e4tigen, wie schwierig es ist, aus einer Farbe das exakte Mischungsverh\u00e4ltnis der Grundfarben zu bestimmen. Damit ist das Commitment, also die von Bob gemischte Farbe, schon einmal verbergend<\/i>.<\/p>\n

\"Bob<\/a>
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.<\/figcaption><\/figure>\n

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\u00e4hlen kann. Um zu verhindern, dass die Gebote bekannt werden, nutzen sie dazu Verschl\u00fcsselungsverfahren. Da die Gebote jetzt festliegen, kann Eve keinen Einfluss auf das Verfahren mehr nehmen.<\/p>\n

\"Alle<\/a>
Alle drei Bieter geben ein Commitment mit ihrem Gebot als Inhalt ab.<\/figcaption><\/figure>\n

In unserem Beispiel hat Bob das beste Angebot abgegeben und das Bieterverfahren gewonnen. Alice gibt diese Entscheidung bekannt und Bob \u00f6ffnet sein Commitment. Dazu nennt Bob sein Gebot und damit auch die zugeordnete Farbe, sowie die hinzugemischten nicht zugeordneten Farben. Nun pr\u00fcft jeder der anderen Bieter zwei Dinge: Erstens mischt jeder die Farben von Bob zusammen und pr\u00fcft, 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.<\/p>\n

Bob hat sein Commitment ge\u00f6ffnet und die Farben genannt, aus denen er sein Commitment gemischt hat. Alice als Auftraggeberin sowie die Mitbewerber Carol und Dave pr\u00fcfen, 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\u00dferdem pr\u00fcfen 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<\/i> ist. F\u00fcr Bob ist es praktisch unm\u00f6glich, 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\u00e4uchte Bob, um ein Commitment auf zwei verschiedene Weisen \u00f6ffnen zu k\u00f6nnen. Damit ist das Commitment f\u00fcr Bob, und analog f\u00fcr jeden anderen, verbindlich<\/i>. Oben haben wir bereits gesagt, dass das Commitment-Verfahren verbergend<\/i> ist, also besitzt das Commitment-Verfahren beide geforderten Eigenschaften. <\/p>\n

Die Tatsache, dass das Commitment-Verfahren verbindlich<\/i>, hilft uns auch beim n\u00e4chsten Aspekt. Nachdem Bob sein Commitment ge\u00f6ffnet 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\u00e4tte, kann sie ihrerseits ihr Commitment \u00f6ffnen 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\u00e4glich ver\u00e4ndert haben.<\/p>\n

Die Eigenschaften der Farben in unserem Beispiel klingen vielleicht etwas weit hergeholt.
\nIn der Welt der Mathematik m\u00fcssen wir nicht auf Farben zur\u00fcckgreifen, sondern benutzen spezielle mathematische Strukturen, n\u00e4mlich zyklische Gruppen, in denen das Problem des diskreten Logarithmus schwer zu l\u00f6sen ist. Die gleichen Strukturen werden von einigen Verschl\u00fcsselungs- und Signaturverfahren benutzt, bieten genau die Eigenschaften, die wir hier f\u00fcr das Commitment-Verfahren ben\u00f6tigen, und sind gut untersucht. Ein anderes ber\u00fchmtes Verfahren, das diese Strukturen nutzt, ist der Diffie-Hellman-Schl\u00fcsselaustausch. Es gibt ein YouTube-Video<\/a> und einen Artikel<\/a> dazu (beides auf Englisch), bei denen ebenfalls das Verfahren mit Farben erkl\u00e4rt wird.
\nAber zur\u00fcck zu unseren Farben.<\/p>\n

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\u00fcngliche (die zugeordnete Farbe hat sich ja nicht ge\u00e4ndert), aber anders aussieht. Das Dazumischen l\u00e4sst sich \u00fcberpr\u00fcfen. Wenn man wei\u00df, welche nicht zugeordneten Farben dem urspr\u00fcnglichen Commitment hinzugemischt wurden, kann man durch Nachmischen nachpr\u00fcfen, dass beide Commitments den gleichen Inhalt haben. Um das neue Commitment zu \u00f6ffnen, muss man lediglich der Liste der nicht zugeordneten Farben die dazugemischte Farbe hinzuf\u00fcgen. Diese zus\u00e4tzliche Eigenschaft spielt eine zentrale Rolle f\u00fcr das zweiten Werkzeug der Kryptologie, das wir hier kennen lernen.<\/p>\n

Zero-Knowledge-Beweise<\/b>
\nVera ist eine junge und aufstrebende Journalistin und m\u00f6chte \u00fcber 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\u00fctzen 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\u00f6ffentlichen, wenn nicht ersichtlich ist, wer welches Gebot abgegeben hat. Vera nimmt die Liste der Commitments, die im Rahmen des Bieterverfahrens ver\u00f6ffentlicht wurden, und die Liste der Gebote dankend entgegen, zusammen mit der Versicherung von Alice, dass jedes Gebot in einem der Commitments enthalten sei.<\/p>\n

Als gute Journalistin glaubt Vera diese Aussage nicht einfach sondern \u00fcberpr\u00fcft sie. Alice darf jedoch die Zuordnung zwischen Commitment und Gebot nicht verraten, denn sonst w\u00e4re klar, welcher Bieter welches Gebot abgegeben hat. Die speziellen Commitments, die die Bieter bei dem Bieterverfahren f\u00fcr ihre Gebote verwendet haben, erlauben aber einen sehr eleganten Ausweg, n\u00e4mlich die Verwendung eines Zero-Knowledge-Beweises<\/b>.<\/p>\n

Bevor wir anfangen, m\u00fcssen wir noch kurz eine Kleinigkeit kl\u00e4ren. Alice m\u00f6chte Vera "beweisen", dass die Inhalte der Liste der Commitments mit der Liste der Gebote \u00fcbereinstimmt. 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 \u00fcberzeugt. Warum ein Zero-Knowledge-Beweis \u00fcberzeugend 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\u00e4her anschauen wollen.<\/p>\n

Zun\u00e4chst ist ein Zero-Knowledge-Beweis nicht einfach ein statischer Text, sondern ein Gespr\u00e4ch zwischen dem Beweiser, hier Alice, und einem Verifizierer, hier Vera, das \u00fcber mehrere Runden geht. Alice m\u00f6chte Vera \u00fcberzeugen, 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\u00e4rung auf Englisch<\/a> geschrieben, die ein Zero-Knowledge-Beweissysten mit Graph-3-F\u00e4rbbarkeit beschreibt. Das oben beschriebenen Commitment-Verfahren erm\u00f6glicht einen anderen Zero-Knowledge-Beweis, den wir im Folgenden betrachten.<\/p>\n

Schauen wir uns zuerst genauer an, was Alice beweisen will: \u00d6ffentlich 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\u00e4chlich soll geheim bleiben, welches Commitment welche Zahl als Inhalt hat. Alice Geheimnis besteht aus der Zuordnung zwischen Commitment und Inhalt sowie den Informationen zum \u00d6ffnen der Commitments, also den f\u00fcr das Mischen verwendeten Farben. Das Ziel des Zero-Knowledge-Beweises ist es, Vera davon zu \u00fcberzeugen, dass Alices Behauptung stimmt, ohne dass sie irgendwelche Kenntnis \u00fcber Alices Geheimnis erlangt.<\/p>\n

Um Vera zu \u00fcberzeugen, erzeugt Alice zun\u00e4chst neue Commitments und zeigt diese Vera. Dabei behauptet Alice, dass sie jedes der neuen Commitments durch Hinzumischen einer Farbe zu einem urspr\u00fcnglichen Commitments erzeugt hat und die neuen Commitments damit den gleichen Inhalt haben wie die urspr\u00fcnglichen. Anstatt die urspr\u00fcnglichen Commitments direkt zu \u00f6ffnen hat Alice mit der Erzeugung der neuen Commitments einen Zwischenschritt eingef\u00fcgt und damit die zu beweisende Aussage in zwei H\u00e4lften zerlegt. Beide H\u00e4lften zusammen, also sowohl die Erzeugung der neuen Commitments aus den urspr\u00fcnglichen als auch die Inhalte der neuen Commitments, verraten das Geheimnis von Alice. Jede H\u00e4lfte f\u00fcr sich aber ist wertlos.<\/p>\n

\"Der<\/a>
Der erste Teil einer Runde des Zero-Knowledge-Beweises: Die Liste mit urspr\u00fcnglichen 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.
<\/figcaption><\/figure>\n

Vera w\u00e4hlt, ob Alice die neuen Commitments \u00f6ffnet oder ob sie ihr verr\u00e4t, 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\u00fcgt. Vera allerdings empfindet eine 50%-ige Wahrscheinlichkeit, dass Alice sie anl\u00fcgt, 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\u00e4hlt erneut, ob Alice die Erzeugung der neuen Commitments zeigt oder ob sie die neuen Commitments \u00f6ffnet. Vera hat also wieder eine 50%-ige Chance, Alice beim L\u00fcgen 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\u00e4sst sich diese Chance beliebig nahe an 100% bringen. Vera kann die Beweisschritte so lange wiederholen, bis sie \u00fcberzeugt ist, dass Alice das Geheimnis kennt und die fraglichen Inhalte tats\u00e4chlich in den Commitments enthalten sind.<\/p>\n

\"Der<\/a>
Der zweite Teil einer Runde des Zero-Knowledge-Beweises: Nachdem Alice die neuen Commitments erstellt hat, trifft Vera eine Wahl. Entweder Vera l\u00e4sst sich von Alice zeigen, wie sie die neuen Commitments aus den urspr\u00fcnglichen Commitments erstellt hat (links) oder Alice \u00f6ffnet die neuen Commitments und zeigt, dass die neuen Commitments tats\u00e4chlich den behaupteten Inhalt haben.
<\/figcaption><\/figure>\n

Dieses Verfahren hei\u00dft Beweis, weil Vera am Ende \u00fcberzeugt ist, dass die Behauptung stimmt. Aber warum nennt man es Zero-Knowledge? Ich habe behauptet, dass Vera als Verifizierer aus dem Gespr\u00e4ch mit Alice nicht mehr lernt als dass die Behauptung stimmt. Die Argumentation daf\u00fcr ist ein bisschen abgefahren. Im Grunde dreht sich alles um die Frage, ob Vera ihren Lesern zus\u00e4tzliche Informationen gibt, wenn sie das Gespr\u00e4ch mit Alice vollst\u00e4ndig abdruckt, in dem Alice Vera beweist, dass die Inhalte der Liste der Commitment mit den sp\u00e4ter ver\u00f6ffentlichten Geboten \u00fcbereinstimmt.<\/p>\n

Betrachten wir dazu Walter, einen weiteren jungen und aufstrebenden Journalisten. Walter hat geh\u00f6rt, dass Vera \u00fcber den Bau des neuen Rathauses berichtet und m\u00f6chte 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<\/i>, in der Alice ihn von der Korrektheit ihrer Behauptung \u00fcberzeugt. 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\u00e4hlt dann, ob Alice die Entstehung der neuen Commitments aus den Originalen zeigt oder die neuen Commitments \u00f6ffnet. F\u00fcr seine ausgedachte Unterhaltung f\u00e4ngt Walter einfach mit der Frage an, die er als Verifizierer an die imagin\u00e4re Alice stellen will, und erzeugt dann die neuen Commitments entsprechend. Entscheidet er sich also f\u00fcr die Entstehung der neuen Commitments so erzeugt er einfach neue Commitments aus den alten. Entscheidet er sich hingegen f\u00fcr das \u00d6ffnen der neuen Commitments, so erzeugt er v\u00f6llig neue Commitments, die die Gebote als Inhalt haben. Dann l\u00e4sst Walter die imagin\u00e4re Alice die neuen Commitments pr\u00e4sentieren, stellt dann seine Frage und l\u00e4sst die imagin\u00e4re 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\u00e4sst sich dies beliebig wiederholen.<\/p>\n

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\u00f6ffentlicht haben, welches Gebot steckt. Also kann in der ausgedachten Aufzeichnung der Unterhaltung also auch keine Information dar\u00fcber enthalten sein. Und wenn es nicht m\u00f6glich ist, die Aufzeichnung einer ausgedachten Unterhaltung von einer echten zu unterscheiden, so ist auch in der echten Aufzeichnung keine Information \u00fcber das Geheimnis enthalten. Die Aufzeichnung enth\u00e4lt alles, was der Verifizierer (in unserem Beispiel Vera) sieht, und daraus folgt, dass der Verifizierer zwar von der Korrektheit der Behauptung \u00fcberzeugt ist, aber keine Informationen \u00fcber das Geheimnis erh\u00e4lt.<\/p>\n

An dieser Stelle muss ich zugeben, dass mir erst bei der Erstellung der Bilder aufgefallen ist, dass f\u00fcr den Zero-Knowledge-Beweis das Beispiel mit den Farben nicht funktioniert. Mich w\u00fcrde wirklich brennend interessieren, wer von den Lesern es ebenfalls gemerkt hat. Da ich aber leider kein besseres verst\u00e4ndliches Beispiel f\u00fcr die Commitments habe, m\u00f6chte ich hier stattdessen diskutieren, warum es nicht funktioniert, denn bekanntlich lernt man aus Fehlern ja am meisten (und es m\u00fcssen nicht immer die eigenen sein). Schauen wir uns noch einmal genau an, wie die Antwort von Alice aussieht, wenn sich Vera f\u00fcr das \u00d6ffnen der neuen Commitments entscheidet. Alice nennt f\u00fcr jedes Commitment die zugeordnete Farbe sowie die Liste der nicht zugeordneten Farben, mit denen das Commitment erstellt wurde. Vera wei\u00df jetzt aber, dass eine der nicht zugeordneten Farben nachtr\u00e4glich 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\u00fcnglichen Commitments erh\u00e4lt. Damit ist der Beweis auch kein Zero-Knowledge-Beweis, denn nat\u00fcrlich funktioniert dies nicht bei einer Aufzeichnung, die sich Walter ausgedacht hat.<\/p>\n

Mein erster Gedanke war, dass sich dieses Problem l\u00f6sen l\u00e4sst, indem beim \u00d6ffnen eines Commitments nicht die Liste der nicht zugeordneten Farben genannt wird, sondern lediglich das Ergebnis, wenn man alle nicht zugeordneten Farben zusammenmischt. Dann k\u00f6nnte man nicht mehr durch Ausprobieren und Weglassen einzelner Farben beim Nachmischen ein urspr\u00fcngliches Commitment erhalten. Das w\u00fcrde zwar die Zero-Knowledge-Eigenschaft des Beweises retten, aber leider w\u00e4re damit das Commitment nicht mehr verbindlich. Denn beim \u00d6ffnen lie\u00dfe sich nicht mehr \u00fcberpr\u00fcfen, ob Bob tats\u00e4chlich nur genau eine zugeordnete Farbe verwendet hat. Dies ist aber die Voraussetzung f\u00fcr die Verbindlichkeit des Commitments. Kleine \u00c4nderungen 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.<\/p>\n

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

Wir haben gesehen, woher der Begriff Zero-Knowledge-Beweis<\/b> kommt und warum ich es ein interaktives Beweis-System genannt habe.
\nEine m\u00f6gliche Anwendung f\u00fcr Zero-Knowledge-Beweise ist die Authentifizierung. In den meisten F\u00e4llen authentifiziert sich ein Computer (Client) bei einem anderen (Server), indem der Client ein Passwort an den Server \u00fcbersendet und der Server dies mit einem gespeicherten Wert abgleicht. Verschl\u00fcsselung sch\u00fctzt das Passwort bei der \u00dcbertragung und eine Hashfunktion verhindert, dass der Server das Passwort direkt speichert (um es vor Diebstahl zu sch\u00fctzen). Diese Schutzma\u00dfnahmen werden hinf\u00e4llig, 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\u00e4hrt.<\/p>\n

Die Authentifizierung ist aber bei Weitem nicht die einzige Anwendungsm\u00f6glichkeit f\u00fcr Zero-Knowledge-Beweise. Tats\u00e4chlich sind sie ein m\u00e4chtiges Werkzeug der Kryptologie und erm\u00f6glichen 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\u00e4hler seine Stimme an einem Wahlcomputer abgibt und einen Beleg erh\u00e4lt. Mit diesem Beleg kann der W\u00e4hler kontrollieren, dass seine Stimme korrekt gez\u00e4hlt wurde, sogar wenn der Wahlcomputer manipuliert wurde und versucht, die Wahl zu verf\u00e4lschen. Wer mehr zu Bingo Voting erfahren m\u00f6chte, dem empfehle ich die Wikipedia-Seite von Bingo Voting<\/a> als Einstieg.<\/p>\n","protected":false},"excerpt":{"rendered":"

Dieser Artikel ist Teil des ScienceBlogs Blog-Schreibwettbewerb 2017. Informationen zum Ablauf gibt es hier. Leserinnen und Leser k\u00f6nnen die Artikel bewerten und bei der Abstimmung einen Preis gewinnen – Details dazu gibt es hier. Eine \u00dcbersicht \u00fcber alle am Bewerb teilnehmenden Artikel gibt es hier. Informationen zu den Autoren der Wettbewerbsartikel finden sich in den […]<\/p>\n","protected":false},"author":1,"featured_media":24109,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[733,11],"tags":[2666],"class_list":["post-24383","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-blog-schreibwettbewerb","category-naturwissenschaften","tag-blog-schreibwettbewerb"],"_links":{"self":[{"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/posts\/24383","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/comments?post=24383"}],"version-history":[{"count":1,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/posts\/24383\/revisions"}],"predecessor-version":[{"id":24389,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/posts\/24383\/revisions\/24389"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/media\/24109"}],"wp:attachment":[{"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/media?parent=24383"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/categories?post=24383"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/tags?post=24383"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}