Die neue Mathematik der Quantenkryptographie

Die Originalversion dieser Geschichte erschien im Quanta Magazine .

Schwierige Probleme sind normalerweise kein gern gesehener Anblick. Kryptographen hingegen lieben sie. Denn bestimmte schwierige mathematische Probleme bilden die Grundlage für die Sicherheit moderner Verschlüsselung. Jeder clevere Trick, um sie zu lösen, wird die meisten Formen der Kryptographie zum Scheitern verurteilen.

Vor einigen Jahren entdeckten Forscher einen radikal neuen Verschlüsselungsansatz , der diese potenzielle Schwachstelle nicht kennt. Er nutzt die Besonderheiten der Quantenphysik. Anders als frühere Quantenverschlüsselungsverfahren, die nur für wenige Spezialaufgaben geeignet waren, kann der neue Ansatz jedoch ein deutlich breiteres Aufgabenspektrum bewältigen. Und er könnte sogar dann funktionieren, wenn sich alle Kernprobleme der herkömmlichen „klassischen“ Kryptografie als leicht lösbar erweisen.

Doch diese bemerkenswerte Entdeckung beruhte auf unrealistischen Annahmen. Das Ergebnis sei „eher ein Proof of Concept“, sagte Fermi Ma , Kryptografieforscher am Simons Institute for the Theory of Computing in Berkeley, Kalifornien. „Es ist keine Aussage über die reale Welt.“

Nun hat ein neues Papier zweier Kryptographen einen Weg zur Quantenkryptographie aufgezeigt, der diese abwegigen Annahmen überflüssig macht. „Dieses Papier besagt, dass Quantenkryptographie existieren muss, wenn bestimmte andere Vermutungen zutreffen“, sagte Ma.

Man kann sich die moderne Kryptografie als einen Turm mit drei wesentlichen Teilen vorstellen. Der erste Teil ist das Fundament tief unter dem Turm, das aus schwierigen mathematischen Problemen besteht. Der Turm selbst ist der zweite Teil – dort finden Sie spezifische kryptografische Protokolle, mit denen Sie private Nachrichten senden, digitale Dokumente signieren, geheime Abstimmungen durchführen und vieles mehr können.

Um diese alltäglichen Anwendungen auf mathematischem Fundament zu sichern, gibt es eine Basis aus Bausteinen, sogenannten Einwegfunktionen . Sie sind für die jedem Verschlüsselungsschema innewohnende Asymmetrie verantwortlich. „Einwegfunktionen sind deshalb so wichtig, weil man Nachrichten zwar verschlüsseln, aber nicht entschlüsseln kann“, erklärt Mark Zhandry , Kryptograf bei NTT Research.

In den 1980er Jahren bewiesen Forscher, dass Kryptografie auf der Basis von Einwegfunktionen die Sicherheit für viele verschiedene Aufgaben gewährleisten kann. Doch Jahrzehnte später ist man sich immer noch nicht sicher, ob die zugrundeliegende Struktur robust genug ist, um diese Sicherheit zu gewährleisten. Das Problem ist, dass diese Struktur aus besonders schwierigen Problemen – den sogenannten NP-Problemen – besteht, deren entscheidendes Merkmal darin besteht, dass sich die Richtigkeit einer möglichen Lösung leicht überprüfen lässt. (Beispielsweise ist die Zerlegung einer Zahl in ihre Primfaktoren ein NP-Problem: Bei großen Zahlen schwierig durchzuführen, aber leicht zu überprüfen.)

Viele dieser Probleme scheinen an sich schwierig zu sein, aber Informatiker konnten dies nicht beweisen . Wenn jemand einen ausgeklügelten Algorithmus zur schnellen Lösung der schwierigsten NP-Probleme entdeckt, wird das Fundament zerbröckeln und der ganze Turm einstürzen.

Leider können Sie Ihren Turm nicht einfach woanders hin versetzen. Das Fundament des Turms – Einwegfunktionen – kann nur auf einem Fundament aus NP-Problemen ruhen.

Um einen Turm für schwierigere Probleme zu bauen, bräuchten Kryptographen eine neue Grundlage, die nicht auf Einwegfunktionen basiert. Das schien bis vor wenigen Jahren unmöglich, als Forscher erkannten, dass die Quantenphysik Abhilfe schaffen könnte.

Es begann mit einer Arbeit des Doktoranden William Kretschmer aus dem Jahr 2021, die auf ein seltsames Problem der Eigenschaften von Quantensystemen aufmerksam machte. Forscher zeigten bald, dass Kretschmers Problem Einwegfunktionen als Grundlage für einen neuen Turm kryptografischer Protokolle ersetzen könnte. Im folgenden Jahr bewiesen Kretschmer und andere, dass dieser alternative Ansatz auch ohne schwierige NP-Probleme funktionieren könnte. Plötzlich schien es möglich, eine weitaus robustere kryptografische Festung zu errichten.

Doch wo sollte man es bauen? Kretschmers Quantenproblem basierte auf hypothetischen Rechenmaschinen, sogenannten Orakeln, die spezifische Fragen sofort beantworten können. Orakel können zwar nützliche theoretische Werkzeuge sein, existieren aber in Wirklichkeit nicht. Kretschmers Beweise waren wie eine Blaupause für ein Luftschloss. Gab es eine Möglichkeit, sie auf die Erde zu bringen?

Im Herbst 2022 erregte diese Frage die Aufmerksamkeit von Dakshita Khurana , einer Kryptografin an der University of Illinois at Urbana-Champaign und bei NTT Research. Khurana und ihr Doktorand Kabir Tomer machten sich daran, einen neuen Turm der Kryptografie zu errichten. Ihr erster Schritt bestand darin, ein neues Fundament zu schaffen, bei dem sie Quantenbausteine ​​anstelle klassischer Einwegfunktionen verwendete. Dann musste sie beweisen, dass dieses neue Fundament einen Turm aus anderen kryptografischen Protokollen tragen konnte. Sobald sie bewiesen hatte, dass das Fundament den Turm tragen konnte, musste sie einen soliden Platz für das Ganze finden – ein Fundament aus realen Problemen, die noch schwieriger erscheinen als die NP-Probleme der klassischen Kryptografie.

Im ersten Schritt konzentrierten sich Khurana und Tomer auf eine Quantenversion einer Einwegfunktion, einen sogenannten Einweg-Zustandsgenerator , der die drei Eigenschaften erfüllt, die Einwegfunktionen nützlich machen. Erstens muss die Funktion schnell laufen, damit sich für jede zu sendende Nachricht problemlos ein kryptografisches Schloss und der dazugehörige Schlüssel zum Öffnen generieren lassen. Zweitens muss jedes Schloss sicher sein und ohne den richtigen Schlüssel nur mit großem Aufwand geknackt werden können. Und schließlich muss jedes Schloss mit dem richtigen Schlüssel leicht zu öffnen sein.

Der entscheidende Unterschied lag in der Art der Sperren. Klassische Einwegfunktionen erzeugen mathematische Sperren aus Bits – den Nullen und Einsen, die in einem klassischen Computer Informationen speichern. Quanten-Einwegzustandsgeneratoren würden stattdessen Sperren aus Quanteninformationseinheiten, sogenannten Qubits, erzeugen. Diese Quantensperren könnten potenziell sicher bleiben, selbst wenn alle klassischen Sperren leicht zu knacken sind. Khurana und Tomer hofften, mit diesem neuen Quantenfundament beginnen und darauf einen Turm aus kryptografischen Protokollen aufbauen zu können. „Das erwies sich als ziemlich schwierig“, sagte Khurana. „Wir steckten viele, viele Monate fest.“

Im Juli 2023 war Khurana im neunten Monat schwanger und plante ihre Elternzeit. Tomer hatte keine Ideen mehr. „Ich bin viel pessimistischer als Dakshita“, sagte er. „Sie ist immer diejenige, die daran glaubt, dass alles klappen wird.“

Dann gelang ihnen ein Durchbruch. Der entscheidende Schritt bestand in der Definition eines weiteren mathematischen Bausteins, der als eine Art Kellergeschoss diente: eine Struktur, die die Grundlage der Einweg-Zustandsgeneratoren mit einem Turm aus kryptografischen Protokollen verbinden sollte. Als Khurana und Tomer herausfanden, welche Eigenschaften dieser Baustein haben musste, stellten sie fest, dass er einer Einwegfunktion mit einer verblüffenden Mischung aus Quanten- und klassischen Eigenschaften ähnelte. Wie bei einer gewöhnlichen Einwegfunktion bestanden sowohl Schlösser als auch Schlüssel aus klassischen Bits, doch das Verfahren zur Erzeugung dieser Schlösser und Schlüssel ließ sich nur auf einem Quantencomputer ausführen. Noch merkwürdiger war, dass der neue Baustein die ersten beiden definierenden Eigenschaften von Einwegfunktionen erfüllte, nicht jedoch die dritte: Schlösser und Schlüssel ließen sich leicht erzeugen, und jedes Schloss war schwer zu knacken. Ein Schlüssel hingegen ließe sich nicht leicht öffnen.

Khurana und Tomer nannten diese verblüffenden neuen Bausteine ​​Einwegrätsel. Intuitiv ist es schwer vorstellbar, wie nützlich sie sein könnten: Was nützt ein Schlüssel, den man nie benutzen kann? Doch die beiden Kryptographen zeigten, dass Einwegrätsel in Kombination mit anderen Quantentricks tatsächlich viele kryptographische Protokolle ermöglichen würden. Wenn man Schlösser und Schlüssel erzeugen kann, die prinzipiell zusammenpassen, spielt es keine Rolle, ob das Entschlüsselungsverfahren extrem ineffizient ist.

„Es genügt zu wissen, dass es einen Algorithmus gibt, der beliebig langsam sein kann“, sagte Kretschmer, der heute am Simons Institute forscht. „Das ist sehr überraschend.“

Nachdem dieses fehlende Stück vorhanden war, konnten sie den Beweis am 4. August schnell abschließen. Nur wenige Tage später wurde Khuranas Tochter geboren.

Im November war Khurana wieder an der Arbeit und bereit, die zweite Phase ihres Plans in Angriff zu nehmen. Sie und Tomer hatten gezeigt, dass viele Arten der Kryptografie auf Einwegrätseln aufbauen können und dass Einwegrätsel wiederum auf einem neuen Quantenfundament aus Einwegzustandsgeneratoren aufgebaut werden können. Der nächste Schritt in ihrem ursprünglichen Plan bestand darin, dieses Quantenfundament mit einem neuen Fundament zu verbinden – einer Reihe relativ unangreifbarer mathematischer Probleme, die noch schwieriger zu lösen sind als die in NP.

Doch als Khurana und Tomer mit dieser Aufgabe haderten, entschieden sie sich für einen direkteren Ansatz: Sie ließen die Einweg-Zustandsgeneratoren außer Acht und verankerten Einweg-Rätsel stattdessen direkt im mathematischen Fundament.

Aus einer Perspektive schien dies eine seltsame Wahl zu sein. Einwegrätsel waren mathematische Kuriositäten, die Khurana und Tomer in einem Zwischenschritt ihres Beweises verwendet hatten.

Dennoch hatten Einwegrätsel einige Vorteile. Zum einen waren sie zwar quantenmechanisch, die von ihnen generierten Schlösser und Schlüssel jedoch klassisch. Khurana glaubte, dass dies ihre Verknüpfung mit den Grundlagen der klassischen Mathematik erleichtern könnte. Darüber hinaus generierten Einwegrätsel Schlüssel, die zu unhandlich waren, um tatsächlich Schlösser zu öffnen. Das könnte ihre Verknüpfung mit Problemen erleichtern, die so knifflig sind, dass selbst die Überprüfung der Lösungen hoffnungslos schwierig erscheint.

Doch welche konkreten Probleme wären dafür geeignet? Khurana hatte einen Kandidaten im Sinn: die Berechnung einer bestimmten Kombination von Einträgen in einer Zahlentabelle, einer sogenannten Matrix. Dieses Problem, bekannt als Matrix-Permanent-Problem, ist bei großen Matrizen bekanntermaßen schwer zu lösen, und es gibt keine einfache Möglichkeit, die Richtigkeit einer Berechnung zu überprüfen. Das Matrix-Permanent-Problem weist zudem weitere besondere mathematische Eigenschaften auf, die Kryptographen interessant finden.

„Das wäre ein wunderbares Problem, auf dem man Kryptographie aufbauen könnte“, sagte Khurana.

Das Matrix-Permanent-Problem steht zudem mit einem anderen Problem in Zusammenhang, das Quantencomputer leicht lösen können, klassische Computer jedoch scheinbar nicht . Forscher arbeiten daran, diesen Vorteil der Quantenberechnung theoretisch präzise zu beweisen. Khurana und Tomer zeigten, dass ein solcher Beweis es ihnen auch ermöglichen würde, sichere Einwegrätsel – und damit den gesamten Turm der Quantenkryptographie – auf dem Permanent-Problem aufzubauen.

„Sie konnten dies auf der Grundlage dieser gut durchdachten Annahmen erreichen“, sagte Kretschmer. „Das hat mich wirklich gefreut.“

Mit ihrem neuen Ergebnis haben Khurana und Tomer zwei offene Probleme effektiv auf ein einziges reduziert. Gelingt den Forschern der Beweis, dass Quantencomputer klassische Computer bei einer bestimmten Aufgabe tatsächlich übertreffen, steht die Quantenkryptographie automatisch auf einer viel solideren theoretischen Grundlage als praktisch jede Form klassischer Kryptographie.

Leider wird man Khuranas und Tomers neuen Ansatz nicht so bald zum Versenden geheimer Nachrichten nutzen können. Trotz jüngster Fortschritte ist die Quantencomputertechnologie noch nicht ausgereift genug, um ihre Ideen in die Praxis umzusetzen. Andere Forscher haben inzwischen Methoden der Quantenkryptografie entwickelt, die schon früher eingesetzt werden könnten . Allerdings bedarf es noch weiterer Forschung, um ihre tatsächliche Sicherheit zu beweisen.

Die Quantenkryptografie hat bereits viele Überraschungen bereitgehalten, und Forscher haben erst vor Kurzem begonnen, die Möglichkeiten zu erforschen. „Wir versuchen einfach, diese neue Landschaft zu verstehen, die es eigentlich schon immer gab“, sagte Zhandry.

Der Originalartikel wurde mit Genehmigung des Quanta Magazine nachgedruckt, einer redaktionell unabhängigen Publikation der Simons Foundation , deren Aufgabe darin besteht, das öffentliche Verständnis für die Wissenschaft zu verbessern, indem sie über Forschungsentwicklungen und Trends in der Mathematik sowie den Natur- und Biowissenschaften berichtet.