Avi Wigderson und der Einbruch des Zufalls in das Reich der Beweise

Christoph Pöppe

Das erste Mal, dass mir der Name Avi Wigderson begegnete, war gleich ein feierlicher Anlass. Auf dem internationalen Mathematiker-Kongress in Zürich 1994 wurde ihm der Nevanlinna-Preis verliehen, eine Auszeichnung für Leistungen auf Weltniveau in der theoretischen Computerwissenschaft. Der Preis war nach dem Vorbild der Fields-Medaille in der Mathematik gebaut; insbesondere durfte der Preisträger am 1. Januar des Verleihungsjahres noch nicht 40 Jahre alt sein. Damals wurde unter anderem eine Erfindung Wigdersons ausgezeichnet, die als „zero-knowledge proof“ („Beweis mit null Ahnung“) bekannt geworden ist.

Inzwischen hat der junge Mann das gesetzte Alter von 65 erreicht – und den Abelpreis gewonnen. Der ist nach dem Vorbild des Nobelpreises konstruiert und wird typischerweise für ein wissenschaftliches Lebenswerk verliehen. Und in der Tat: Da ist in den letzten 27 Jahren noch allerlei dazugekommen. In seinem Vortrag auf dem letzten Heidelberg Laureate Forum bot Wigderson ein absolut überwältigendes Panorama der letzten Erkenntnisse aus der theoretischen Computerwissenschaft. Es ist aussichtslos, das hier auch nur ungefähr zu referieren. Aber ein paar Highlights will ich versuchen zu vermitteln. Für alle, die es genauer wissen wollen: Wigderson hat der Welt sein Buch „Mathematics and Computation“ geschenkt, in dem er diese neueren Entwicklungen umfassend beschreibt.

Was hat es mit dem Null-Ahnungs-Beweis auf sich? Ich (der „Beweiser“, „prover“) kann einem Gegenüber (dem „Prüfer“, „verifier“) etwas beweisen: eine mathematische Gleichung, ein ganzes Theorem oder auch nur die Tatsache, dass ich ein Geheimnis kenne. Und zwar so, dass der Prüfer von der Richtigkeit meiner Behauptung überzeugt ist, ohne von meinem Rechenweg, meiner Argumentation, meinem Geheimnis irgendetwas in Erfahrung gebracht zu haben! Ich könnte meiner Bank klarmachen, dass ich meine Geheimzahl kenne, ohne dass ich sie, wie heute üblich, in irgendein mir unbekanntes Gerät eintippen müsste. Das wäre durchaus hilfreich, denn damit müsste ich nicht mehr fürchten, dass jemand das Gerät manipuliert hat, so dass er die Geheimzahl mitlesen und sich hinterher gegenüber der Bank für mich ausgeben kann.

Aber wie soll das gehen? Im Prinzip so, dass der Prüfer dem Beweiser Fragen stellt, die dieser nur dann richtig beantworten kann, wenn er das Geheimnis kennt. Da die Computerwissenschaftler immer in Bits denken, soll es sich um Fragen handeln, auf die man nur mit 1 oder 0 („Ja“ oder „Nein“) antworten kann. Natürlich kann ein falscher Beweiser auf eine Frage irgendeine beliebige Antwort geben und damit, wenn er Glück hat, den Prüfer täuschen. Das gelingt ihm mit einer Wahrscheinlichkeit von 50 Prozent – bei der ersten Frage. Jede weitere Frage halbiert die Wahrscheinlichkeit des Gelingens, und nach der hundertsten richtig beantworteten Frage wird kein vernünftiger Prüfer mehr auf die Idee kommen, dass ein Betrüger am anderen Ende der Leitung sitzt. Man gewinnt also keine absolute Sicherheit, kommt aber der absoluten Sicherheit beliebig nahe. Und wem das nicht reicht, der hat die Freiheit, noch ein paar Fragen mehr zu stellen.

Aber das schwierigere Problem kommt erst noch: Welche Fragen darf der Prüfer überhaupt stellen? Die nur mit Kenntnis des Geheimnisses richtig zu beantworten sind, ihm selbst aber keine Information über das Geheimnis bringen? „Ist deine Geheimzahl gerade?“ scheidet jedenfalls aus; noch ein paar Fragen dieser Machart („Ist die erste Binärziffer deiner Geheimzahl eine Eins?“), und der Prüfer kann sich die Zahl zurechtbasteln. Jede Frage der Art „Wenn du diese wilde Berechnung mit deinem Geheimnis anstellt, kommt dann eine Eins heraus?“ ist unzulässig; der Prüfer könnte ja den Rechenweg – den er kennt, weil er ihn selbst vorgegeben hat – zurückgehen und, vielleicht zusammen mit den anderen bereits vorliegenden Antworten, das Geheimnis ermitteln.

Es sei denn, Zurückrechnen wäre unmöglich. Das würde heißen, man kann einen Rechenschritt nicht eindeutig umkehren. Zum Beispiel Quadrieren. Wurzelziehen ist keine eindeutige Umkehrung; es könnte ja auch die negative Wurzel gewesen sein. Dann gäbe es zwei verschiedene Geheimzahlen, die beide jedesmal die richtige Antwort produzieren, und der Prüfer wüsste nicht, ob der Beweiser die richtige oder die falsche Geheimzahl hat.

Nun stellt sich heraus: Zurückrechnen muss gar nicht grundsätzlich unmöglich sein. Es genügt, wenn es praktisch unmöglich ist. In der Sprache der Computerwissenschaftler ausgedrückt: Die Umkehrfunktion existiert zwar, ist aber nicht „effektiv“, das heißt in erträglicher Zeit, berechenbar. Solche „Einwegfunktionen“, also leicht zu berechnende Funktionen, deren Umkehrung schwer ist, dienen in der Tat als universelles Mittel für die verschlüsselte Kommunikation.

Leichte und schwere Probleme

Ein Problem ist umso schwerer, je mehr Zeit seine Lösung in Anspruch nimmt. Aber wie bestimmt man einen prinzipiellen Unterschied zwischen leichten und schweren Problemen? Was ist eine erträgliche Zeit? Eine Angabe in Sekunden ist wenig hilfreich. Stattdessen geben die Computerwissenschaftler an, wie stark der Rechenaufwand mit der Größe des Problems anwächst, und die wiederum ist definiert als die Anzahl der Zeichen (zum Beispiel Binärziffern), die man benötigt, um das Problem zu beschreiben. Die Aufgabe „Multipliziere zwei tausendstellige Zahlen“ ist also von der Größe g=2000. Eine Aufgabe, deren Rechenzeitbedarf proportional einer Potenz gⁿ (mit einer natürlichen Zahl n) ist, gilt als leicht. Man sagt, das Ergebnis ist effektiv oder auch „in polynomialer Zeit“ berechenbar. Zum Beispiel ist beim Multiplizieren n=2. Wenn die Größe g allerdings im Exponenten steht, also zum Beispiel der Rechenzeitaufwand proportional zu 2^g ist, nennt man die Aufgabe schwer.

Wenn die beiden tausendstelligen Zahlen Primzahlen sind, dann ist die Umkehrung ihrer Multiplikation eine wohldefinierte Aufgabe: Zerlege eine (sagen wir ungefähr 2000-stellige) Zahl in ihre Primfaktoren. Und während das Multiplizieren leicht ist, ist das Zerlegen („Faktorisieren“) schwer. Es gibt nämlich keinen wesentlich besseren Weg, als alle Möglichkeiten der Reihe nach durchzuprobieren, und deren Anzahl ist größenordnungsmäßig gleich einer Konstante mal 2 hoch die Anzahl der Stellen (wir denken wieder in Binärzahlen).

Wer sich auskennt (oder einen alten Artikel von Thomas Beth zum Thema liest), kann mit den folgenden Stichworten etwas anfangen: In endlichen Körpern ist die Exponentiation (f(x)=a^x mit einer Konstanten a) leicht zu berechnen. Deren Umkehrung (der „diskrete Logarithmus“) ist schwer.

Ein anderes Prinzip des „ahnungslosen Beweisens“ erklärt Wigderson anhand eines mathematischen Sachverhalts aus der Graphentheorie. Ein Graph ist zunächst nur eine Sammlung von Punkten (den „Knoten“) und Strichen („Kanten“), die jeweils zwei Knoten miteinander verbinden. Es soll aber nicht darauf ankommen, wo Knoten und Kanten auf dem Papier liegen. Man darf also die Knoten beliebig hin- und herschieben, wobei die Kanten gummifädenartig mitgezogen werden, und es bleibt eigentlich derselbe Graph.

Im Computer ist dementsprechend ein Graph nichts weiter als eine Liste von Zahlenpaaren, etwa (1, 2), (1, 3), (2, 5), …, was bedeutet, dass eine Kante von Knoten Nummer 1 zu Knoten Nummer 2 verläuft, eine von 1 nach 3, eine weitere von 2 nach 5 und so weiter. Natürlich soll es nicht darauf ankommen, in welcher Reihenfolge die Knoten nummeriert sind. Das heißt, zwei Graphen (Kantenlisten) gelten auch dann als im Wesentlichen gleich („isomorph“), wenn sie durch Umnummerieren auseinander hervorgehen.

Zu entscheiden, ob zwei vorgelegte Graphen isomorph sind, ist schwer. Wenn die beiden nicht offensichtlich nicht-isomorph sind (unterschiedliche Gesamtzahl von Knoten, von Kanten oder so), bleibt einem nämlich nicht viel anderes übrig, als sämtliche Permutationen der Zahlen von 1 bis n (Anzahl der Knoten) daraufhin durchzuprobieren, ob bei einer dieser Umnummerierungen des ersten Graphen der zweite herauskommt.

Angenommen, jetzt kommt ein genialer Meister, dessen Rechenfähigkeiten wir nicht kennen, legt zwei Graphen vor und behauptet, sie seien erstens nicht isomorph, und zweitens könne er das beweisen. Aber er will den Beweis nicht herausrücken. Wie können wir mit unseren beschränkten Fähigkeiten – wir können nur leichte Probleme lösen – uns trotzdem davon überzeugen, dass seine Behauptung zutrifft?

Das geht relativ einfach. Nennen wir die beiden Graphen G und H. Wir (der Prüfer) werfen eine Münze, wählen abhängig vom Ergebnis entweder G oder H aus und nummerieren die Knoten des gewählten Graphen irgendwie um, mit einer Permutation, die wir ebenfalls zufällig auswählen. Den so errechneten Graphen K legen wir dem Beweiser vor und fragen „Zu welchem der beiden Graphen G und H ist er isomorph?“

Wenn er die richtige Antwort gibt, uns also auf den Kopf zusagt, wie die Münze gefallen ist, dann ist das zumindest ein Indiz für die Richtigkeit seiner Behauptung. Die Permutation anzuwenden ist leicht, sie ausfindig zu machen ist schwer. Der Beweiser hat also gezeigt, dass er die schwere Aufgabe lösen kann. Wenn er mit seiner ersten Behauptung gelogen hat, dann sind sowieso alle drei Graphen, G, H und K, isomorph, und die Antwort auf unsere Frage kann bestenfalls geraten sein.

Natürlich kann er, mit Wahrscheinlichkeit 50 Prozent, richtig geraten haben. Aber jetzt wiederholen wir das Frage-Antwort-Spiel, sagen wir hundertmal. Damit sinkt die Wahrscheinlichkeit, dass der Beweiser gelogen hat, auf 2^–100, und wenn uns das nicht reicht, fragen wir noch ein paarmal. Vor allem aber: Dieser Beweis ist echt zero-knowledge! Denn aus den Antworten des Beweisers haben wir nur gelernt, was wir längst wussten, nämlich das Ergebnis des jeweiligen Münzwurfs, und sonst gar nichts.

Es bleibt also ein beliebig kleines Restrisiko. Damit könnte eine Bank ohne weiteres leben. Wenn aber das Geheimnis in einem mathematischen Satz besteht: Würden wir den Satz als korrekt akzeptieren, ohne den Beweis selbst gesehen zu haben? Da müssten die Mathematiker schon sehr hart schlucken. Aber: Die Anzahl der beweisbaren Sätze wächst stark an, wenn man diese Beweismethode akzeptiert. Das könnte auf die Dauer auch den traditionell gesinnten Fachvertretern die Kröte schmackhaft machen.

Und die Reichweite dieser Erweiterung ist größer, als es auf den ersten Blick scheint. Die Probleme der theoretischen Computerwissenschaft haben es nämlich so an sich, dass man sehr häufig eines in ein anderes umrechnen kann, und zwar „leicht“, das heißt mit polynomialem Aufwand. Auf diese Weise findet sich eine praktische Bedeutung selbst für das Graphenisomorphieproblem – das nun wirklich nicht so aussieht. Neue Beweismethoden führen zur Definition neuer Problemklassen, und immer wieder stellt sich heraus, dass eine neue Klasse gleich einer anderen, altbekannten ist. Das heißt: Für gewisse Probleme, die bislang als irgendwie schwer galten (und damit zur entsprechenden Problemklasse zählten), gibt es jetzt mit den zufallsabhängigen und Frage-Antwort-Spiel-Verfahren eine neue, geschicktere Lösungsmethode.

Die wesentlichen Zutaten der neuen Verfahren sind einerseits der Zufall, andererseits die Existenz von Einwegfunktionen. Den Zufall schenkt uns die Natur in Gestalt der Ereignisse aus der Quantenmechanik, die „echten Zufall“ enthalten (und nicht nur eine Beschreibung unserer Unwissenheit). Mit den Einwegfunktionen ist es schwieriger. Es ist nicht ausgeschlossen, dass es zur Faktorisierung oder zur Berechnung des diskreten Logarithmus effektive Verfahren gibt und nur unser beschränkter Verstand uns bislang daran gehindert hat, sie zu finden. Diese Frage ist in der Kurzform „P≠NP?“ eines der noch ungelösten „Jahrtausendprobleme“. Aber dass sie mit „P=NP“ beantwortet wird, dass also alle schweren Probleme in Wirklichkeit doch leicht sind, glaubt eigentlich niemand mehr ernsthaft.

The post Avi Wigderson und der Einbruch des Zufalls in das Reich der Beweise originally appeared on the HLFF SciLogs blog.