Das Kinderbuch »Alice im Wunderland« steckt voller verschlüsselter Anspielungen auf anspruchsvolle politische Inhalte. Und tatsächlich beschäftigte sich der Autor, Lewis Carroll, der eigentlich Charles Dodgson hieß, auch in seiner Forscherkarriere mit Verschlüsselungen. Wahrscheinlich würde er sich freuen, dass »Alice« inzwischen in der Informationstheorie als Synonym für einen Sender oder einen Empfänger genutzt wird.

Im Jahr 1868 war Dodgson überzeugt, den Heiligen Gral der Kryptografie ausgemacht zu haben: Er erklärte die seit dem 16. Jahrhundert verwendete Vigenère-Chiffre (siehe »Vigenère-Chiffre«) als unknackbar. Er konnte das zwar nicht beweisen, hatte jedoch gute Gründe für die Aussage. Denn nach mehr als 300 Jahren war seines Wissens noch immer keine effiziente Methode bekannt, um die Chiffre zu brechen.

Es gab nur ein kleines Problem: Fünf Jahre vor Dodgsons wagemutiger Behauptung hatte der preußische Infanteriemajor Friedrich Kasiski die Vigenère-Chiffre in seinem damals kaum beachteten Buch »Die Geheimschriften und die Dechiffrier-Kunst« geknackt.

Kryptografen spielen dieses Katz-und-Maus-Spiel – das Erfinden und Knacken von Codes – schon so lange, wie Menschen geheime Informationen teilen. »Seit Tausenden von Jahren versuchen wir herauszufinden, ob man den Kreislauf durchbrechen kann«, so der Computerwissenschaftler Rafael Pass von der Cornell University.

Vor etwa 50 Jahren kam man einer Antwort auf die Frage erstmals merklich näher. Wie Fachleute damals gezeigt haben, ist es durchaus möglich, nachweislich sichere Chiffren zu erstellen – vorausgesetzt, man hat Zugang zu einer wichtigen Zutat: einer »Einwegfunktion«, die leicht auszuführen, aber nicht oder zumindest nur sehr schwer umzukehren ist. Seitdem haben Forscherinnen und Forscher eine breite Palette an Einwegfunktionen entwickelt, die auf einfacher Multiplikation basieren oder komplizierte geometrische sowie logarithmische Verfahren nutzen und sich aus heutiger Sicht nicht in absehbarer Zeit umkehren lassen. Internetprotokolle wie Transport Layer Security (kurz: TLS) hängen von diesen Funktionen ab; mit ihnen kann man vertrauliche Daten wie Kreditkartennummern oder Anmeldedaten sicher übermitteln.

All das hat das Katz-und-Maus-Spiel allerdings nicht beendet – im Gegenteil: Es hat es nur verschärft. Anstatt sich auf jeden einzelnen Aspekt eines Verschlüsselungsschemas zu fokussieren, mussten sich Kryptografen bloß noch um die zu Grunde liegende mathematische Funktion bemühen. Doch für keines der derzeit verwendeten Beispiele ließ sich endgültig beweisen, dass es sich tatsächlich um eine Einwegfunktion handelt. Schlimmer noch: Man weiß nicht einmal, ob echte Einwegfunktionen existieren. Sollte das nicht der Fall sein, ist jede Art der Kryptografie im Prinzip angreifbar.

Mangels Hinweisen hoffen Programmierer daher einfach darauf, dass die Funktionen, die bisherigen Angriffen standgehalten haben, auch wirklich sicher sind. Es gibt keinen einheitlichen Ansatz, um die Sicherheit der mathematischen Probleme zu untersuchen, »weil jede Variante aus einem anderen Bereich und von einer anderen Expertengruppe stammt«, erklärt der Kryptograf Yuval Ishai vom Technion in Haifa, Israel.

In der Kryptografie fragt man sich seit Langem, ob man auch anders vorgehen könnte, statt sich bloß auf Erfahrungswerte zu stützen. »Gibt es ein Schlüsselargument, etwa ein Problem, das uns verrät, ob sichere Kryptografie möglich ist?«, so Pass. Darauf hat er nun zusammen mit Yanyi Liu, seinem Doktoranden an der Cornell University, eine eindeutige Antwort gefunden: Ja. Ob echte Einwegfunktionen existieren, so bewiesen sie, hängt von einem der ältesten und zentralsten Probleme eines anderen Bereichs der Computerwissenschaft ab, der Komplexitätstheorie. Dabei geht es um die so genannte Kolmogorow-Komplexität, die ein Maß dafür darstellt, wie schwer es ist, zufällige Zahlenfolgen zu identifizieren.

Liu und Pass haben gezeigt: Wenn eine bestimmte Version der Kolmogorow-Komplexität schwer zu berechnen ist, dann existieren echte Einwegfunktionen. In diesem Fall liefern die beiden Informatiker sogar ein Rezept, um solche Abbildungen zu konstruieren. Wenn sich die Komplexität hingegen leicht bestimmen lässt, sind Einwegfunktionen ausgeschlossen – und damit auch sichere Verschlüsselungsverfahren.

Anstatt weiter nach Kandidaten für unumkehrbare Funk­tionen zu suchen, können Fachleute dank dieser Erkenntnis ihre Bemühungen nun ganz auf die Kolmogorow-Komplexität konzentrieren. Zudem vereint die Arbeit von Pass und Liu zwei Bereiche der Informatik: die Komplexitätstheorie und die Kryptografie. Das hat Expertinnen und Experten aus den Gebieten dazu veranlasst, enger zusammenzuarbeiten, was zu vielen neuen Ansätzen geführt hat.

Die Suche nach den schwersten Problemen

In den meisten Forschungsbereichen stellt ein komplexes Problem ein Hindernis dar. Aber in der Kryptografie, wo man die Gegner mit möglichst unüberwindbaren Hürden konfrontieren möchte, ist es ein Segen. 1976 veröffent­lichten Whitfield Diffie und Martin Hellman einen bahn­brechenden Aufsatz: Sie argumentierten, die besondere Schwierigkeit von Einwegfunktionen sei genau das, was die Informatik brauche, um den Anforderungen des heraufdämmernden Computerzeitalters gerecht zu werden. »Wir stehen heute an der Schwelle einer Revolution in der Kryptografie«, schrieben sie in ihrer Arbeit.

Diffie und Hellman entwickelten damals ein völlig neues Verschlüsselungsverfahren. Herkömmliche Methoden basieren darauf, dass zwei Parteien – meist Alice und Bob genannt – einen geheimen Schlüssel teilen und dann darüber sicher kommunizieren. Doch wie tauscht man diesen aus, ohne dass ein Gegner ihn abgreift? Im digitalen Zeit­alter kann man sich nicht mit jeder Partei treffen, um im Vorhinein Informationen zu übergeben.

Die beiden Informatiker schlugen daher die »Public-Key-Kryptografie« vor: Bob besitzt zwei Schlüssel, einen privaten und einen öffentlichen. Wenn Alice ihm eine Nachricht schicken möchte, kann sie diese mit dem öffentlichen Schlüssel chiffrieren (in dieser Richtung lässt sich die Einwegfunktion einfach ausführen). Die Codierung ist nicht umkehrbar, ein Gegner kann aus den Zeichenfolgen nicht auf den ursprünglichen Inhalt schließen – selbst mit Kenntnis von Bobs öffentlichem Schlüssel. Erst sein privater Code ermöglicht es Bob, Alices Nachricht zu dechiffrieren.

In den folgenden Jahrzehnten fanden Forscherinnen und Forscher heraus, wie man Einwegfunktionen für Anwendungen nutzen kann, die über reine Verschlüsselung hinausgehen: etwa um digitale Signaturen zu entwickeln, welche die Identität einer Person verifizieren; um Zufallszahlen zu erzeugen oder »Zero-knowledge«-Beweise zu führen. Letzteres nutzt man, um jemanden zu überzeugen, dass eine Aussage wahr ist, ohne den Beweis selbst preiszugeben. Die Public-Key-Verfahren von Diffie und Hellman erwiesen sich als erstaunlich vielseitig. Aus dem einzigen Baustein der Einwegfunktionen gelang es den beiden Computerwissenschaftlern, zahlreiche bedeutende Prozesse zu entwickeln.

Um die unumkehrbaren Abbildungen besser zu verstehen, kann man sich eine praktische Aufgabe ansehen: etwa jene, zwei große Primzahlen miteinander zu multiplizieren wie 6547 und 7079. Um die Antwort (46 346 213) anzugeben, muss man zwar etwas Fleißarbeit leisten, aber das Ergebnis ist problemlos berechenbar. Würde man Ihnen jedoch die Zahl 46 346 213 nennen und nach den dazugehörigen Primteilern fragen, wären Sie höchstwahrscheinlich ratlos. Denn tatsächlich gibt es keinen – zumindest keinen bekannten – effizienten Weg, große Primfaktoren zu bestimmen. Das macht die Multiplikation zu einem möglichen Kandidaten für eine Einwegfunktion: Solange man von ausreichend hohen Primzahlen ausgeht, ist das Produkt leicht auszuführen, scheint aber schwer rückgängig zu machen. Gesichert ist das allerdings nicht. Jederzeit könnte jemand eine ausgeklügelte Methode finden, um auch große Zahlen schnell zu faktorisieren – so wie es Kasiski irgendwann gelang, die als sicher geltende Vige­nère-Chiffre zu knacken.

Gibt es ein »Hauptproblem«?

Fachleute haben inzwischen zahlreiche mögliche Einwegfunktionen aus verschiedenen Bereichen der Mathematik zusammengetragen. Doch keine davon scheint besser geeignet als eine andere. Wenn man beispielsweise morgen eine Methode finden würde, um die Primfaktorzerlegung effizient auszuführen, würde das nichts über die Gültigkeit der übrigen in Frage kommenden Kandidaten aussagen. Kryptografen suchen schon lange nach einem solchen »Hauptproblem«: eine Funktion, die, wenn sie gebrochen wird, alle anderen Ansätze mit sich in den Abgrund reißt.

1985 fand der Informatiker Leonid Levin von der Boston University ein derartiges Problem – allerdings ein sehr abstraktes. Ihm gelang es, eine universelle, unumkehrbare Abbildung zu definieren, die diese Eigenschaft garantiert besitzt, falls es überhaupt Einwegfunktionen gibt. Könnte man zeigen, dass sein Ansatz gebrochen werden kann, wären auch alle anderen Kandidaten verloren. »Aber seine Funktion war sehr konstruiert«, so der Computerwissenschaftler Eric Allender von der Rutgers University. »Niemand würde sie aus einem anderen Grund studieren, als um ein solches Ergebnis zu erhalten.« Damit rückte man dem Rätsel also nicht wirklich näher.

Gesucht war eine universelle Funktion, die auf ein natürliches Problem zurückgeht – eines, das Aufschluss darüber gibt, ob Einwegfunktionen überhaupt existieren. Und tatsächlich gab es einen viel versprechenden Kandidaten, den Informatiker schon länger ins Auge gefasst hatten: die Kolmogorow-Komplexität, die in den 1960er Jahren als eine Art Maß für Zufälligkeit entwickelt wurde.

2004 stieß Pass als Doktorand erstmals auf den möglichen Zusammenhang und war sofort fasziniert. Im Lauf der Jahre beschäftigte ihn neben seinen sonstigen Forschungsprojekten auch dieses Problem immer wieder, aber ohne viel Erfolg. Dennoch ließ es ihn nicht los. Er war sich sicher, dass die Kolmogorow-Komplexität etwas mit Einwegfunktionen zu tun haben musste. Die Fortschritte im Bereich der Komplexitätstheorie in den letzten Jahren bestärkten ihn, weiter daran zu arbeiten.

Pass versuchte mehrmals, seine Doktoranden zu überreden, die Frage mit ihm zu erforschen. Doch keiner war bereit, sich auf ein Projekt einzulassen, das sich höchstwahrscheinlich als Sackgasse herausstellen würde. Dann lernte er Yanyi Liu kennen, der sein Studium an der Cornell University absolvierte. »Er war furchtlos«, erinnert sich Pass. Gemeinsam stürzten sie sich ins Abenteuer.

Dafür mussten sie zunächst mehr über die Kolmogorow-Komplexität erfahren, die mit dem Konzept des Zufalls zusammenhängt. Zwar hat jeder eine Vorstellung davon, was mit Zufälligkeit gemeint ist. Dennoch ist das Phänomen schwer zu fassen. Es gibt einen »Dilbert«-Comic von Scott Adams, der die Schwierigkeit veranschaulicht. Darin zeigt der Büroleiter seinem Angestellten Dilbert den »Zufallszahlengenerator« der Buchhaltungsabteilung: ein Monster, das einfach nur die Zahl 9 wiederholt. »Sind Sie sicher, dass das wirklich zufällig ist?«, fragt Dilbert. »Das ist das Problem mit dem Zufall«, so der Leiter, »man kann sich nie sicher sein.« Damit hat er Recht: Wenn Ihnen jemand die Zahlenfolgen 99999999999999999999 und 03729563829603547134 zeigt und behauptet, beide seien zufällig erzeugt worden, können Sie das nicht widerlegen: Würden Sie aus einem Topf willkürlich Ziffern ziehen, dann ist die Wahrscheinlichkeit genauso groß, die erste Zeichenkette zu erzeugen wie die zweite. Dennoch fühlt sich die zweite zufälliger an. »Wir glauben zu wissen, was wir meinen, wenn wir über zufällige Phänomene sprechen«, sagt Allender. »Aber erst der Begriff der Kolmogorow-Komplexität hat gezeigt, dass es eine mathematisch sinnvolle Definition dafür gibt.«

Um zufällige Zahlenfolgen besser zu verstehen, beschloss der sowjetische Mathematiker Andrei Kolmogorow (1903–1987) in den 1960er Jahren, sich nicht auf den Prozess zu konzentrieren, der die Zahlen erzeugt, sondern auf die Art, sie zu beschreiben. 99999999999999999999 kann man kurz und bündig als »20 Neunen« bezeichnen, wohingegen es für 03729563829603547134 womöglich keine Definition gibt, die knapper ist als die Zeichenfolge selbst.

Das Problem mit dem Zufall: Man kann sich nie sicher sein, ob etwas wirklich zufällig ist

Kolmogorow hat die Komplexität einer Folge als die Länge des kürzesten Algorithmus definiert, der sie erzeugt. Für Zeichenketten mit 1000 Ziffern können sehr knappe Programme existieren, wie »Gib 1000 Neunen aus«, »Gib die Zahl 23319 aus« oder »Gib die ersten 1000 Ziffern von π unter Verwendung folgender Formel (…) aus«. Andere Folgen lassen sich dagegen nicht kurz beschreiben. Für sie gibt es keine Definition, die kürzer ist als jene, die alle Ziffern diktiert.

Die Kolmogorow-Komplexität entwickelte sich schnell zu einem Kernkonzept der Informatik. Der Begriff ist so grundlegend, dass gleich mehrere Personen ihn in den 1960er Jahren unabhängig voneinander entdeckten, darunter Ray Solomonoff und Gregory Chaitin. Namensgeber wurde aber Kolmogorow, da er den Ansatz als Erster veröffentlichte. »Es ist ein tief greifendes Konzept, nicht nur in Bezug auf den Zufall und die Mathematik, sondern auch auf die Wissenschaft im Allgemeinen«, so Pass.

Eine unberechenbare Funktion

Allerdings hat die Kolmogorow-Komplexität einen erheblichen Nachteil: Sie ist nicht berechenbar. Das heißt, es gibt keinen Algorithmus, der die Komplexität jeder möglichen Folge berechnen kann. Glücklicherweise existiert eine schwächere Variante der Idee, die durchaus berechenbar ist. Die »zeitlich begrenzte« Kolmogorow-Komplexität gibt nicht zwangsweise das kürzeste Programm an, das eine Zeichenfolge erzeugt, aber dafür das knappste, das effizient ist. Denn der kürzeste Algorithmus könnte unter Umständen Millionen von Jahren brauchen, um die Beschreibung einer Folge zu finden. Solche Fälle schließt man in der abgeschwächten Version aus.

Man kann also für jede beliebige Zahlenfolge die zeitlich begrenzte Kolmogorow-Komplexität bestimmen. Nun stellt sich die für Computerwissenschaften typische Frage: Wie einfach lässt sich die Komplexität berechnen? Wie Liu und Pass herausgefunden haben, ist genau das der Schlüssel zum Beweis der Existenz von Einwegfunktionen.

Tatsächlich muss man bei der Aufgabe nicht ganz so streng sein: Es genügt, sich der zeitlich begrenzten Komplexität näherungsweise (man fordert keine exakte Genauigkeit) zu widmen – zudem möchte man sie nur für die meisten Zeichenketten bestimmen. Falls es einen effizienten Weg gibt, das zu tun, dann existieren keine echten Einwegfunktionen, wie Liu und Pass gezeigt haben. Und alle Kandidaten für unumkehrbare Funktionen wären nicht nur in der Theorie, sondern auch in der Praxis schnell knackbar. Damit könnte es keine sichere Kryptografie geben.

Im umgekehrten Szenario existieren hingegen gemäß Pass und Liu echte Einwegfunktionen: wenn es unmöglich ist, für viele Zahlenfolgen die ungefähre zeitlich begrenzte Kolmogorow-Komplexität effizient zu berechnen. Für diesen Fall liefern die beiden Informatiker sogar eine Anleitung, nach der man eine unumkehrbare Abbildung erzeugen kann. In der jetzigen Form wäre sie jedoch zu kompliziert, um in realen Anwendungen eingesetzt zu werden. Aber wie Ishai betont, folgen auf einen theoretischen Durchbruch in der Kryptografie oft praktische Konstruktionen. Daher ist die komplexe Herleitung der Einwegfunktion von Liu und Pass laut Ishai keine grundlegende Einschränkung.

Falls sich der Ansatz der beiden Computerwissenschaftler tatsächlich vereinfachen lässt, sollte man ihn den auf Multiplikation und anderen mathematischen Operationen basierenden Funktionen vorziehen. Denn bei Letzteren ist nicht sichergestellt, dass sie wirklich unumkehrbar sind.

Der Aufsatz von Pass und Liu hat eine regelrechte Flut von Forschungsarbeiten an der Schnittstelle zwischen Kryptografie und Komplexitätstheorie ausgelöst. Obwohl beide Disziplinen dasselbe Ziel haben, gehen sie die Frage von unterschiedlichen Standpunkten aus an, erklärt der Komplexitätstheoretiker Rahul Santhanam von der University of Oxford. Die Kryptografie sei schnelllebig und pragmatisch, die Komplexitätstheorie eher langsam und konservativ.

Jeder Bereich bietet dem anderen eine neue Perspektive: Kryptografen haben gute Gründe zu glauben, dass es Einwegfunktionen gibt; gleichzeitig spricht für Komplexitätstheoretiker einiges dafür, dass die zeitlich begrenzte Kolmogorow-Komplexität schwierig zu bestimmen ist. Durch die neuen Ergebnisse von Liu und Pass stützen sich die beiden Hypothesen nun gegenseitig. Dennoch untersuchen Fachleute weiterhin, ob es neben der Kolmogorow-Komplexität noch andere »Hauptprobleme« gibt, die für unumkehrbare Funktionen ausschlaggebend sein könnten. Damit käme man dem Traum einer absolut sicheren Kommunikation vielleicht noch ein Stückchen näher.