Ein Ziel der Komplexitätstheorie ist der Nachweis, dass Probleme nicht effizient gelöst werden können. Solche Ergebnisse wirken oft "negativ" und nicht wünschenswert. Dieser Beitrag beschäftigt sich mit ihrem "positiven" Aspekt, den Anwendungen der Ineffizienz. Während man normalerweise möglichst effiziente Algorithmen zur Lösung von Problemen entwickeln will, ist man in der Kryptographie gerade im Gegenteil daran interessiert, die Ineffizienz bestimmter Probleme nachzuweisen und anzuwenden: Ein Beweis der Ineffizienz gewisser Probleme bedeutet hier einen Zuwachs an Sicherheit in der Übertragung verschlüsselter Nachrichten. In diesem Beitrag werden Protokolle für den Schlüsseltausch und digitale Signaturen vorgestellt sowie die kryptographischen Grundbausteine solcher Protokolle, wie z. B. "Einwegfunktionen", beschrieben. Wir gehen auch auf das ganz aktuelle Thema der Zero-Knowledge-Protokolle ein. Das sind kryptographische Protokolle, die es erlauben, dass keinerlei Information ungewollt preisgegeben wird: Mit einem Zero-Knowledge-Protokoll kann Alice Bob davon überzeugen, dass sie ein gewisses Geheimnis kennt, ohne auch nur den geringsten Teil dieses Geheimnisses zu verraten.

Protokolle für den Schlüsseltausch und digitale Signaturen

Stellen wir uns die folgende Situation vor: Alice und Bob möchten Botschaften über einen unsicheren Kanal, wie z. B. eine öffentliche Telefonleitung, austauschen, wobei sie von Erich belauscht werden:

Deshalb wollen Alice und Bob ihre Botschaften verschlüsseln. Damit die Verschlüsselung effizient ist, entscheiden sie sich für ein symmetrisches Kryptosystem, in dem also der Schlüssel für die Verschlüsselung derselbe ist wie der für die Entschlüsselung. Aber wie können sie sich dann auf einen gemeinsamen geheimen Schlüssel einigen, wenn sie nur über einen unsicheren Kanal kommunizieren können? Würden sie eine verschlüsselte Botschaft verschicken, die den künftig zu benutzenden Schlüssel enthält, ergibt sich die Frage: Mit welchem Schlüssel soll diese Botschaft verschlüsselt werden?

Diese Situation, die ein wenig an das bekannte Paradoxon von dem Ei und der Henne erinnert, ist als das Problem des Schlüsseltauschs (engl.: secret-key agreement problem) bekannt, das über Jahrtausende – seit Beginn der Kryptographie – als nicht lösbar galt. Es war eine ziemliche Überraschung, als 1976 Whitfield Diffie und Martin Hellman² eine Lösung dieses lange offenen, paradox wirkenden Problems vorschlugen: das allererste secret-key agreement-Protokoll. Ihr Protokoll wird in Abbildung 1 dargestellt. Interessanterweise, und das ist das eigentlich Paradoxe am Diffie-Hellman-Protokoll, inspirierte dieses die Erfindung des RSA-Systems durch Rivest, Shamir und Adleman³. RSA ist das historisch erste Public-Key-Kryptosystem; auch heute noch ist es weit verbreitet. Das heißt, mit der Lösung des für die symmetrische Kryptographie wichtigen Schlüsseltauschproblems öffneten Diffie und Hellman die Tür zur asymmetrischen (oder public-key) Kryptographie, in der keine geheimen Schlüssel mehr über unsichere Kanäle verschickt werden müssen.

Eine andere Aufgabe in der Kryptographie ist die Erstellung digitaler Signaturen. Diese werden zur Authentifizierung von Dokumenten, wie z. B. E-Mails, benötigt. Das Ziel ist sicherzustellen, dass weder Erich noch Bob die digitale Unterschrift von Alice fälschen können. Alice möchte ihre verschlüsselten Nachrichten an Bob so signieren, dass (a) Bob verifizieren kann, dass tatsächlich sie die Absenderin war, und (b) auch Dritte, die womöglich kein Vertrauen in Bob haben, sich von der Echtheit ihrer Unterschrift überzeugen können. Die Eigenschaft (a) leisten bereits die symmetrischen Authentikationscodes; die spezifische Asymmetrie der digitalen Signaturen kommt erst in der Eigenschaft (b) zum Ausdruck. Diese Eigenschaft (b) ist es, die die digitalen Signaturen beispielsweise für den sicheren E-Commerce nützlich und notwendig macht, denn dort sind Interessenskonflikte zwischen Alice und Bob zu erwarten.

Diffie-Hellman-Protokoll für den Schlüsseltausch

---

---

Abbildung 1 zeigt das Diffie-Hellman-Protokoll. Es beruht auf der modularen Exponentialfunktion mit Basis g und Modulus p, wobei p eine Primzahl und g eine primitive Wurzel von p in Z_p^* ist, der zyklischen Gruppe der primen Reste modulo p. Etwas formaler: Z_p^* ist die Menge aller natürlichen Zahlen a mit 1 < a < p - 1, die teilerfremd zu p sind. Z_p^* hat die Ordnung (p) = p- 1, wobei die Eulersche Funktion ist. Der Satz von Euler sagt, dass für alle n N und für alle a Z_n^* gilt: a⁽ⁿ⁾ 1 mod n. Der Spezialfall, bei dem n eine Primzahl p ist, die a nicht teilt, ist bekannt als der "Kleine Fermat": Ist p eine Primzahl und a Z_p^*, so gilt a^p-1 1 mod p. Eine primitive Wurzel von p ist jedes Element a Z_p^*, so dass für jedes d mit 1 < d < (p) gilt: a^d / 1 mod p. Die Funktion _(g,p) : Z_p^* Z_p^*, die definiert ist durch

heißt modulare Exponentialfunktion mit Basis g und Modulus p. Ihre Umkehrfunktion, die für fixiertes p und g den Wert _(g,p)(a) auf a = log _g mod p abbildet, heißt der diskrete Logarithmus. Das Protokoll ist korrekt, da in der Arithmetik modulo p gilt:

Die Sicherheit des Diffie-Hellman-Protokolls beruht auf der (unbewiesenen, aber plausiblen) Annahme, dass die Berechnung diskreter Logarithmen eine sehr schwere Aufgabe ist. Im Gegensatz dazu kann die modulare Exponentialfunktion mit der square-and-multiply-Methode effizient berechnet werden. Deshalb wird diese Funktion als eine Einwegfunktion betrachtet, eine Funktion, die zwar leicht zu berechnen, aber nur schwer zu invertieren ist. Einwegfunktionen spielen eine wichtige Rolle in der Kryptographie.

Wenn Erich die Kommunikation von Alice und Bob aufmerksam belauscht, dann kennt er p, g, und . Er möchte ihren gemeinsamen geheimen Schlüssel k_A = k_B berechnen. Könnte er das Problem des diskreten Logarithmus effizient lösen, dann könnte er leicht a = log _g mod p und b = log _g mod p und somit k_A = ^a mod p und k_B = ^b mod p berechnen. Glücklicherweise ist dieses Problem, wie oben erwähnt, schwer, und folglich ist diese Attacke keine wirkliche Bedrohung. Allerdings gibt es für das Diffie-Hellman-Protokoll bis heute keinen "Beweis der Sicherheit". Das unmittelbare Berechnen des Schlüssels k_A = k_B aus und ist nicht die einzige mögliche Attacke auf das Diffie-Hellman-Protokoll. Zum Beispiel ist es verwundbar durch die man-in-the-middle-Attacke, bei der sich Erich gegenüber Alice als Bob und Bob gegenüber als Alice ausgibt. Diese Attacke wirft das Problem der Authentifizierung von Personen – im Gegensatz zu Dokumenten – auf, wobei wir unter einer "Person" im weitesten Sinn eine Instanz verstehen wollen, die ihr Wissen oder beliebige andere Informationen aktiv an andere Instanzen weitergeben kann. Eine "Person" in unserem Sinne könnte also auch ein Computer sein, der so programmiert ist, dass er einem anderen Computer seine Daten übermittelt. Insofern unterscheidet sich unser Begriff der Authentifizierung von Personen etwa von der biometrischen Authentifizierung natürlicher Personen. Wir kommen auf die man-in-the-middle-Attacke und das aus ihr resultierende Authentikationsproblem für Personen später zurück.

ElGamal (1997) modifizierte das Protokoll von Diffie und Hellman, um sowohl ein Public-Key-Kryptosystem als auch ein Protokoll für digitale Signaturen zu entwickeln. Eine besonders effiziente Variante dieses Protokolls, die auf eine Idee von Schnorr⁴ zurückgeht, ist heute der Digital Signature Standard⁵ der USA.

Rivest-Sherman-Rabi-Protokolle für Schlüsseltausch und digitale Signaturen

Ron Rivest, Alan Sherman und Muhammad Rabi entwickelten andere Protokolle für den Schlüsseltausch und für digitale Signaturen. Das Schlüsseltausch-Protokoll aus Abbildung 2 geht auf Rivest und Sherman zurück⁶. Rabi und Sherman (1997) modifizierten es zu einem Protokoll für digitale Signaturen, welches in Abbildung 3 dargestellt ist.

---

---

Der entscheidende Grundbaustein beider Protokolle ist eine stark nichtinvertierbare, assoziative Einwegfunktion. Eine totale (d. h. überall definierte) zweistellige Funktion heißt assoziativ, falls für alle x, y und z gilt: (xy)z = x(yz).⁷ Die Assoziativität von sichert, dass Alice und Bob denselben Schlüssel berechnen: k_A = k_B. Wie oben erwähnt, lassen sich Einwegfunktionen leicht berechnen, aber nur schwer invertieren. Eine zweistellige Einwegfunktion heißt stark nichtinvertierbar, falls sie selbst dann schwer invertierbar ist, wenn zusätzlich zum Funktionswert eines ihrer Argumente gegeben ist. Im traditionellen Modell der worst-case-Komplexität versteht man unter "schwer invertierbar", dass kein Polynomialzeit-Algorithmus in der Lage ist, für jedes Element z aus dem Bild der Funktion eines der Urbilder von z zu berechnen. Die starke Nichtinvertierbarkeit von sichert, dass Erich, der ja in den Protokollen sowohl einen Funktionswert als auch eines der zugehörigen Argumente erlauschen kann, das jeweils andere zugehörige Argument nicht leicht ermitteln kann.

---

---

Der Begriff der komplexitätstheoretischen (d. h. worst-case) Einwegfunktion geht auf Grollmann und Selman (1988) zurück, die die Existenz verschiedener Typen von worst-case-Einwegfunktionen durch Separationen geeigneter Komplexitätsklassen charakterisierten⁸. Beispielsweise ist bekannt, dass solche Einwegfunktionen genau dann existieren, wenn PNP, wobei P die Klasse der in Polynomialzeit lösbaren Probleme und NP die Klasse der in nichtdeterministischer Polynomialzeit lösbaren Probleme bezeichnet. Folglich kann man an die Existenz von worst-case- Einwegfunktionen mit derselben Gewissheit glauben, mit der man an die Gültigkeit der Hypothese PNP glaubt. Mit Euler könnte man, in leichter Abwandlung seines Ausspruchs⁹, sagen: "PNP, also existieren Gott und Einwegfunktionen!"

Doch kehren wir zurück zu den Protokollen. Die entscheidende Frage hier ist: Gibt es denn Einwegfunktionen mit all diesen schönen Eigenschaften? Die Antwort auf diese Frage scheint heute und in der nahen Zukunft noch nicht möglich zu sein; schließlich impliziert die Existenz von beliebigen Einwegfunktionen (also solchen ohne diese Eigenschaften) die Ungleichheit von P und NP, und ein Beweis der Vermutung "PNP" konnte in über dreißig Jahren intensiver Forschung nicht erbracht werden.

Etwas bescheidener fragen wir also: Kann man Einwegfunktionen mit diesen schönen Eigenschaften wenigstens aus beliebigen Einwegfunktionen (äquivalent: aus der Annahme PNP) konstruieren? Obwohl Rabi und Sherman (1997) bewiesen, dass assoziative Einwegfunktionen im worst-case-Modell genau dann existieren, wenn PNP, ließen sie die Frage offen, ob irgendeine natürliche komplexitätstheoretische Bedingung hinreichend für die Existenz starker, totaler, kommutativer und assoziativer Einwegfunktionen ist.¹⁰ Hemaspaandra und Rothe (1999) beantworten (ebenfalls im worst-case-Modell) diese Frage: Stark nichtinvertierbare, totale, kommutative und assoziative Einwegfunktionen existieren genau dann, wenn PNP.

Für die meisten kryptographischen Anwendungen genügt das worst-case-Modell nicht. Statt dessen wird das Modell der average-case-Komplexität zugrunde gelegt und gefordert, dass nicht einmal randomisierte Algorithmen in der Lage seien, Einwegfunktionen mit vernünftig beschränkter Fehlerwahrscheinlichkeit zu invertieren. Dies für stark nichtinvertierbare, assoziative Einwegfunktionen zu leisten ist eine interessante Aufgabe künftiger Forschung. Und es besteht Hoffnung: Ajtai (1996) zeigte die Äquivalenz der worst-case- und der average-case-Komplexität für das NP-harte Shortest Lattice Vector Problem.

Interaktive Beweissysteme und Zero-Knowledge- Protokolle

Im Zusammenhang mit dem Diffie-Hellman-Protokoll wurde die man-in-the-middle- Attacke erwähnt. Stellen wir uns vor, dass Bob sich gerade mit seiner Partnerin über eine öffentliche Telefonleitung auf einen gemeinsamen geheimen Schlüssel geeinigt hat. Bob war so clever, das Diffie-Hellman-Protokoll zu verwenden, und so glaubt er, dass Erich über den von ihnen gewählten geheimen Schlüssel keine Ahnung hat:

Aber Erich war noch schlauer. In Wirklichkeit ist dies passiert:

Diese Situation wirft die Frage der Authentifizierung von Personen auf: Wie kann sich Bob sicher sein, dass es tatsächlich Alice war, mit der er kommunizierte, und nicht Erich, der sich als Alice ausgab? Anders gesagt, wie kann Alice zweifelsfrei ihre Identität beweisen? Eine Möglichkeit, dieses Ziel zu erreichen, ist es, mit Alice eine geheime Information zu verknüpfen. Das könnte z. B. ihre PIN ("Personal Identification Number") sein oder irgendein anderes privates Geheimnis, das niemandem außer ihr bekannt ist. Diese Information nennen wir Alice’ Geheimnis.

Aber hier ist noch ein Haken. Alice möchte gern Bob von ihrer Identität überzeugen, indem sie beweist, dass sie ihr Geheimnis kennt. Ideal wäre es, wenn sie dabei dieses Geheimnis nicht enthüllen müsste, denn sonst wäre es ja kein Geheimnis mehr: Wüsste Bob Alice’ Geheimnis, so könnte er in der Kommunikation mit einem Dritten so tun, als wäre er selbst Alice. Die Frage ist also: Wie kann man die Kenntnis eines Geheimnisses mitteilen, ohne es zu verraten? Und das ist genau, worum es bei den Zero-Knowledge- Protokollen geht.

Interaktive Beweissysteme

Zero-Knowledge-Protokolle sind spezielle interaktive Beweissysteme; letztere werden zunächst beschrieben. Sie wurden von Shafi Goldwasser, Silvio Micali und Charles Rackoff (1989) eingeführt. Wie in den bisherigen Protokollen betrachten wir die Kommunikation zwischen zwei Parteien, Prover Alice und Verifier Bob:

Vorerst interessieren uns nicht die Sicherheitsaspekte, die hierbei auftreten können, sondern wir sind nur an dem folgenden Kommunikationsproblem interessiert: Alice und Bob wollen gemeinsam ein gegebenes Problem L lösen, d. h., sie wollen entscheiden, ob ein gegebenes Eingabewort zu L gehört. Konkret betrachten wir das Graphisomorphie-Problem: Entscheide, ob ein gegebenes Paar von Graphen isomorph ist. Ein Isomorphismus zwischen zwei ungerichteten Graphen ist eine kantenerhaltende Bijektion zwischen den Knotenmengen der Graphen. GI bezeichne die Menge aller Paare von isomorphen Graphen. Dieses Problem liegt in NP, aber es ist nicht bekannt, ob es NP-vollständig ist, d. h., ob es zu den schwersten NP-Problemen gehört. Andererseits ist kein effizienter Algorithmus bekannt, der es lösen würde, und es gibt eine Reihe von Indizien, die für die Härte dieses Problems sprechen.

Das Kommunikationsproblem von Alice und Bob besteht nun darin, gemeinsam zu entscheiden, ob ein gegebenes Paar (G,H) von Graphen isomorph ist. Alice versucht, ihre Isomorphie durch Angabe eines Isomorphismus zwischen G und H zu beweisen. Sie versucht, Bob von der Isomorphie der Graphen zu überzeugen – unabhängig davon, ob diese Graphen isomorph sind oder nicht. Aber Bob ist misstrauisch. Um die Eingabe zu akzeptieren, will er mit überwältigender Wahrscheinlichkeit überzeugt werden. Noch schlimmer: Bob ist erst dann überzeugt, wenn jede denkbare Prover-Strategie von Alice eine überwältigende Erfolgswahrscheinlichkeit hat. Kann Alice dies leisten, so akzeptiert er, andernfalls lehnt er ab.

Um diese Intuition zu formalisieren, stellen wir uns Alice und Bob als zwei Turingmaschinen vor. Alice ist eine "allmächtige" Turingmaschine A von unbeschränkter Berechnungskraft. Bob ist eine randomisierte Turingmaschine B, die in Polynomialzeit arbeitet. Ein interaktives Beweissystem (oder kurz IP-Protokoll) (A,B) ist ein Protokoll zwischen Alice und Bob. Beide greifen auf dasselbe Eingabeband und auf ein gemeinsames Kommunikationsband zu, und sie haben private Arbeitsbänder für interne Berechnungen. Alice sieht nicht Bobs zufällige Münzwürfe, die seine randomisierte Berechnung beeinflussen. Pr((A,B)(x) = 1) bezeichne – gemäß der zufälligen Wahlen in Bobs und, gegebenenfalls, in Alice’ Berechnung – die Wahrscheinlichkeit, dass Bob die Eingabe x akzeptiert; das heißt, für eine spezielle Folge von Zufallsbits ist "(A,B)(x) = 1" das Ereignis, dass Bob von Alice’ Beweis für x überzeugt ist und akzeptiert. Ein interaktives Beweissystem (A,B) akzeptiert ein Problem L genau dann, wenn für jedes x gilt:

wobei irgendein Prover (d. h. irgendeine Turingmaschine von unbeschränkter Berechnungskraft) ist, die Alice ersetzen kann. Das heißt, im Falle der Akzeptierung genügt es, dass Alice eine Strategie findet, die Bob überzeugt. Im Falle der Ablehnung ist es formal zweckmäßiger, über alle potenziellen Prover zu quantifizieren, anstatt alle potenziellen Strategien von Alice zu betrachten. Die Bedingung (1.1) wird als Vollständigkeit (engl.: completeness) und die Bedingung (1.2) als Verlässlichkeit (engl.: soundness) bezeichnet.

IP bezeichne die Klasse aller Probleme, die von interaktiven Beweissystemen akzeptiert werden können. Die Akzeptierungswahrscheinlichkeiten von wenigstens für x L bzw. von höchstens für x / L sind dabei willkürlich gewählt. Mit den üblichen Techniken zur Wahrscheinlichkeitsamplifikation kann man statt dessen beliebige Konstanten + bzw.  - wählen, wobei > 0. Man kann sogar eine Akzeptierungswahrscheinlichkeit von genau 1 in der Vollständigkeitsbedingung (1.1) fordern, ohne damit die Klasse IP zu verändern ¹¹. In der Literatur findet man für Prover und Verifier auch die Bezeichnungen Merlin und Arthur: Der Begriff der Arthur-Merlin-Spiele¹² ist äquivalent zu dem der interaktiven Beweissysteme.

Was, wenn Bob die Münzen ausgehen? Das heißt, was passiert, wenn er sich deterministisch verhält beim Verifizieren von Alice’ Beweis für "x L"? Wegen ihrer unbeschränkten Berechnungskraft kann Alice Beweise unbeschränkter Länge liefern. Da Bob jedoch eine polynomialzeit-beschränkte Turingmaschine ist, kann er nur Beweise einer in der Größe von x polynomiell beschränkten Länge überprüfen. Folglich ist IP, eingeschränkt auf deterministische Polynomialzeit-Verifizierer, nur eine etwas umständliche Art, die Klasse NP zu definieren. Da GI zu NP gehört, muss dieses Problem also auch zur (nicht eingeschränkten) Klasse IP gehören.

Aber was ist mit GI, dem Komplement von GI? Gibt es ein interaktives Beweissystem, das entscheidet, ob zwei gegebene Graphen nicht isomorph sind? Selbst wenn Alice über unbeschränkte Berechnungskraft verfügt, kann sie dann in Schwierigkeiten kommen, wenn sie die Nicht-Isomorphie zweier Graphen zu beweisen versucht. Betrachten wir z. B. zwei nicht isomorphe Graphen mit jeweils 1.000 Knoten. Ein Beweis für ihre Nicht-Isomorphie verlangt von Alice anscheinend zu zeigen, dass keine der 1000! möglichen Permutationen ein Isomorphismus zwischen den Graphen ist. Nicht nur wäre es für Bob unmöglich, einen so langen Beweis zu überprüfen, auch für Alice wäre es wohl unmöglich, diesen auch nur hinzuschreiben. Schließlich ist 1000! ungefähr 4 ^. 10²⁵⁶⁷. Diese Zahl übersteigt die Anzahl der Atome im gesamten sichtbaren Universum (ohne dunkle Masse), die derzeit auf etwa 10⁷⁷ geschätzt wird, um einen wahrhaft astronomischen Faktor.

Deshalb war es eine Überraschung, als Goldreich, Micali und Wigderson (1991) zeigten: GI ist in IP. Somit enthält IP nicht nur ganz NP, sondern auch ein Problem aus coNP, der Klasse der Komplemente von NP-Problemen. GI liegt vermutlich nicht in NP. Das wirft die Frage auf, wie groß die Klasse IP eigentlich ist. Ein berühmtes Resultat von Adi Shamir (1992) beantwortet diese Frage: IP ist gleich PSPACE, der Klasse der Probleme, die in polynomialem Raum gelöst werden können.

Zero-Knowledge- Protokolle

Nun sind wir soweit, dass wir den Begriff der Zero-Knowledge-Protokolle definieren können, und wollen uns dann der Frage zuwenden, wie sich diese für Authentifizierungszwecke verwenden lassen. Wie oben erwähnt, liegt GI in IP. Um zu beweisen, dass zwei gegebene Graphen isomorph sind, schickt Alice einfach einen Isomorphismus an Bob, den dieser deterministisch in Polynomialzeit verifiziert. Nehmen wir jedoch an, dass Alice geheim halten möchte. Einerseits möchte sie ihr Geheimnis nicht enthüllen; andererseits möchte sie Bob davon überzeugen, dass sie es kennt. Was sie braucht, ist ein ganz spezielles IP-Protokoll, das nichts über ihren geheimen Isomorphismus verrät und dennoch beweist, dass die Graphen isomorph sind. Ein solches Protokoll für GI wird im nächsten Abschnitt angegeben.

Aber was ist ein Zero-Knowledge-Protokoll und wie kann man diesen Begriff formal fassen? Die Intuition ist dies. Stellen wir uns vor, dass Alice eine Zwillingsschwester hat, die Malice heißt und genau wie sie aussieht. Malice kennt jedoch Alice’ Geheimnis nicht. Außerdem verfügt Malice nicht über Alice’ unbeschränkte Berechnungskraft; stattdessen arbeitet sie wie eine randomisierte Turingmaschine, genau wie der Verifizierer Bob. Sie versucht, Alice’ Kommunikation mit Bob zu simulieren. Ein IP-Protokoll hat die Zero-Knowledge-Eigenschaft, falls die Information, die in Malice’ simuliertem Protokoll kommuniziert wird, nicht von der Information zu unterscheiden ist, die in Alice’ Originalprotokoll kommuniziert wird. Malice, die das Geheimnis nicht kennt, kann natürlich keinerlei Information über das Geheimnis in ihr simuliertes Protokoll stecken. Dennoch ist sie in der Lage, einen Klon des Originalprotokolls zu erzeugen, der von einem unabhängigen Beobachter nicht vom Original zu unterscheiden ist. Es folgt, dass der Verifizierer Bob (oder irgendeine andere Partei, wie z. B. der betrügerische Erich) keinerlei Information aus dem Original herausziehen kann. Kurz gesagt: Wo nichts drin ist, kann man auch nichts herausholen.

Diese Intuition kann nun so formalisiert werden: Ein interaktives Beweissystem (A,B) für ein Problem L ist genau dann ein Zero-Knowledge-Protokoll für L, wenn es einen Simulator Malice gibt, so dass gilt:

• Malice arbeitet wie eine randomisierte Polynomialzeit-Turingmaschine M und simuliert Alice’ Protokoll mit Bob, wobei ein simuliertes Protokoll (M,B) entsteht;
• für jedes x L sind die Tupel (a₁,a₂,...,a_k) und (m₁,m₂,...,m_k), die die Kommunikation in (A,B) bzw. in (M,B) repräsentieren, identisch verteilt über die Münzwürfe von A und B im Protokoll (A,B) bzw. von M und B im Protokoll (M,B).

Diese Definition wird in der Literatur als honest-verifier perfect zero-knowledge bezeichnet. Das heißt zum einen, dass in der obigen Definition von einem "ehrlichen" Verifizierer ausgegangen wird; zum anderen, dass man eine "vollkommene" Übereinstimmung (bezüglich der entsprechenden Wahrscheinlichkeitsverteilungen) der kommunizierten Information im simulierten und im Originalprotokoll fordert. In den meisten kryptographischen Anwendungen kann man jedoch nicht voraussetzen, dass Bob immer ehrlich ist. Deshalb modifiziert man die obige Definition durch die stärkere Forderung, dass es für jeden Verifizierer B^* einen Simulator M^* geben soll, der ein vom Originalprotokoll nicht zu unterscheidendes simuliertes Protokoll erzeugt. Andererseits gibt es auch andere, schwächere Begriffe für Zero-Knowledge, bei denen die Ununterscheidbarkeit der kommunizierten Information nicht "perfekt" ist, wie z. B. statistical zero-knowledge und computational zero-knowledge.

Zero-Knowledge- Protokoll für das Graphisomorphie-Problem

---

---

---

---

Oded Goldreich, Silvio Micali und Avi Wigderson (1991) entwickelten das in Abbildung 4 dargestellte Zero-Knowledge-Protokoll für GI. Da bislang nur Zero-Knowledge-Protokolle für Probleme, die sowohl in NP als auch in coNP liegen, bekannt waren und da GI vermutlich nicht in coNP liegt, war ihr Resultat eine Überraschung.

Alice’ Geheimnis im Protokoll ist der von ihr gewählte Isomorphismus . Das Protokoll ist korrekt, weil Alice ihr Geheimnis und die von ihr gewählte zufällige Permutation kennt und somit leicht den Isomorphismus mit (G_b) = H berechnen kann, um Bob ihre Identität zu beweisen. Dabei muss sie ihr Geheimnis nicht verraten. G₁ und G₂ sind isomorph, also gibt es ein A mit Pr((A,B)(G₁,G₂) = 1) = 1, und die Implikation (1.1) gilt. Andererseits hat Alice selbst die beiden Graphen isomorph gewählt, so dass der Fall (G₁,G₂) /GI nicht eintreten kann und die Implikation (1.2) trivialerweise gilt. Somit ist das Protokoll ein interaktives Beweissystem.

Nehmen wir nun an, dass Erich oder Malice betrügen und sich als Alice ausgeben wollen. Sie kennen ihren geheimen Isomorphismus nicht, aber sie kennen die öffentlichen Graphen G₁ und G₂. Sie würden Bob gern davon überzeugen, dass sie Alice’ Geheimnis kennen, das zum Paar (G₁,G₂) passen muss. Wenn Bobs Bit b zufällig mit ihrem zuvor gewählten Bit a übereinstimmt, dann gewinnen sie. Ist jedoch ba, dann erfordert die Berechnung von = o oder = o ^-1 die Kenntnis von . Ohne zu kennen, ist die Berechnung von nur aus den öffentlichen Graphen G₁ und G₂ so gut wie unmöglich, weil GI ein schweres Problem ist, zu schwer selbst für randomisierte Polynomialzeit-Maschinen. Sind die Graphen groß genug gewählt, werden Betrüger wie Malice oder Erich in diesem Falle scheitern.

Da ihre beste Chance ist, das Bit b zu raten, können sie höchstens mit Wahrscheinlichkeit betrügen. Natürlich können sie das Bit b immer raten, und somit ist ihre Chance, erfolgreich zu betrügen, genau . Verlangt Bob, dass, sagen wir, k unabhängige Runden des Protokolls ausgeführt werden, dann wird die Betrugswahrscheinlichkeit so klein wie 2^-k. Es ist also sehr wahrscheinlich, dass ein Betrüger erwischt wird. Nicht mehr als 20 Runden des Protokolls bewirken, dass die Chancen der betrügerischen Malice, unentdeckt davonzukommen, schlechter als eins zu einer Million sind. Folglich ist das Protokoll korrekt.

Es bleibt zu zeigen, dass das Protokoll in Abbildung 4 zero-knowledge ist. Abbildung 5 zeigt ein simuliertes Protokoll mit Malice, die Alice ersetzt, ohne ihr Geheimnis zu kennen. Die Information, die in einer Runde des Protokolls kommuniziert wird, ist durch ein Tripel der Form (H,b,) gegeben. Jedes Mal, wenn Malice ein Bit a mit a = b wählt, sendet sie einfach = an Bob und gewinnt: Bob, oder irgendein anderer unabhängiger Beobachter, wird nicht entdecken, dass sie in Wirklichkeit Malice ist. Im anderen Falle, immer wenn ab gilt, hat Malice Pech. Das ist jedoch überhaupt kein Problem: Sie löscht einfach diese misslungene Runde aus dem simulierten Protokoll und wiederholt den Versuch. In dieser Art und Weise kann sie eine Folge von Tripeln der Form (H,b,) erzeugen, die von der entsprechenden Folge von Tripeln im Originalprotokoll zwischen Alice und Bob nicht zu unterscheiden ist. Es folgt, dass das Protokoll von Goldreich, Micali und Wigderson (1991) für GI die Zero-Knowledge-Eigenschaft hat.

Zero-Knowledge- Protokoll von Feige, Fiat und Shamir

Amos Fiat und Adi Shamir (1986) entwarfen ein Schema zur Authentikation und für digitale Signaturen, welches von Uriel Feige, Fiat und Shamir (1988) zu einem Zero-Knowledge-Identifikationsprotokoll modifiziert wurde. Genauer gesagt entwickelten sie ein Zero-Knowledge-Protokoll für ein zahlentheoretisches Problem, das auf der Annahme beruht, dass das Wurzelziehen in Z_n^* für sehr große Zahlen n praktisch nicht machbar ist. Wegen seiner Eigenschaften ist das Protokoll von Feige, Fiat und Shamir (1988) besonders gut für die Authentifizierung von Nutzern in großen Computer-Netzwerken geeignet. Es ist ein Public-Key- Protokoll, es ist effizienter als die meisten anderen Public-Key-Protokolle, wie z. B. RSA, es kann auf einer Chip-Karte implementiert werden und es ist zero-knowledge. Diese Vorteile führten zu einem raschen Einsatz des Protokolls in praktischen Anwendungen. Das Feige-Fiat-Shamir-Protokoll ist in das "Videocrypt" Pay-TV-System¹³ integriert.

---

---

Das Protokoll von Feige, Fiat und Shamir (1988) ist in Abbildung 6 dargestellt. Es ist korrekt, weil Alice das von ihr gewählte Geheimnis s Z_n^* kennt. Folglich kann sie y = r ^.s^b berechnen, wobei b das von Bob zufällig gewählte Bit ist. Bob akzeptiert Alice’ Identität, weil in Z_n^* gilt:

Nehmen wir nun an, dass Erich oder Malice betrügen und sich als Alice ausgeben wollen. Sie kennen ihr Geheimnis s nicht und ebenso wenig die Primzahlen p und q, aber sie kennen die öffentlichen Zahlen n = pq und v = s² mod n. Sie möchten Bob davon überzeugen, dass sie Alice’ Geheimnis s kennen, die Quadratwurzel von v modulo n. Falls Bob zufällig das Bit b = 0 wählt, so gilt y = r ^. s⁰ = r, und sie gewinnen. Ist jedoch b = 1, dann erfordert die Berechnung eines y mit y² x ^. v mod n die Kenntnis des Geheimnisses s, vorausgesetzt, dass das Berechnen von Quadratwurzeln modulo n für große n sehr schwer ist. Wären Malice oder Erich auch ohne Kenntnis von s dazu in der Lage, die korrekte Antwort sowohl für b = 0 als auch für b = 1 zu geben – sagen wir, y_b mit y_b² x ^. v^b mod n –, dann könnten sie Quadratwurzeln modulo n wie folgt effizient berechnen: die Kongruenzen y₀² x mod n und y₁² x ^. v mod n implizieren ()² v mod n; folglich ist eine Quadratwurzel von v modulo n.

Somit können sie höchstens mit Wahrscheinlichkeit betrügen. Natürlich können sie stets das Bit b zuvor raten und ihre Antwort entsprechend präparieren. Die Wahl von x = r^{2 .} v^-b mod n und y = r impliziert, dass gilt:

(1.3)

In diesem Fall wird Bob keinerlei Irregularität entdecken, und er akzeptiert. Die Betrugswahrscheinlichkeit ist damit exakt und kann wie üblich durch k unabhängige Runden des Protokolls beliebig klein gemacht werden.

Es bleibt zu zeigen, dass das Feige-Fiat-Shamir-Protokoll in Abbildung 6 die Zero-Knowledge-Eigenschaft hat. Abbildung 7 zeigt ein simuliertes Protokoll mit Malice, die Alice ersetzt, ohne ihr Geheimnis s zu kennen. Die Information, die in einer Runde des Protokolls kommuniziert wird, ist durch ein Tripel der Form (x,b,y) gegeben. Zusätzlich zum zufällig gewählten r Z_n^* rät Malice ein Bit c {0,1}, berechnet x = r^{2 .} v^-c mod n und schickt dieses x an Bob. Stimmt c zufällig mit Bobs Bit b überein, so schickt Malice einfach y = r und gewinnt. Ein zur Gleichung (1.3) analoges Argument zeigt dann, dass weder Bob noch irgendein anderer unabhängiger Beobachter den Betrug aufdecken kann:

Im anderen Falle, immer wenn cb gilt, hat Malice Pech. Das ist jedoch überhaupt kein Problem: Sie löscht einfach diese misslungene Runde aus dem simulierten Protokoll und wiederholt den Versuch. In dieser Art und Weise kann sie eine Folge von Tripeln der Form (x,b,y) erzeugen, die von der entsprechenden Folge von Tripeln im Originalprotokoll zwischen Alice und Bob nicht zu unterscheiden ist. Es folgt, dass das Feige-Fiat-Shamir-Protokoll ein Zero-Knowledge-Protokoll ist.

---

---

Abschließende Bemerkungen und vergleichender Ausblick

In diesem Beitrag wurden verschiedene kryptographische Protokolle und Techniken vorgestellt. Diese sind jeweils auf spezifische Szenarien zugeschnitten, die bei der Kommunikation über unsichere Kanäle auftreten können. Speziell wurden Protokolle für den Schlüsseltausch bei symmetrischen Kryptosystemen sowie digitale Signaturen und Zero-Knowledge-Protokolle vorgestellt, und es wurden diesbezügliche Sicherheitsaspekte kurz diskutiert. Im Vordergrund stand dabei die Darstellung der Modelle und der mathematischen Grundlagen kryptographischer Techniken; Aspekte des Security-Engineering, wie etwa der Entwurf von sicheren Public-Key- Infrastrukturen¹⁴, die für die praktische Umsetzung der Modelle erforderlich sind, wurden nicht behandelt.

Natürlich bilden die hier vorgestellten kryptographischen Techniken nur einen kleinen, sehr selektiven Einblick in das weite Feld kryptographischer Anwendungen. So gäbe es etwa über digitale Signaturen, ihre Sicherheitseigenschaften (die auch formal gefasst werden müssen wie in der klassischen Definition in Goldwasser et al. 1988) und ihre Bedeutung in großen Computer-Netzwerken und für sichere Internet-Technologien, noch viel mehr zu sagen. Schöne Übersichtsdarstellungen zu digitalen Signaturen mit Hinweisen zur weiterführenden Literatur findet man z. B. in den Büchern von Stinson (1995), Kapitel 6 und von Buchmann (²2001), Kapitel 11. Für ganz aktuelle Entwicklungen auf diesem sehr aktiven Forschungsgebiet sei beispielhaft auf eine Arbeit von Micali und Reyzin (2002) verwiesen, in welcher eine "exaktere Sicherheit" für dem Fiat-Shamir-Protokoll (Fiat und Shamir 1986) ähnliche Verfahren zur Erstellung digitaler Signaturen untersucht wird.

Ebenso ist das Gebiet der Zero-Knowledge-Protokolle nur kurz angerissen worden. Für eine deutlich tiefer gehende Lektüre und eine mathematisch rigorose Behandlung der Zero-Knowledge-Protokolle sei auf das Kapitel 4 im Buch von Oded Goldreich (2001) verwiesen. Eine schöne und lockere Darstellung findet man in den Büchern von Albrecht Beutelspacher et al. (⁴2001) und Uwe Schöning (1995), von denen die Präsentation konkreter Zero-Knowledge-Protokolle in diesem Beitrag profitierte.

Ein wesentlicher Unterschied zwischen digitalen Signaturen und den Zero-Knowledge- Identifikationsprotokollen liegt darin, dass die einen dem Beweis der Echtheit von Unterschriften unter Dokumenten dienen, während die anderen für die Authentifikation von Personen – von Instanzen, die ihr Wissen aktiv an andere weitergeben können – verwendet werden. Gewissermaßen verhalten sich digitale Signaturen und Zero-Knowledge-Identifikationsprotokolle dual zueinander. Digitale Signaturen leisten deutlich mehr hinsichtlich der Authentizität: (a) sie authentifizieren nicht nur den Urheber einer Nachricht, sondern beweisen auch die Echtheit der Nachricht selbst; (b) die unter (a) genannten Eigenschaften sind transferierbar, d. h., auch Dritte können sich von ihnen überzeugen. Demgegenüber verfolgen Zero-Knowledge- Protokolle ein entgegengesetztes Ziel: (c) sie leisten perfekt und beweisbar die Geheimhaltung des zur Authentikation notwendigen Geheimnisses; (d) das mittels eines Zero-Knowledge-Verfahrens erlangte Wissen bleibt in dem Sinne "geheim", dass es nicht in beweisbarer Form an Dritte weitergegeben werden kann.

Danksagung. Ich danke Andreas Pfitzmann für seine interessanten und sehr hilfreichen Kommentare zu diesem Text und insbesondere zum Vergleich von digitalen Signaturen und Zero-Knowledge-Identifikationsprotokollen, die die Darstellung deutlich verbessert haben.

Bibliographie

AJTAI, M. "Generating hard instances of lattice problems", in: Proceedings of the 28^th ACM Symposium on Theory of Computing. New York 1996, 99-108.

BABAI, L. und S. MORAN. "Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes", Journal of Computer and System Sciences 36(2) (1988), 254-276.

BEUTELSPACHER, A., J. SCHWENK und K. WOLFENSTETTER. Moderne Verfahren der Kryptographie. Braunschweig u. a. ⁴2001.

BUCHMANN, J. Einführung in die Kryptographie. Berlin u. a. ²2001.

DIFFIE, W. und M. HELLMAN. "New directions in cryptography", IEEE Transactions on Information Theory IT-22(6) (1976), 644-654.

ELGAMAL, T. "A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Transactions on Information Theory IT-31(4) (1985), 469-472.

FEIGE, U., A. FIAT und A. SHAMIR. "Zero-knowledge proofs of identity", Journal of Cryptology 1(2) (1988), 77-94.

FIAT, A. und A. SHAMIR. "How to prove yourself: Practical solutions to identification and signature problems", in: Advances in Cryptology—CRYPTO ’86. Heidelberg u. a. 1986, 186-194. (Springer-Verlag Lecture Notes in Computer Science; 263)

GOLDREICH, O., Y MANSOUR und M. SIPSER. "Interactive proof systems: Provers that never fail and random selection", in: Proceedings of the 28^th IEEE Symposium on Foundations of Computer Science. Los Alamitos, Kalifornien, 1987, 449-461.

GOLDREICH, O., S. MICALI und A. WIGDERSON. "Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems", Journal of the ACM 38(3) (1991), 691-729.

GOLDREICH, O. Foundations of Cryptography. Cambridge u. a. 2001.

GOLDWASSER, S., S. MICALI und R. RIVEST. "A digital signature scheme secure against adaptive chosen-message attacks", SIAM Journal on Computing 17(2) (1988), 281-308.

GOLDWASSER, S., S. MICALI und C. RACKOFF. "The knowledge complexity of interactive proof systems", SIAM Journal on Computing 18(1) (1989), 186-208.

GROLLMANN, J. und A. SELMAN. "Complexity measures for public-key cryptosystems", SIAM Journal on Computing 17(2) (1988), 309-335.

HEMASPAANDRA, L. und J. ROTHE. "Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory", Journal of Computer and System Sciences 58(3) (1999), 648-659.

HEMASPAANDRA, L. und J. ROTHE. "Characterizing the existence of one-way permutations", Theoretical Computer Science 244(1-2) (2000), 257-261.

MICALI, S. und L. REYZIN. "Improving the exact security of digital signature schemes", Journal of Cryptology 15(1) (2002), 1-18.

RABI, M. und A. SHERMAN. "An observation on associative one-way functions in complexity theory", Information Processing Letters 64(5) (1997), 239-244.

RIVEST, R., A. SHAMIR und L. ADLEMAN. "A method for obtaining digital signature and public-key cryptosystems", Communications of the ACM 21(2) (1978), 120-126.

ROTHE, J. "Some facets of complexity theory and cryptography: A five-lectures tutorial". Technical Report cs.CC/0111056. Computing Research Repository (CoRR) 2001.
http://xxx.lanl.gov/abs/cs.CC/0111056 (12.9.2002).

ROTHE, J. und L. HEMASPAANDRA. "On characterizing the existence of partial one-way permutations", Information Processing Letters (2002).

SCHNORR, C. "Efficient identification and signature schemes for smart cards", in: CRYPTO ’89. Heidelberg u. a. 1990, 239-251. (Springer-Verlag Lecture Notes in Computer Science; 435)

SCHÖNING, U. Perlen der Theoretischen Informatik. Mannheim 1995.

SHAMIR, A. "IP=PSPACE", Journal of the ACM 39(4) (1992), 869-877.

SINGH, S. Fermat’s Last Theorem. London 1997.

STINSON, D. Cryptography Theory and Practice. Boca Raton 1995.