Compressed Permutation Oracles Revisited

In der digitalen Welt beruht Sicherheit oft auf der Vorstellung einer perfekten, unvorhersehbaren Maschine. Kryptographen stellen sich ein Gerät vor, das jede beliebige Eingabe entgegennimmt und eine vollkommen zufällig aussehende Ausgabe liefert, aber mit einer entscheidenden Regel: Wenn man dieselbe Eingabe zweimal hineingibt, erhält man jedes Mal dieselbe Ausgabe. Dies ist als eine Zufallspermutation bekannt. Sie ist der unsichtbare Motor hinter vielen der Werkzeuge, die wir nutzen, um unsere Daten sicher zu halten, von der Art und Weise, wie unsere Passwörter gespeichert werden, bis hin zu den Algorithmen, die die Integrität unserer Kommunikation verifizieren. Um zu testen, ob diese Werkzeuge wirklich sicher sind, stellen sich Wissenschaftler einen mächtigen Angreifer vor, der dieser Maschine Fragen stellen kann. In der klassischen Welt stellt ein Angreifer eine Frage nach der anderen. Aber in der Quantenwelt kann ein Angreifer viele Fragen gleichzeitig stellen, indem er sie überlagert, was sich so anfühlt, als würde er jede mögliche Frage simultan stellen. Diese Fähigkeit, Abfragen in Superposition vorzunehmen, macht die Beweisführung der Sicherheit unglaublich schwierig, da der Angreifer Informationen auf eine Weise gewinnt, die unserer üblichen Intuition trotzt.

Jahrelang haben Forscher versucht, ein mathematisches Modell zu entwickeln, um zu verfolgen, was ein Quantenangreifer aus diesen Fragen lernt. Eine vielversprechende Methode namens „Compressed Oracle“ (komprimiertes Orakel) fungiert dabei wie ein vereinfachtes Notizbuch. Anstatt die gesamte, massive Maschine zu verfolgen, zeichnet das Notizbuch nur die spezifischen Paare von Eingaben und Ausgaben auf, nach denen der Angreifer bisher gefragt hat. Dies macht die Mathematik handhabbar und ermöglicht es Wissenschaftlern, zu beweisen, dass bestimmte Sicherheitssysteme sicher sind. Es gab jedoch ein erhebliches Problem, das diese Methode plagte: Das Notizbuch war nicht perfekt genau. Es wurde nur bewiesen, dass es korrekt funktioniert, wenn der Angreifer eine relativ geringe Anzahl von Fragen stellt. Wenn der Angreifer zu viele Fragen stellte, konnten die Vorhersagen des Notizbuchs von der Realität abweichen, was die Sicherheitsbeweise unzuverlässig machte. Diese Einschränkung bedeutete, dass wir für viele moderne kryptographische Systeme nicht sicher sein konnten, ob sie einem entschlossenen Quanten-Gegner standhalten würden.

Ein Team von Forschern hat diese Methode nun wieder aufgegriffen und ihren kritischsten Fehler behoben. Sie haben demonstriert, dass das komprimierte Notizbuch weitaus zuverlässiger ist als bisher angenommen. Ihre neue Analyse beweist, dass die Methode auch dann korrekt funktioniert, wenn der Angreifer eine wesentlich größere Anzahl von Fragen stellt – nämlich bis zur Quadratwurzel der Gesamtzahl der möglichen Eingaben. Dies ist eine massive Verbesserung gegenüber dem bisherigen Limit, das nur ein winziger Bruchteil dieser Zahl war. Die Forscher erreichten dies, indem sie die Art und Weise änderten, wie sie die Verbindung zwischen der realen, komplexen Maschine und dem vereinfachten Notizbuch aufbauten. Anstatt einer komplizierten, indirekten Konstruktion zeigten sie, dass das Notizbuch als direkte Messung des zugrunde liegenden Zustands der Maschine betrachtet werden kann. Diese neue Perspektive macht die Mathematik nicht nur sauberer und direkter, sondern hebt auch die künstliche Decke auf, bei der die Beweisführung durch die Anzahl der Fragen des Angreifers zusammenbricht.

Die Auswirkung dieser Verbesserung ist unmittelbar und konkret. Die Forscher haben ihren neuen, engeren Beweis auf zwei der wichtigsten Strukturen der modernen Kryptographie angewendet: die Sponge-Konstruktion und die Davies-Meyer-Kompressionsfunktion. Dies sind die Blaupausen, die verwendet werden, um die Hash-Funktionen zu bauen, die unsere digitale Welt sichern, einschließlich des SHA-3-Standards sowie der älteren SHA-1- und SHA-2-Systeme. Unter Verwendung ihrer verfeinerten Methode berechneten die Forscher exakt, wie viele Quantenabfragen ein Angreifer benötigen würde, um diese Systeme zu brechen. Sie fanden heraus, dass die Sicherheit dieser Systeme robust ist und eine Anzahl von Operationen erfordert, die mit der Quadratwurzel der Systemgröße für das Finden von Kollisionen wächst, und sogar noch mehr für das Finden von Präbildern. Ihre Ergebnisse liefern explizite, konkrete Zahlen für die Sicherheit der vier Hauptvarianten von SHA-3 und zeigen, dass diese selbst gegen leistungsstarke Quantencomputer sicher bleiben, vorausgesetzt, diese Computer finden keinen Weg, spezifische strukturelle Schwächen im zugrunde liegenden Design auszunutzen.

Die Forscher waren sorgfältig darin, zwischen dem Beweis der Sicherheit des mathematischen Modells und der Sicherheit der tatsächlichen Hardware zu unterscheiden. Ihre Arbeit bestätigt, dass die kryptographischen Konstruktionen, die auf der darauf basierenden Zufallspermutation aufbauen, sicher sind, sofern die zugrunde liegende Zufallspermutation sich wie erwartet verhält. Sie haben nicht behauptet, dass die in der realen SHA-3-Standard verwendeten spezifische Permutation perfekt sei, sondern dass das Design selbst fundiert ist. Diese Unterscheidung ist entscheidend; sie bedeutet, dass das Versagen eines Systems wahrscheinlich auf einen Fehler in der spezifischen Implementierung der Permutation zurückzuführen wäre und nicht auf eine fundamentale Schwäche in der Art und Weise, wie das System aufgebaut ist. Durch die Straffung der mathematischen Grenzen haben die Forscher den Kryptographen ein mächtigeres Werkzeug zur Analyse zukünftiger Systeme gegeben, um sicherzustellen, dass die nächste Generation der digitalen Sicherheit mit einem klaren und genauen Verständnis der Quantenbedrohungen entworfen werden kann.

Der Kern ihrer Entdeckung liegt in der Handhabung der Beziehung zwischen den Abfragen des Angreifers und der Datenbank bekannter Antworten. In der alten Methode war die Verbindung zwischen der realen Maschine und dem Notizbuch etwas lose, was zu Fehlern führte, die mit der Anzahl der Fragen kumulierten. Der neue Ansatz behandelt das Notizbuch als ein direktes, kohärentes Spiegelbild des Zustands der Maschine. Sie konstruierten eine Brücke zwischen beiden, die die exakten mathematischen Beziehungen bewahrt und sicherstellt, dass das Notizbuch den wahren Zustand des Systems niemals aus den Augen verliert, egal wie viele Fragen gestellt werden. Diese Brücke wird durch eine Technik gebaut, die Informationen in distinkte Ebenen unterteilt – ähnlich wie die Organisation einer Bibliothek nach Stockwerken – und dann die Verbindungen zwischen ihnen sorgfältig normalisiert. Diese Normalisierung stellt sicher, dass die im Notizbuch berechneten Wahrscheinlichkeiten mit den Wahrscheinlichkeiten in der realen Welt übereinstimmen, wodurch die Drift eliminiert wird, die zuvor die Nützlichkeit der Methode einschränkte.

Diese Arbeit verbessert nicht nur einen einzelnen Beweis; sie stärkt das gesamte Fundament der Quanten-Sicherheitsanalyse für die symmetrische Kryptographie. Indem sie die Grenze des komprimierten Orakels von einem winzigen Bruchteil der möglichen Eingaben auf die Quadratwurzel verschoben haben, haben die Forscher die Tür zur Analyse von Systemen geöffnet, die zuvor außer Reichweite lagen. Die Ergebnisse legen nahe, dass der Quantenvorteil beim Brechen dieser spezifischen Arten kryptographischer Systeme nicht so groß ist, wie man befürchten könnte, sofern die Systeme über eine ausreichende Kapazität verfügen. Die Fähigkeit des Teams, explizite Konstanten und konkrete Schranken zu liefern, bedeutet, dass Ingenieure nun das exakte Sicherheitsniveau eines Systems berechnen können, anstatt sich auf vage Schätzungen zu verlassen. Diese Klarheit ist essenziell für den Aufbau der digitalen Infrastruktur der Zukunft, um sicherzustellen, dass unsere Daten auch in einer Ära, in der Quantencomputer Realität werden, geschützt bleiben.

Die Studie weitet ihre Erkenntnisse auch auf ideale Chiffren aus, welche die Bausteine für viele Verschlüsselungsverfahren sind. In diesem Modell hängt die Sicherheit von einer Familie von Permutationen ab, die jeweils durch einen anderen Schlüssel gesteuert werden. Die Forscher zeigten, dass ihre verbesserte Methode auch hier genauso gut funktioniert, selbst wenn der Angreifer das System in Superposition über verschiedene Schlüssel abfragen kann. Dies ist ein bedeutendes Ergebnis, denn es bedeutet, dass die Sicherheit dieser Systeme nicht einfach dadurch sinkt, dass viele Schlüssel involviert sind. Die Analyse bleibt stabil, unabhängig von der Anzahl der Schlüssel, und untermauert die Idee, dass die fundamentale Struktur dieser kryptographischen Designs gegenüber Quantenangriffen fundiert ist.

Letztendlich stellt diese Arbeit eine Reifung der Werkzeuge dar, die zur Untersuchung der Quantensicherheit eingesetzt werden. Sie nimmt eine Methode, die einst als zu fragil für einen strengen Beweis galt, und stärkt sie zu einem zuverlässigen Instrument. Die Forscher haben gezeigt, dass das komprimierte Orakel nicht nur eine heuristische Annäherung ist, sondern eine mathematisch fundierte Art, Quanteninformationen zu verfolgen. Damit haben sie der Kryptographie-Gemeinschaft eine klarere Sicht auf die Landschaft ermöglicht, die es erlaubt, Systeme zu entwerfen, die nachweislich sicher gegen die fortschrittlichsten Bedrohungen sind. Die Arbeit steht als Zeugnis für die Kraft, unsere mathematischen Modelle zu verfeinern, um die komplexen Realitäten der Quantenwelt besser widerzuspiegeln.