Quantum Cryptography and Autoformalization in Lean

In der Welt der sicheren Kommunikation bestehen die vertrauenswürdigsten Schlösser nicht aus Stahl, sondern aus den fundamentalen Gesetzen der Physik. Dies ist das Reich der Quantenschlüsselverteilung, einer Methode, bei der zwei Personen, traditionell Alice und Bob genannt, einen gemeinsamen geheimen Code generieren, um ihre Nachrichten zu schützen. Im Gegensatz zur herkömmlichen Verschlüsselung, die auf der Schwierigkeit beruht, komplexe mathematische Probleme zu lösen, stützt sich dieser Ansatz auf die Tatsache, dass die Messung eines winzigen Lichtteilchens, oder Photons, es unweigerlich verändert. Wenn ein Dritter, eine Lauscherin namens Eve, versucht mitzuhören, hinterlässt sie eine nachweisbare Spur ihrer Interferenz. Jahrzehntelang haben Wissenschaftler Protokolle entwickelt, um diese Schlüssel zu erzeugen, aber den Beweis zu führen, dass diese Systeme wirklich sicher sind, war ein fragiler Prozess. Die Beweise stützten sich oft auf eine Kette mathematischer Argumente, die aus verschiedenen Papieren zusammengestückelt wurden, wobei jedes seine eigenen Annahmen hatte. Wenn ein Glied in dieser Kette geringfügig nicht mit einem anderen übereinstimmte oder wenn eine versteckte Annahme übersehen wurde, konnte die gesamte Sicherheitsgarantie beeinträchtigt werden, ohne dass es jemand bemerkte.

Ein Team von Forschern am Massachusetts Institute of Technology hat diese Fragilität nun angegangen, indem sie einen Sicherheitsbeweis von Grund auf neu aufgebaut haben, unter Verwendung eines Computerprogramms, das die mathematische Logik überprüft. Sie konzentrierten sich auf eine spezifische, weit verbreitete Methode namens BB84-Protokoll, das verschränkte Teilchenpaare verwendet, um Schlüssel zu generieren. Anstatt darauf zu vertrauen, dass ein Mensch verifiziert, ob jeder Schritt der Logik zusammenhält, haben sie das gesamte Sicherheitsargument in eine formale Sprache übersetzt, die ein Computer lesen und mit absoluter Präzision verifizieren kann. Das Ergebnis ist ein maschinengeprüfter Beweis, der keinen Raum für verborgene Lücken oder unpassende Annahmen lässt. Er bestätigt, dass das Protokoll auch dann sicher bleibt, wenn die Anzahl der ausgetauschten Teilchen begrenzt ist – eine in der Praxis häufige Einschränkung, die die Sicherheitsschätzungen oft schwächt. Darüber hinaus wurde dasselbe Computersystem, das den Beweis verifizierte, verwendet, um eine neue, engere mathematische Schranke zu entdecken, welche die endliche Größenstrafe (finite-size penalty) auf die Schlüsselrate reduziert.

Die Forscher begannen damit, eine digitale Sprache innerhalb des Computersystems zu erstellen, die die Regeln lokaler Operationen und klassischer Kommunikation strikt durchsetzt. Im Kontext der Quantenkryptografie bedeutet dies, dass der Computer sicherstellt, dass Alice und Bob nur Operationen an ihren eigenen Teilchen durchführen können und Informationen nur über öffentliche Kanäle austauschen können, ohne magisch auf die privaten Daten des jeweils anderen zuzugreifen. Diese Sprache fungiert als Leitplanke, die die Art von logischen Fehlern verhindert, die menschlichen Prüfern entgehen können. Beispielsweise schlug ein KI-Agent in früheren Versuchen zur Formalisierung dieser Beweise einmal eine Methode vor, bei der der endgültige Schlüssel durch die Kombination von Zeichenfolgen erstellt wurde, die keine der beiden Parteien tatsächlich besaß. Die strengen Regeln des Computers markierten dies sofort als unmöglich und zwangen das Team, ihren Ansatz zu verfeinern. Durch den schrittweisen Aufbau des Protokolls innerhalb dieser beschränkten Umgebung stellte das Team sicher, dass das endgültige Sicherheitstheorem exakt den physikalischen Prozess beschreibt, den sie schützen wollten.

Nachdem das Protokoll konstruiert worden war, bat das Team den Computer, dessen Sicherheit gegen eine leistungsstarke Art von Angriff zu verifizieren, bekannt als kohärenter Angriff (coherent attack), bei dem eine Lauscherin mit allen Teilchen gleichzeitig interagiert, anstatt mit ihnen einzeln. Der Computer prüfte jeden logischen Schritt, von der anfänglichen Messung der Teilchen bis hin zu den abschließenden Schritten der Fehlerkorrektur und Privatsphäre-Verstärkung (privacy amplification). Er bestätigte, dass das Protokoll sicher ist, was bedeutet, dass der resultierende Schlüssel – sofern das System nicht abbricht – selbst für eine Lauscherin mit unbegrenzter Rechenleistung nicht von einem perfekten, zufälligen geheimen Schlüssel zu unterscheiden ist. Entscheidend war, dass der Beweis die Tatsache berücksichtigte, dass reale Systeme mit einer endlichen Anzahl von Teilchen arbeiten und nicht mit einem unendlichen Strom. Dieser Effekt der endlichen Größe (finite-size effect) zwingt Wissenschaftler normalerweise dazu, übermäßig konservativ zu sein und mehr potenzielles Schlüsselmaterial zu verwerfen, um die Sicherheit zu gewährleisten. Der neue Beweis lieferte jedoch eine präzise Berechnung darüber, wie viel Schlüsselmaterial sicher behalten werden kann, was die Strafe reduziert, die durch diese endlichen Grenzen auferlegt wird.

In einer überraschenden Wendung nutzten die Forscher die gleiche Computer-Pipeline nicht nur, um ihre Arbeit zu verifizieren, sondern um sie zu verbessern. Während das System die Logik prüfte, half es dem Team, eine engere Schranke für die bedingte Entropie-Varianz zu identifizieren, die zur Schätzung der Sicherheit dieser Systeme verwendet wird. Die bestehende Formel war zu locker, was zu einer unnötigen Reduzierung der Länge des geheimen Schlüssels führte. Das Team, geleitet von der Fähigkeit des Computers, verschiedene mathematische Schranken zu testen und zu vergleichen, leitete eine neue, schärfere Ungleichung ab. Diese neue Schranke ist enger gefasst, was es dem System ermöglicht, Schlüssel mit einer reduzierten endlichen Größenstrafe im Vergleich zu dem zu generieren, was die alte Formel erlaubt hätte, ohne die Sicherheit zu opfern. Diese Entdeckung war kein Ratespiel, sondern ein rigoroses mathematisches Ergebnis, das der Computer als wahr verifizierte, was zeigt, dass formale Beweis-Engines mehr können als nur Arbeit zu prüfen – sie können die wissenschaftliche Entdeckung aktiv beschleunigen, indem sie bessere Lösungen für alte Probleme finden.

Die Arbeit dient auch als Vorlage dafür, wie zukünftige kryptografische Systeme validiert werden sollten. Durch die Veröffentlichung der zugrunde liegenden Bibliothek von Definitionen und Theorem als Open Source haben die Forscher der Fachwelt ein wiederverwendbares Toolkit zur Verfügung gestellt. Diese Bibliothek enthält die formalen Definitionen von Quantenzuständen, Kanälen und die spezifische Sprache zur Beschreibung von Protokollen, sodass andere Wissenschaftler auf dieser Grundlage aufbauen können. Dies bedeutet, dass zukünftige Beweise für andere Quantenprotokolle oder sogar für andere Bereiche der Quanteninformationswissenschaft mit demselben Maß an Strenge konstruiert werden können. Das Team zeigte, dass es durch die Kombination von menschlicher Einsicht mit der unerbittlichen Präzision maschinengeprüfter Logik möglich ist, die verborgenen Unsicherheiten zu eliminieren, die das Feld lange Zeit geplagt haben. Das Ergebnis ist ein neuer Standard für Sicherheitsargumente, bei dem die Vertrauenswürdigkeit eines Quantenschlüssels nicht nur eine Behauptung eines Forschers ist, sondern eine Tatsache, die von einer Maschine verifiziert wurde.