⚛️ quantum physics

On the Impossibility of Simulation Security for Quantum Functional Encryption

Diese Arbeit stellt die Unmöglichkeit der Erreichung von simulationssicherer Quanten-Funktionaler Verschlüsselung fest, indem sie aufzeigt, dass klassische Unmöglichkeitsresultate in das Quantenregime übergehen, wodurch bedingungslose Barrieren für unbeschränkte Herausforderungsnachrichten sowie die Unmöglichkeit unter schwächeren Annahmen wie pseudozufälligen Quantenzuständen oder Public-Key-Verschlüsselung für Szenarien mit beschränkten Schlüsseln bewiesen werden.

Ursprüngliche Autoren: Mohammed Barhoush, Arthur Mehta, Anne Müller, Louis Salvail

Veröffentlicht 2026-01-27

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Mohammed Barhoush, Arthur Mehta, Anne Müller, Louis Salvail

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Was ist Funktionale Verschlüsselung?

Stellen Sie sich vor, Sie haben einen verschlossenen Tresor (Verschlüsselung), der eine riesige Bibliothek von Büchern enthält.

Traditionelle Verschlüsselung: Entweder besitzen Sie den Generalschlüssel, um den ganzen Tresor zu öffnen und jedes Buch zu lesen, oder Sie haben keinen Schlüssel und können gar nichts lesen. Es ist ein „Alles-oder-Nichts“-Prinzip.
Funktionale Verschlüsselung (FE): Dies ist ein intelligenteres System. Sie geben einer bestimmten Person eine spezielle „magische Linse“ (einen funktionalen Schlüssel). Wenn diese Person durch diese Linse auf den verschlossenen Tresor blickt, kann sie nur das Ergebnis eines spezifischen mathematischen Problems auf den Büchern sehen (z. B. „Wie hoch ist die durchschnittliche Wortanzahl?“). Sie kann weder die eigentlichen Wörter, noch die Titel oder andere Daten sehen. Sie erhält nur die Antwort auf die spezifische Frage, die sie gestellt hat.

Das Ziel: „Simulationssicherheit“

In der Kryptographie wollen wir beweisen, dass dieses System perfekt sicher ist. Der Goldstandard dafür wird als Simulationssicherheit bezeichnet.

Denken Sie an einen Zaubertrick.

Die reale Welt: Ein Magier (der Verschlüsseler) schließt die Bücher ein, und ein Helfer (der Schlüsselinhaber) benutzt die Linse, um die Antwort zu erhalten.
Die Simulationswelt: Ein zweiter Magier (der Simulator) versucht, eine gefälschte Version des Tricks zu erstellen, ohne jemals die Bücher gesehen zu haben. Er kennt nur die gestellte Frage und die gegebene Antwort.

Wenn das Publikum (der Angreifer) nicht zwischen der realen Welt und der Simulationswelt unterscheiden kann, ist das System sicher. Es beweist, dass die Linse nichts über die Bücher verraten hat, außer der spezifischen Antwort.

Das Problem: Die „unmögliche“ Barriere

In der klassischen Welt (unter Verwendung normaler Computer und Bits) haben Forscher bereits bewiesen, dass man kein Funktionales Verschlüsselungssystem bauen kann, das in allen Situationen perfekt „Simulationssicher“ ist. Wenn man dem Angreifer erlaubt, zu viele Fragen zu stellen oder zu viele verschlossene Tresore zu sehen, bricht der Zaubertrick zusammen.

Die große Frage: Gilt diese „Unmöglichkeit“ auch in der Quantenwelt?
Quantencomputer nutzen „Qubits“, die viel mehr Informationen speichern können und sich seltsam verhalten (wie etwa an zwei Orten gleichzeitig zu sein). Vielleicht bietet die Quantenmechanik eine Hintertür, die es uns ermöglicht, ein perfektes, Simulationssicheres System zu bauen, wo klassische Computer gescheitert sind?

Die Antwort der Arbeit: Nein, die Barriere besteht weiterhin

Die Autoren dieser Arbeit sagen: Nein. Die klassischen Unmöglichkeitsergebnisse lassen sich weitgehend auf die Quantenwelt übertragen. Selbst mit den Superkräften der Quantenmechanik kann man in diesen spezifischen Szenarien kein perfekt Simulationssicheres Funktionales Verschlüsselungssystem bauen.

Sie beweisen dies anhand von drei verschiedenen „Fallen“ oder Argumenten:

1. Die „Zu viele Nachrichten“-Falle (Unbedingte Unmöglichkeit)

Das Szenario: Stellen Sie sich einen Angreifer vor, der verlangt, die Ergebnisse für viele verschiedene verschlossene Tresore (Ciphertexte) gleichzeitig zu sehen, aber dann nur eine spezielle Linse (funktionalen Schlüssel) anfordert, um sie alle zu dekodieren.
Die Analogie: Stellen Sie sich vor, Sie haben 1.000 verschlossene Boxen. Sie fragen nach einem einzigen Generalschlüssel, der alle Boxen öffnen kann.
Der Quanten-Twist: In der Quantenwelt könnte der Schlüssel vielleicht ein winziger, komprimierter Quantenzustand sein, der die Anweisungen für alle 1.000 Boxen enthält?
Das Ergebnis: Die Autoren beweisen, dass dies unmöglich ist. Es ist, als versuche man, die Anweisungen für 1.000 verschiedene Bücher in eine einzige, winzige Notiz zu quetschen. Selbst mit Quantenkompression kann man einfach nicht so viele Informationen in einen kleinen Quantenzustand pressen, ohne die Fähigkeit zu verlieren, die spezifischen Bücher später zu dekodieren. Wenn der Simulator versucht, die 1.000 Boxen vorzutäuschen, ohne deren Inhalt zu kennen, scheitert er, weil der „Schlüssel“, den er später generieren müsste, unmöglich groß wäre, um alle Antworten zu beschreiben.

2. Die „Winzige Schlüssel“-Falle (Succinct Schemes)

Das Szenario: Hierbei geht es um ein System, bei dem der „verschlossene Kasten“ (Ciphertext) unabhängig von der Komplexität des mathematischen Problems sehr klein sein soll.
Die Analogie: Stellen Sie sich ein System vor, bei dem Sie einen 100-seitigen Roman in einen winzigen Umschlag in der Größe einer Briefmarke einschließen können.
Der Quanten-Twist: Die Autoren verwenden das Konzept der Pseudozufälligen Quantenzustände (PRS). Dies sind Quantenzustände, die für jeden, der nicht über den geheimen Schlüssel verfügt, völlig zufällig aussehen, aber tatsächlich durch eine bestimmte Formel erzeugt werden.
Das Ergebnis: Sie beweisen, dass man diese scheinbar zufälligen Quantenzustände nicht „komprimieren“ kann. Wenn man versucht, einen zufälligen Quantenzustand in einen kleineren Raum zu schrumpfen (um einen winzigen Ciphertext zu erstellen), zerstört man die Information. Es ist wie der Versuch, eine Weltkarte in ein Quadratzoll zu falten; die Details gehen verloren. Daher kann ein System, das winzige Ciphertexte für komplexe mathematische Probleme verspricht, nicht Simulationssicher sein.

3. Die „Viele Schlüssel“-Falle (Public-Key-Verschlüsselung)

Das Szenario: Stellen Sie sich einen Angreifer vor, der einen verschlossenen Kasten sieht, aber erlaubt ist, nach vielen verschiedenen Linsen (funktionalen Schlüsseln) zu fragen, um herauszufinden, was sich darin befindet.
Die Analogie: Sie haben einen verschlossenen Kasten. Sie fragen nach 1.000 verschiedenen Linsen. Jede Linse soll eine andere Information offenbaren.
Der Quanten-Twist: Die Autoren verknüpfen dies mit der Public-Key-Verschlüsselung (PKE), einer Standardmethode, mit der wir heute E-Mails und Webseiten sichern. Sie zeigen, dass, falls eine perfekte Quanten-Funktionale-Verschlüsselung existierte, man damit die Sicherheit der Standard-Public-Key-Verschlüsselung brechen könnte.
Das Ergebnis: Da wir davon ausgehen, dass die Public-Key-Verschlüsselung sicher ist, impliziert dies, dass ein perfektes Quanten-Funktionales-Verschlüsselungssystem nicht existieren kann. Es ist ein „Beweis durch Widerspruch“: „Wenn dieses magische System existierte, würde es die Sicherheit des Internets brechen. Da die Sicherheit des Internets jedoch real ist, ist dieses magische System unmöglich.“

Zusammenfassung der Ergebnisse

Die Arbeit schließt im Wesentlichen die Tür für die Hoffnung, dass die Quantenmechanik uns vor den Einschränkungen der Funktionalen Verschlüsselung retten kann.

Klassische Unmöglichkeit: Wir wussten bereits, dass man kein perfekt „Simulationssicheres“ System in der klassischen Welt bauen kann, wenn der Angreifer zu viele Fragen stellt oder zu viele Nachrichten sieht.
Quanten-Realität: Die Autoren beweisen, dass die Quantenmechanik dies nicht behebt. Selbst mit Qubits, Verschränkung und Quantenschlüsseln verhindert die fundamentale Informations-Theorie ein perfekt Simulationssicheres Funktionales Verschlüsselungssystem in diesen Szenarien.

Sie zeigen, dass die „Barriere“ nicht nur eine Schwäche klassischer Computer ist, sondern eine fundamentale Grenze dessen, wie Information (selbst Quanteninformation) komprimiert und verborgen werden kann.

Was dies bedeutet (und was es nicht bedeutet)

Es bedeutet NICHT, dass Funktionale Verschlüsselung nutzlos ist. Wir können immer noch Systeme bauen, die „gut genug“ (Unterscheidbarkeits-sicher / Indistinguishability-Secure) für viele reale Anwendungen sind.
Es bedeutet NICHT, dass Quantenverschlüsselung gebrochen ist. Es bedeutet nur, dass eine ganz bestimmte, sehr hochgradige Definition von „perfekter Sicherheit“ (Simulationssicherheit) unerreichbar ist, genau wie dies in der klassischen Welt der Fall war.
Es bedeutet, dass Forscher, die nach dem „Heiligen Gral“ der Quanten-Funktionalen-Verschlüsselung suchen, aufhören sollten, diese spezifische Art der perfekten Sicherheit anzustreben, da die Mathematik sagt, dass sie unmöglich ist.

Technische Zusammenfassung: Über die Unmöglichkeit der Simulationsbasierter Sicherheit für Quanten-Funktionale Verschlüsselung

Problemstellung
Funktionale Verschlüsselung (Functional Encryption, FE) ist ein kryptographisches Primitiv, das einen feingranularen Zugriff auf verschlüsselte Daten ermöglicht, wobei ein Benutzer, der einen funktionalen Schlüssel $fk_F$ besitzt, $F(m)$ aus einer Verschlüsselung von $m$ berechnen kann, ohne etwas anderes zu erfahren. Die stärkste Sicherheitsvorstellung für FE ist die simulationsbasierte Sicherheit (SIM-Sicherheit), die fordert, dass alles, was ein Angreifer aus dem Chiffretext und den funktionalen Schlüsseln berechnen kann, unter Verwendung nur des Funktionsoutputs simuliert werden kann.

Während klassische Unmöglichkeitsresultate etabliert haben, dass SIM-sichere FE für allgemeine polynomielle Schaltkreise unter bestimmten Abfragemodellen (z. B. viele Chiffretexte mit einem einzigen adaptiven Schlüssel oder ein einziger Chiffretext mit vielen nicht-adaptiven Schlüsseln) nicht erreichbar ist, beruhen diese Beweise auf inhärent klassischen Argumenten. Eine kritische offene Frage blieb: Erstrecken sich diese klassischen Unmöglichkeiten auch auf das Quantenregime? Speziell: Können Quantenressourcen (Quantenchiffretexte, Quantenfunktionale Schlüssel oder Quantenöffentliche Schlüssel) diese Barrieren überwinden, um SIM-sichere Quanten-Funktionale Verschlüsselung (QFE) zu realisieren?

Methodik
Die Autoren adressieren diese Frage, indem sie klassische Unmöglichkeitsbeweise auf das Quantensetting erweitern und diese anpassen, um mit Quantenzuständen und -operationen umzugehen. Die Methodologie umfasst drei distinkte Unmöglichkeitsbeweise, die jeweils auf eine andere Sicherheitsvariante der QFE abzielen:

Informationstheoretische Kompressionsargumente: Die Autoren interpretieren die Aufgabe des Simulators in einem SIM-Sicherheitsspiel als Informationskompressionsproblem. Sie zeigen, dass die Existenz eines SIM-sicheren Schemas die Existenz eines Kompressionsalgorithmus implizieren würde, der in der Lage ist, große Mengen an Information (Nachrichten oder Zustände) in einen kleinen Quantenzustand (den funktionalen Schlüssel oder Chiffretext) zu komprimieren und dabei eine perfekte Wiederherstellung zu ermöglichen.
Quanten-Inkompressibilitäts-Lemmata:
- Für den Fall vieler Chiffretexte nutzen sie ein Resultat aus [20] bezüglich der verschränkungsunterstützten Kommunikation, um zu zeigen, dass $n$ Bits nicht zuverlässig aus weniger als $n/2$ Qubits wiederhergestellt werden können.
- Für den Fall des sukzessiven (kompakten) Schemas beweisen sie ein neuartiges Lemma bezüglich der Inkompressibilität von Pseudozufallszuständen (Pseudorandom States, PRS). Sie zeigen, dass die Kompression eines $n$ -Qubit-PRS in $n-k$ Qubits die Struktur fast vollständig irreversibel zerstört, wobei die erwartete Fidelity der Wiederherstellung exponentiell mit der Menge der Kompression sinkt. Dies wird unter Verwendung der Beziehung zwischen durchschnittlicher Fidelity und Verschränkungsfidelity kombiniert mit Levys Lemma über die Konzentration des Maßes für Haar-zufällige Zustände bewiesen.
Reduktionen auf Standard-Kryptographische Annahmen:
- Für den Fall vieler-Schlüssel-Abfragen konstruieren sie eine Reduktion von der Existenz einer SIM-sicheren QFE zum Brechen der Public-Key-Verschlüsselung (PKE). Sie zeigen, dass ein Simulator für ein 1-M-NA (ein Nachricht, viele Abfragen, nicht-adaptiv) QFE-Schema als Informationskompressor für mehrere unabhängige PKE-Chiffretexte agieren würde, was die Sicherheit des zugrunde liegenden PKE-Schemas verletzen würde.

Wesentliche Beiträge und Ergebnisse

Das Paper etabliert drei wesentliche Unmöglichkeitsresultate für Secret-Key QFE (was unmittelbar die Unmöglichkeit für Public-Key QFE impliziert):

Unbedingte Unmöglichkeit von M-1-AD SIM-sicherer QFE:
- Setting: Der Angreifer fordert die Verschlüsselung vieler Nachrichten ( $M$ ) an und erhält dann einen einzigen adaptiven funktionalen Schlüssel für die Identitätsfunktion ($1$-AD).
- Resultat: Ein solches Schema existiert nicht.
- Mechanismus: Der Simulator muss $n$ Chiffretexte generieren, ohne die Nachrichten zu kennen. Nach Erhalt des Identitäts Schlüssels muss er alle $n$ Nachrichten wiederherstellen. Dies erfordert die Kompression von $n$ zufälligen Nachrichten in einen funktionalen Schlüssel der Größe, die durch ein Polynom $p \ll n$ begrenzt ist. Die Autoren beweisen, dass dies selbst mit Quantenzuständen unmöglich ist, da es die informationstheoretischen Grenzen der Kompression klassischer Information in einen kleineren Quantenzustand verletzt.
Bedingte Unmöglichkeit von Sukzessiver 1-1-NA SIM-sicherer QFE:
- Setting: Der Angreifer fordert eine einzige Nachricht und einen einzigen nicht-adaptiven funktionalen Schlüssel an. Das Schema ist sukzessiv (der Chiffretext ist unabhängig von der Funktionsgröße).
- Annahme: Existenz von Pseudozufallszuständen (PRS).
- Resultat: Kein solches Schema existiert.
- Mechanismus: Die Autoren zeigen, dass eine sukzessive QFE für die Schaltungsklasse der PRS-Generatoren die Kompression und Dekompression von PRS ermöglichen würde. Sie beweisen, dass PRS inkompressibel sind (eine Eigenschaft, die in manchen Kontexten stärker als PRF ist, da PRF $\implies$ PRS gilt, aber die Umkehrung nicht bekannt ist). Wenn eine sukzessive QFE existierte, könnte man PRS von Haar-zufälligen Zuständen unterscheiden, indem man prüft, ob der komprimierte Zustand wiederhergestellt werden kann, was die PRS-Annahme brechen würde.
Bedingte Unmöglichkeit von 1-M-NA SIM-sicherer QFE:
- Setting: Der Angreifer fordert einen einzigen Chiffretext und viele nicht-adaptive funktionale Schlüssel an.
- Annahme: Existenz von Public-Key-Verschlüsselung (PKE) mit klassischen Schlüsseln.
- Resultat: Kein solches Schema existiert.
- Mechanismus: Die Autoren konstruieren einen Angriff, bei dem der Angreifer den QFE-Simulator nutzt, um $n$ unabhängige PKE-Chiffretexte (die verschiedene Nachrichten verschlüsseln) in einen einzigen QFE-Chiffretext zu komprimieren. Wenn der Simulator erfolgreich ist, erlaubt dies die Wiederherstellung aller $n$ Nachrichten aus dem einzelnen komprimierten Chiffretext und den funktionalen Schlüsseln. Dies verletzt die Sicherheit des zugrunde liegenden PKE-Schemas. Bemerkenswert ist, dass dieses Resultat für nicht-sukzessive Schemata gilt, im Gegensatz zum PRS-basierten Resultat.

Bedeutung und Behauptungen

Das Paper behauptet, die zentrale Frage zu klären, ob Quantenressourcen die klassischen Barrieren für SIM-sichere FE umgehen können. Die Autoren kommen zu dem Schluss, dass die klassischen Unmöglichkeiten weitgehend in die Quantenwelt übergehen, obwohl die Beweise neue technische Werkzeuge erfordern, um mit Quantenzuständen umzugehen.

Nuancierte Barrieren: Die Resultate sind nuancierter als die klassischen. Beispielsweise beruht die Unmöglichkeit der 1-M-NA SIM-Sicherheit im Quantensetting auf der Annahme von PKE (oder PRS für sukzessive Schemata), während das klassische Resultat unbedingt ist (da klassische FE $\implies$ PRF). Dies verdeutlicht, dass die Barriere zwar existiert, die spezifischen kryptographischen Annahmen im Quantenregime jedoch variieren.
Unabhängigkeit der Annahmen: Das Paper betont, dass die verwendeten Annahmen (PRS und PKE) inkomparabel sind. PKE ist bekannt davon getrennt zu sein von Einwegfunktionen (und somit PRS), und es existiert keine Implikation in die Gegenrichtung. Daher liefern die beiden bedingten Unmöglichkeitsresultate unabhängige Evidenz gegen die Existenz von SIM-sicherer QFE.
Neuheit der Beweise: Die Autoren führen eine neuartige Inkompressibilitäts-Eigenschaft für Pseudozufallszustände ein, die ihrer Meinung nach von eigenem Interesse sein kann. Sie liefern zudem den ersten Unmöglichkeitsbeweis für 1-M-NA SIM-sichere QFE, der nicht auf der Sukzessivität des Schemas beruht.
Geltungsbereich: Die Resultate gelten für allgemeine Schaltungsklassen. Die Autoren räumen ein, dass eingeschränkte Klassen (z. B. „preimage sampleable“ Schaltungen) oder spezifische Modelle (wie das Modell mit begrenztem Quantenspeicher) möglicherweise noch SIM-Sicherheit erlauben, aber für allgemeine QFE scheint das Ziel der simulationsbasierten Sicherheit unerreichbar zu sein.

Zusammenfassend demonstriert das Paper, dass die fundamentale Spannung zwischen der in einem Chiffretext enthaltenen Information und der begrenzten Größe eines funktionalen Schlüssels (oder umgekehrt) im Quantensetting fortbesteht und die Realisierung des stärksten Sicherheitskonzepts für funktionale Verschlüsselung verhindert.