Schwierige Probleme sind normalerweise nichts Gutes. Aber Kryptografen lieben sie. Das liegt daran, dass die Sicherheit moderner Verschlüsselung auf komplexen Aufgaben beruht: Je komplizierter das Problem, desto besser ist beispielsweise ein Passwort geschützt. Jeder clevere Trick für eine einfachere Lösung würde die meisten Formen der Kryptografie zum Scheitern bringen.

2021 entdeckten Fachleute einen völlig neuen kryptografischen Ansatz, der ohne diese potenzielle Schwachstelle auskommt. Die Methode macht sich die Besonderheiten der Quantenphysik zunutze. Im Gegensatz zu früheren Quantenverschlüsselungsverfahren, die nur für wenige Sonderfälle funktionieren, kann die neue Technik ein viel breiteres Spektrum an Aufgaben bewältigen. Und sie könnte selbst dann noch funktionieren, wenn sich alle Probleme der klassischen Kryptografie als leicht lösbar erweisen.

Allerdings beruhte dieses aufsehenerregende Ergebnis auf unrealistischen Annahmen. »Es war eher ein konzeptioneller Beweis«, sagt der Kryptograf Fermi Ma vom Simons Institute for the Theory of Computing in Berkeley. »Es ist keine Aussage über die reale Welt.« Doch eine neue Arbeit hat aufgezeigt, wie eine Quantenkryptografie ohne diese abwegigen Annahmen aussehen könnte.

Man kann sich die moderne Kryptografie wie einen Turm vorstellen, der auf einem Grund aus schwierigen mathematischen Problemen steht. Der Turm selbst setzt sich aus kryptografischen Protokollen zusammen, mit denen sich private Nachrichten versenden, digitale Dokumente unterzeichnen oder geheime Abstimmungen durchführen lassen. Dazwischen befindet sich ein Fundament aus sogenannten Einwegfunktionen, die diese alltäglichen Anwendungen auf mathematischem Grund sichern. Sie erzeugen die Asymmetrie, die jedem Verschlüsselungsverfahren innewohnt. »Wir sprechen von Asymmetrie, weil man Nachrichten verschlüsseln, aber nicht entschlüsseln kann«, erklärt der Kryptograf Mark Zhandry von NTT Research.

Ein wackeliges Gerüst

In den 1980er Jahren haben Forschende bewiesen, dass Kryptografie, die auf Einwegfunktionen aufbaut, die Sicherheit vieler verschiedenen Aufgaben gewährleistet. Aber auch Jahrzehnte später ist noch nicht sichergestellt, ob der Grund und Boden, auf dem der Turm steht, ihn überhaupt stützen kann.

Die schwierigen mathematischen Probleme, aus denen der Grund besteht, werden als NP-Probleme bezeichnet. Sie zeichnen sich dadurch aus, dass es zwar einfach ist, sie zu überprüfen, wenn man eine mögliche Lösung präsentiert bekommt; ihre Lösung ist aber sehr schwer zu ermitteln. Zum Beispiel ist die Zerlegung einer Zahl in ihre Primfaktoren ein NP-Problem: Für große Zahlen kaum zu bewältigen, aber leicht zu überprüfen – hier muss man nur die Primteiler miteinander multiplizieren.

• P-Probleme
  P-Probleme sind vergleichsweise einfach zu lösen: Der Rechenaufwand steigt nur langsam mit der Größe des Problems an. Möchte man zum Beispiel zwei Zahlen miteinander multiplizieren, kann das bei sehr großen Zahlen zwar aufwändig erscheinen – aber ein Computer kann das stets bewältigen, egal wie riesig die Zahlen sind.
• NP-Probleme
  Bei NP-Problemen ist das hingegen anders. Diese können für einfache Spezialfälle vielleicht noch gelöst werden, aber es gibt keine effiziente Methode, um allgemeine Aufgaben dieser Art zu berechnen. Ein typisches NP-Problem besteht darin, zu einer vorgegebenen Zahl die Primteiler zu bestimmen: jene Primzahlen, die miteinander multipliziert die ursprüngliche Zahl ergeben. Für einfache Beispiele wie 15 lassen sich die Primteiler (3 und 5) schnell ermitteln. Doch wenn man die Primteiler einer 1000-stelligen Zahl berechnen möchte, sind Computer schnell überfordert. NP-Probleme zeichnen sich aber auch dadurch aus, dass sich ihre Lösung einfach überprüfen lässt. Falls mir jemand eine 1000-stellige Zahl und ihre vermeintlichen Primteiler vorgibt, kann ich die Primzahlen miteinander multiplizieren (das ist ja aus mathematischer Sicht einfach, weil es ein P-Problem ist) und sofort sehen, ob das Ergebnis mit der 1000-stelligen Zahl übereinstimmt.

Bislang ließ sich jedoch nicht beweisen, dass NP-Probleme wirklich so schwer zu lösen sind, wie sie den Anschein machen. Jederzeit könnte jemand einen genialen Algorithmus entdecken, der die komplexesten NP-Probleme knackt. Falls das geschieht, würde der ganze Turm der Kryptografie einstürzen. Kreditkartendaten, Passwörter, persönliche Chats: Nichts wäre mehr sicher.

Leider kann man den Turm nicht einfach woanders hinstellen. Denn Einwegfunktionen können nur auf NP-Problemen aufbauen. Um einen Turm auf härteren Problemen zu errichten, bräuchte man ein neues Fundament, das nicht aus Einwegfunktionen besteht. Das schien bis vor ein paar Jahren unmöglich. Doch dann erkannten Fachleute, dass die Quantenphysik helfen könnte.

Vom Luftschloss auf den Boden der Tatsachen

Den Grundstein legte eine 2021 erschienene Arbeit des damaligen Doktoranden William Kretschmer. Der hatte sich mit einem seltsamen Problem beschäftigt, das mit den Eigenschaften von Quantensystemen zusammenhängt. Kurz darauf erkannten Fachleute, dass Kretschmers Problem die Einwegfunktionen ersetzen und als Fundament für einen neuen Turm aus Verschlüsselungsprotokollen dienen könnte. Im darauffolgenden Jahr bewiesen Kretschmer und einige Kollegen, dass dieser Ansatz ohne NP-Probleme auskommen könnte. Plötzlich schien es möglich, eine weitaus stabilere kryptografische Festung zu errichten.

Aber worauf sollte sie gebaut werden? Das Quantenproblem, das Kretschmer als Fundament verwendet, hat mit hypothetischen Rechenmaschinen zu tun, die als Orakel bezeichnet werden und augenblicklich bestimmte Fragen beantworten können. Orakel sind in der Informatik nützliche Werkzeuge – allerdings nur in der Theorie, da sie nicht wirklich existieren. Kretschmers Arbeiten waren wie eine Blaupause für den Bau eines Luftschlosses. Und doch ließen sich einige Fachleute nicht entmutigen. Sie suchten nach einer Möglichkeit, das Luftschloss auf die Erde zu bringen.

Im Herbst 2022 begann sich die Kryptografin Dakshita Khurana von der University of Illinois in Urbana-Champaign mit ihrem Doktoranden Kabir Tomer für diese Aufgabe zu interessieren. Gemeinsam entwickelten sie einen Plan, um sie zu lösen. Ihr erster Schritt sollte darin bestehen, ein neues Fundament mit Quantenbausteinen anstelle von klassischen Einwegfunktionen zu schaffen. Anschließend müssten sie beweisen, dass dieses einen Turm mit kryptografischen Protokollen stützen kann. Und dann müssten sie noch einen soliden Platz für das Ganze finden: Einen Grund aus realen Problemen, die noch schwieriger erscheinen als die NP-Probleme der klassischen Kryptografie.

Rätselhafte Einweg-Quanten

Im ersten Schritt konzentrierten sich Khurana und Tomer auf eine Quantenversion einer Einwegfunktion, einen »Einweg-Zustandsgenerator«. Dieser erfüllt die drei Eigenschaften, die gewöhnliche Einwegfunktionen so nützlich machen. Erstens muss die Funktion schnell ausgeführt werden können, sodass sich für jede Nachricht, die man versenden möchte, leicht ein kryptografisches Schloss samt Schlüssel zum Öffnen erzeugen lässt. Zweitens muss jedes Schloss sicher sein – also ohne den richtigen Schlüssel kaum zu knacken sein. Und drittens muss sich jedes Schloss mit dem richtigen Schlüssel leicht öffnen lassen.

Der entscheidende Unterschied zwischen Einwegfunktionen und ihrer Quantenversion liegt in der Art der Schlösser. Klassische Einwegfunktionen erzeugen mathematische Schlösser, die aus Bits bestehen – den Nullen und Einsen, die in einem Computer Informationen speichern. Einweg-Quantenzustandsgeneratoren erzeugen stattdessen Schlösser aus Quanteninformationseinheiten, den Qubits. Das bietet einen entscheidenden Vorteil: Quantenschlösser könnten auch dann noch sicher sein, wenn alle klassischen Schlösser leicht zu knacken sind. 

Khurana und Tomer hofften daher, einen Turm von kryptografischen Protokollen auf diesem neuen Quantenfundament aufzubauen. »Das erwies sich als ziemlich schwierig«, erinnert sich Khurana. »Wir steckten viele, viele Monate fest.« Im Juli 2023 war Khurana im neunten Monat schwanger und plante ihre Elternzeit. Und Tomer waren die Ideen ausgegangen. »Ich bin viel pessimistischer als Dakshita«, sagt er. »Sie ist immer diejenige, die daran glaubt, dass die Dinge funktionieren werden.«

Doch dann gelang ihnen der Durchbruch. Der entscheidende Schritt bestand darin, einen weiteren mathematischen Baustein zu definieren – so etwas wie ein Kellergeschoss. Eine Struktur, die das Fundament der Zustandsgeneratoren mit dem Turm aus kryptografischen Protokollen verbinden würde. Dieser Baustein ähnelt einer Einwegfunktion mit einer Mischung aus Quanten- und klassischen Eigenschaften. Wie bei einer gewöhnlichen Einwegfunktion bestehen Schlösser und Schlüssel aus klassischen Bits, aber das Verfahren zur Erzeugung dieser Schlösser und Schlüssel funktioniert nur auf einem Quantencomputer. Noch merkwürdiger ist, dass der neue Baustein zwar die ersten beiden Eigenschaften von Einwegfunktionen erfüllt, nicht aber die dritte: Es ist zwar einfach, Schlösser und Schlüssel zu erzeugen, und jedes Schloss ist schwer zu knacken – aber ein Schlüssel öffnet nicht so leicht das zugehörige Schloss.

Khurana und Tomer nannten diese neuen Bausteine »Einwegrätsel«. Auf den ersten Blick wirken sie nutzlos. Was bringt ein Schlüssel, den man nicht zum Öffnen eines Schlosses benutzen kann? Die beiden erkannten jedoch, dass die Einwegrätsel zusammen mit gewissen Eigenschaften der Quantenmechanik viele kryptografische Protokolle ermöglichen. Wenn man Schlösser und Schlüssel erzeugen kann, die prinzipiell zusammenpassen, spielt es in manchen Fällen keine Rolle, ob das Aufsperren aufwändig ist. »Allein das Wissen, dass es einen Algorithmus gibt, reicht schon oft aus«, sagt Kretschmer. »Das ist sehr überraschend.«

Mit diesem Baustein konnten Khurana und Tomer ihren Beweis am 4. August 2023 abschließen. Nur wenige Tage später brachte die Kryptografin ihre Tochter zur Welt.

Das schwierigste aller Probleme

Drei Monate später nahm Khurana ihre Arbeit wieder auf und war bereit, die zweite Phase ihres Plans anzugehen. Sie und Tomer hatten gezeigt, dass sich viele Arten der Kryptografie auf Einwegrätseln aufbauen lassen – und dass diese Rätsel wiederum auf einem neuen Fundament aus Einweg-Quantenzustandsgeneratoren aufbauen. Der nächste Schritt bestand also darin, dieses Quantenfundament mit einem neuen Grund zu verbinden: unangreifbaren mathematischen Problemen, die noch komplexer sind als jene in NP.

Doch Khurana und Tomer beschlossen, einen direkteren Ansatz zu wählen. Sie vergaßen die Einweg-Quantenzustandsgeneratoren und verankerten stattdessen die Einwegrätsel direkt im mathematischen Grund. Auf den ersten Blick kann das seltsam erscheinen, weil die Einwegrätsel bloß als mathematisches Hilfsmittel dienten, die Khurana und Tomer in einem Zwischenschritt ihres Beweises verwendet hatten.

Doch tatsächlich haben diese Einwegrätsel auch einige Vorteile. Zum Beispiel erzeugen sie klassische Schlösser und Schlüssel. Khurana glaubte, dass es dadurch einfacher sein könnte, sie mit der klassischen Mathematik zu verbinden. Außerdem bringen Einwegrätsel Schlüssel hervor, die zu unhandlich sind, um Schlösser zu öffnen. Das könnte es erleichtern, sie mit Problemen in Verbindung zu bringen, die so kompliziert sind, dass selbst die Überprüfung ihrer Lösungen hoffnungslos schwierig erscheint.

Aber welche mathematischen Probleme würden sich als Grund für diesen neuen kryptografischen Turm eignen? Khurana hatte eine Idee: die Berechnung einer bestimmten Kombination von Einträgen in einer Matrix, einer Art mathematische Tabelle. Eine solche »Permanente« ist für große Matrizen bekanntermaßen schwierig zu berechnen. Und es gibt keine einfache Möglichkeit zu überprüfen, ob das Ergebnis korrekt ist. 

Die Berechnung der Permanente hängt mit einem anderen Problem zusammen, das als potenzieller Kandidat für den Nachweis eines Quantenvorteils dient: ein Problem, das Quantencomputer leicht lösen können, klassische Computer aber offenbar nicht. Seit Jahren versuchen Forschende diesen Vorteil von Quantencomputern mathematisch zu beweisen. Wie Khurana und Tomer zeigten, würde ein solcher Beweis es ihnen auch ermöglichen, nachweislich sichere Einwegrätsel auf dem Matrizenproblem aufzubauen.

Mit ihrem neuen Ergebnis haben Khurana und Tomer zwei offene Fragen der Kryptografie auf eine einzelne reduziert. Wenn es gelingt zu beweisen, dass Quantencomputer ihre klassischen Gegenstücke bei einer bestimmten Aufgabe übertreffen, lässt sich die Quantenkryptografie automatisch auf einem viel solideren Grund aufbauen als jede Art von klassischer Kryptografie.

Doch selbst wenn das gelingt, wird sich der neue Ansatz von Khurana und Tomer in absehbarer Zeit wohl nicht nutzen lassen, um geheime Nachrichten zu versenden. Denn trotz der jüngsten Fortschritte sind Quantencomputer noch nicht ausgereift genug, um die dafür erforderlichen Schlösser und Schlüssel zu erzeugen. Daher arbeiten Fachleute an anderen Methoden der Quantenkryptografie, die schon früher eingesetzt werden könnten, von denen aber noch nicht klar ist, wie sicher sie sind. Doch es herrscht Zuversicht. Denn die Quantenkryptografie hat bereits viele Überraschungen hervorgebracht – und das, obwohl die Fachwelt erst vor Kurzem begonnen hat, den Bereich zu erforschen.