Direkt zum Inhalt

Komplexität: Auf der Jagd nach unknackbaren Funktionen

Ob es überhaupt möglich ist, Daten völlig sicher zu verschlüsseln, hängt von einer der bedeutendsten Fragen der theoretischen Informatik ab: Wie ­effizient lässt sich beurteilen, ob eine Zeichenfolge zufällig entstanden ist?
Kryptografie
Fachleute suchen nach speziellen Funktionen, die Informationen verschleiern. Die Chiffre muss aber auch wieder entzifferbar sein.

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.

Vigenère-Chiffre

Diese Art der Verschlüsselung basiert auf der berühmten Cäsar-Chiffre, also einer Verschiebung der Buchstaben des Alphabets. Bei der Vigenère-Verschlüsselung wendet man eine solche Substitution allerdings mehrmals auf die Zeichen einer Nachricht an. Dafür notiert man zunächst alle möglichen ­Cäsar-Chiffren in einer Tabelle. Anschließend wählt man einen Schlüssel, zum Beispiel »Spektrum«. Wenn Sie nun eine Nachricht, etwa »Kryptografie ist toll«, verschlüsseln möchten, gehen Sie folgendermaßen vor: Sie notieren den Schlüssel oberhalb der Nachricht und wiederholen ihn, bis Sie jedem Buchstaben des Texts je einen des Schlüsselworts zugeordnet haben:

SPEKTRUMSPEK TRU MSPE
KRYPTOGRAFIE IST TOLL

Der Buchstabe des Schlüssels gibt an, welche Verschiebung des Alphabets Sie verwenden, um das zugehörige Zeichen der Nachricht zu chiffrieren. Sie gehen die Zeilen der Tabelle durch, bis Sie beim entsprechenden Buchstaben des Schlüssels gelandet sind. Als Spalte wählen Sie den zu verschlüsselnden Buchstaben des Textes und erhalten so das codierte Zeichen. Damit ergibt sich schließlich:

CGBZMFADSUMO BJN FGAP

Wie der preußische Infanteriemajor Friedrich Kasiski 1863 herausfand, existiert eine Methode, einen auf diese Weise verschlüsselten Text zu knacken – insbesondere wenn er lang ist. Dafür sucht man nach wiederholt auftretenden Zeichenfolgen, die bestimmten Wörtern wie Artikeln entsprechen könnten und mehrmals in einem Text vorkommen. Damit lässt sich die Länge n des Schlüsselworts bestimmen. Wenn man sie kennt, kann man nach jedem n-ten Zeichen einen Zeilenumbruch einfügen. Damit hat man eine Tabelle mit n Spalten erzeugt. Jede Spalte entspricht einem Code mit einer einfachen Cäsar-Chiffre, da in ihr das Alphabet um jeweils dieselbe Distanz verschoben ist. Ein solcher Code lässt sich jedoch leicht mit einer Häufigkeitsanalyse knacken: Man vergleicht die Anzahl der codierten Zeichen mit der Häufigkeit, in der Buchstaben in der verwendeten Sprache auftauchen. Hat das Passwort hingegen nicht viel weniger Zeichen als die versendete Nachricht, ist diese Form der Codierung sicher.

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.

Die Kolmogorow-Komplexität ist unberechenbar

Angenommen, es gäbe einen Algorithmus K, der die Kolmogorow-Komplexität für jede beliebige Zeichenfolge berechnen kann. Das Programm könnte zum Beispiel aus einer Million Zeichen bestehen. Nun sucht man nach der kürzesten Folge S, deren Kolmogorow-Komplexität doppelt so lang ist wie K, was also zwei Millionen entspricht. Das bedeutet, das kürzeste Programm, das S ausgibt, ist zwei Millionen Zeichen lang.

Dank des Algorithmus K lässt sich S einfach – wenn auch nicht unbedingt schnell – berechnen: Man kann dazu ein neues Programm P entwickeln: »Gehe alle möglichen Zeichenfolgen der Reihe nach durch und nutze K, um ihre Kolmogorow-Komplexität zu bestimmen. Falls die Komplexität zwei Millionen beträgt, gebe die Folge aus und halte an.« P hängt also von K ab, das aus einer Million Zeichen besteht. Doch so, wie wir P formuliert haben (und es war nicht einmal der effektivste Weg), enthält es bloß ein klein bisschen mehr als eine Million Zeichen. Das System liefert jedoch die Folge S, deren kürzester erzeugender Algorithmus laut Definition zwei Millionen Zeichen hat – wesentlich mehr als P. Man hat also einen Widerspruch: Denn man hat eine kürzere Folge S gefunden, als per Definition erlaubt wäre. Wegen dieses Widerspruchs muss die Annahme falsch sein: Es existiert also kein Programm K, das die Kolmogorow-Komplexität für jede beliebige Folge berechnen kann.

Der Widerspruch löst sich allerdings auf, wenn man nicht nach dem kürzesten Algorithmus sucht, sondern nach dem knappsten, der auch noch effizient ist. Schließlich braucht das oben beschriebene P extrem lange, um alle möglichen Ziffernfolgen durchzugehen. Wenn man solche langsamen Algorithmen verbietet, landet man bei der »zeitlich begrenzten« Kolmogorow-Komplexität. Diese ist berechenbar: Man kann sie für jede Zeichenfolge bestimmen – zumindest theoretisch. Und sie ist wesentlich realistischer als die ursprüngliche Variante.

Kolmogorow-Komplexität | Ein Maß für Zufälligkeit basiert darauf, wie einfach es ist, eine bestimmte Zahlenfolge zu beschreiben. Je einfacher das Programm ist, das die Ziffern erzeugt, desto geringer ist die Kolmogorow-Komplexität der Folge.

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. 

In welcher kryptografischen Welt leben wir?

1995 beschäftigte sich der Computerwissenschaftler Russell Impagliazzo von der University of California, San Diego, mit den unterschiedlichen kryptografischen Möglichkeiten, die eine Welt bieten kann. Um seine Ergebnisse zusammenzufassen, beschrieb Impagliazzo fünf Universen, die er fantasievoll Algorithmica, Heuristica, Pessiland, Minicrypt und Cryptomania nannte. In ihnen haben mathematische Probleme verschiedene Schwierigkeitsgrade und Anwendungsspielräume, die sich für Verschlüsselungsverfahren eignen. Jedes einzelne beschriebene Universum könnte die Welt sein, in der wir leben. Welches wir tatsächlich bewohnen, ist bisher noch unklar.

Algorithmica
In dieser Welt sind alle Rechen­aufgaben einfach, was Kryptografie unmöglich macht. Das heißt, die Menge der Probleme mit effizienten Lösungen – in der Informatik als »P« bezeichnet – enthält nicht nur die bisher bekannten Aufgaben, die wir schnell berechnen können. Vielmehr umfasst P in diesem Universum auch alle NP-Prob­leme; das sind solche, deren Er­gebnisse sich leicht überprüfen lassen, wenn sie jemand liefert. Unter anderem fallen in diese Kategorie Aufgaben, die aktuell schwer zu lösen sind.

Auf den ersten Blick wirken P und NP sehr unterschiedlich: Zwar lässt sich die Lösung eines effizient lösbaren Problems wohl schnell verifizieren (P ist also Teil von NP) – umgekehrt ist das aber nicht immer der Fall. Ein Beispiel dafür ist das Packen eines Koffers. Wenn ihn eine andere Person füllt, kann man sich einfach versichern, ob alles hineingepasst hat. Man muss nur nachsehen, ob etwas vergessen wurde. Es handelt sich also um ein NP-Problem. Aber die Tasche selbst zu packen, ist wesentlich schwieriger, gerade wenn man viel verstauen möchte: Man muss vielleicht zahlreiche Anordnungen ausprobieren, bis es funktioniert. Gegenwärtig ist nicht klar, ob es einen effizienten Algorithmus gibt, dem das für alle möglichen Kom­binationen von Gegenständen und Koffern gelingt. Wir wissen also nicht, ob das Problem in P liegt.

In Algorithmica sind P und NP gleich, das heißt, sie enthalten dieselben Aufgaben. Wenn das tatsächlich der Fall wäre, hätte man eine regelrechte Goldgrube entdeckt. Denn daraus würde folgen, dass es für schwierige Probleme wie das Kofferpacken und viele andere komplexe Beispiele aus NP schnelle Algorithmen gibt, die sie lösen. Das würde zahlreiche Anwendungen erleichtern – für Kryptografen wäre es hingegen eine Katastrophe. Denn ein weiteres Element von NP ist die Entschlüsselung kryptografischer Verfahren: Wenn jemand behauptet, eine chiffrierte Nachricht geknackt zu haben, kann man sich ganz leicht davon überzeugen, ob der entzifferte Text mit dem ursprünglichen übereinstimmt.

Die vorherrschende Auffassung in der Informatik ist, dass sich P und NP unterscheiden – aus dem einfachen Grund, dass es so viele Probleme in NP gibt, die man trotz jahrelanger aufwändiger Bemühungen nicht effizient lösen kann. Be­weisen oder widerlegen konnte das bisher jedoch niemand. Tatsächlich gilt »P versus NP« seit mehr als fünf Jahrzehnten als die berühmteste Frage der theoretischen Informatik. Es ist eines der sieben Millennium-Probleme, für deren Lösung das Clay Mathematics Institute im Jahr 2000 jeweils eine Belohnung in Höhe von einer Million Dollar ausgeschrieben hat. »Abgesehen vom ständigen Scheitern der klügsten Köpfe gibt es allerdings keine Hinweise darauf, dass ›P versus NP‹ schwer zu knacken ist«, meint Yuval Ishai vom Technion in Haifa, Israel.

Heuristica
In dieser Welt gibt es NP-Probleme, die nicht einfach zu lösen sind, das heißt, allgemein gilt P ≠ NP. Dennoch sind die meisten Aufgaben aus NP zumindest durchschnittlich effizient berechenbar. In Heuristica könnte es zum Beispiel einen schnellen Algorithmus zum Kofferpacken geben, der fast immer funktioniert. Nur bei einigen wenigen Kombinationen aus Behältnissen und Gegenständen würde die Rechenvorschrift versagen. Solche effizienten und in der Regel erfolgreichen Algorithmen werden gemeinhin als »Heuristiken« bezeichnet, daraus leitet sich der Name des Universums ab.

Aus kryptografischer Sicht gibt es keinen großen Unterschied zu Algorithmica. Wenn man sich in Heuristica ein Verschlüsselungsverfahren ausdenkt, existiert eine schnelle Entschlüsselungsmethode, die mit fast jeder Nachricht umgehen kann. Damit ist Kryptografie in diesem Szenario für praktische Zwecke nutzlos.

Pessiland
Tatsächlich ist diese Welt die aus computerwissenschaftlicher Sicht schlechteste aller möglichen Optionen. Denn in Pessiland sind einige Probleme in NP zwar durchschnittlich schwer, aber sie erlauben keine Einwegfunktionen, die für die Kryptografie notwendig sind.

Dabei handelt es sich um mathematische Abbildungen, die sich einfach ausführen (so schafft man eine Verschlüsselung), allerdings nicht umkehren (entschlüsseln) lassen. Informatikerinnen und Informatiker haben gezeigt, dass sichere Verschlüsselungen Einwegfunktionen erfordern.

In diesem Universum versagt jeder effiziente Algorithmus nicht nur gelegentlich – wie in Heuristica –, sondern fast immer. Andererseits kann man aus den durchschnittlich schweren Aufgaben jedoch keine Funktionen konstruieren, um geheime Informationen zu verstecken. »Wir wollen definitiv nicht in Pessiland leben«, sagt Eric Allender von der Rutgers University. »Hier hat man alle Nachteile hoher Komplexität, aber keinerlei Vorteile davon, wie etwa Kryptografie.«

Minicrypt
In jener Welt sind einige NP-Probleme durchschnittlich schwierig, wobei sich manche dafür eignen, den grundlegendsten Baustein der Kryptografie zu schaffen: eine Einwegfunktion. Diese ermöglicht kryptografische Verfahren mit geheimen Schlüsseln; digitale Signaturen, welche die Identität einer Person sicherstellen; und Pseudozufallszahlengeneratoren.

»Ob es Einwegfunktionen gibt, ist ohne Frage das wichtigste Problem der Kryptografie«, sagt Rafael Pass von der Cornell University. »Wenn wir sie nicht haben, können all diese Dinge gebrochen werden.«

Cryptomania
Das Universum bietet in diesem Szenario genügend Komplexität, um alle Anwendungen in Minicrypt zu ermöglichen – und sogar noch fortgeschrittenere kryptografische Protokolle. In Cryptomania lassen sich auch Verschlüsselungen mit Public-Key-Verfahren (durch die man chiffrierte Nachrichten übermitteln kann, ohne den geheimen Schlüssel zu kennen) realisieren, die im digitalen Zeitalter unerlässlich sind.

Yuval Ishai zufolge sind die meisten Informatikerinnen und Informatiker davon überzeugt, dass Kryptografie in unserer Welt zumindest teilweise existiert. Demnach leben wir höchstwahrscheinlich in Cryptomania oder Minicrypt. Ein eindeutiger Beweis liegt aber noch in weiter Ferne. Denn dafür müsste man die anderen drei Welten ausschließen – und allein um Algorithmica zu eliminieren, muss man das »P versus NP«-Problem lösen, mit dem sich die theoretische Informatik seit Jahrzehnten erfolglos herumschlägt.

Allerdings haben Rafael Pass und sein Doktorand Yanyi Liu im Jahr 2020 einen neuen Ansatz gefunden, um die möglichen kryptografischen Universen zu durchforsten. Dabei konnten sie zeigen, dass die zeitlich begrenzte Kolmogorow-Komplexität Welten mit und ohne Kryptografie eindeutig voneinander abgrenzt.

Wenn sich die genannte Komplexität durchschnittlich leicht berechnen lässt, gibt es gemäß Liu und Pass keine sichere Verschlüsselung. In diesem Fall befinden wir uns also in Algorithmica, Heuristica oder Pessiland. Ist die Aufgabe hingegen im Durchschnitt schwer zu lösen, lassen sich Einwegfunktionen konstruieren – wir wären dann zumindest in Minicrypt und möglicherweise sogar in Cryptomania.

Eine weitere Anstrengung könnte es ermöglichen, mit Hilfe der neuen Ergebnisse Pessiland – die schlimmste aller Welten – vollständig auszuschließen. Dafür müsste man beweisen, dass sich die durchschnittliche Einfachheit der zeitlich begrenzten Kolmogorow-Komplexität auf alle anderen Probleme in NP überträgt. Dann blieben nur vier mögliche Universen übrig: diejenigen, in denen Kryptografie möglich ist (Minicrypt und Cryptomania), und solche, in denen jedes Problem in NP im Durchschnitt leicht ist (Algorithmica und Heuristica).

Außerdem würden Informatiker und Informatikerinnen gerne Heuristica loswerden. Denn falls die zeitlich begrenzte Kolmogorow-Komplexität durchschnittlich einfach ist, wäre in Heuristica jedes NP-Problem immer leicht zu lösen – nicht nur im Durchschnitt.

Ließen sich beide Welten eliminieren, würden wir also entweder in Algorithmica leben, wo alles stets einfach ist, oder es gäbe genug Komplexität, um zumindest grundlegende Kryptografie zu erlauben.

QUELLE: Impagliazzo, R.: A personal view of average-case complexity. Proceedings of Structure in Complexity Theory. 10th Annual IEEE Conference, 1995

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Quellen

Diffie, W., Hellman, M. E.: New directions in cryptography. IEEE Transactions on Information Theory 22, 1976

Levin, L. A.: One-way functions and pseudorandom generators. Proceedings of the 17th annual ACM symposium on Theory of computing, 1985

Liu, Y., Pass, R.: On One-way Functions and Kolmogorov Complexity. ArXiv 2009.11514, 2020

Partnerinhalte