Malleability of transformations on the ciphertext in noisy Quantum public key encryption

Technisches Resümee: Malleabilität von Transformationen auf dem Geheimtext in der verrauschten Quanten-Public-Key-Verschlüsselung

Problemstellung
Diese Arbeit adressiert die Herausforderung, eine rigorose Formulierung für „ewige Sicherheit“ (everlasting security) bei der verrauschten Quanten-Public-Key-Verschlüsselung (QPKE) und dem Quantenschlüsselaustausch (QKD) in Gegenwart von Rauschen zu entwickeln. Während vorangegangene Arbeiten von Malavolta und Walter [3] einen Rahmen für ewige Sicherheit in einem rauschfreien Setting etablierten – und zeigten, dass Sicherheit nach nur zwei Interaktionsrunden zwischen Alice und Bob erreicht werden kann –, untersucht diese Arbeit, wie die Einführung von Rauschen die Sicherheitsschwellen des Protokolls beeinflusst. Speziell erforscht das Paper die Beziehung zwischen der Malleabilität von Geheimtexttransformationen und der Sicherheit des Protokolls, wenn Rauschen in die kryptographischen Operationen injiziert wird. Das Kernproblem besteht darin, die Negligibilitätsfunktion (die den Vorteil eines Angreifers quantifiziert) vom idealen rauschfreien Fall auf ein verrauschtes Setting zu generalisieren, unter Verwendung von Annahmen bezüglich der Malleabilität von Klartext- und Geheimtexttransformationen.

Methodik
Die Autoren verwenden eine Kombination aus Quanteninformationstheorie und abstrakter Kryptographie, um das verrauschte QPKE-QKD-Protokoll zu analysieren. Die Methodik ist um die folgenden Schlüsselkomponenten strukturiert:

1. Rauschinjektion via Malleabilität: Das Paper adaptiert das Konzept der Malleabilität, das ursprünglich von Maurer und Tackmann [9] zum Vergleich von „Authenticate then Encrypt“- und „Encrypt then Authenticate“-Protokollen eingeführt wurde. Die Autoren definieren verrauschte Transformationen auf dem Klartextraum, die durch drei Fehlerwahrscheinlichkeiten charakterisiert sind: Forwarding-Fehler (Weiterleitungsfehler), Deleting-Fehler (Löschfehler) und Reconstruction-Fehler (Rekonstruktionsfehler). Diese Fehler werden verwendet, um die Auswirkungen von Rauschen auf den Geheimtext zu modellieren.
2. Trace-Distanz und Gentle Measurement Lemma (GML): Ein zentrales technisches Werkzeug ist die Adaption des Gentle Measurement Lemma aus der Quanteninformationstheorie [18]. Die Autoren nutzen dieses Lemma, um eine obere Schranke für die Trace-Distanz zwischen zwei Quantenzuständen (die reale und ideale Experimente repräsentieren) basierend auf einer unteren Schranke der Spur eines spezifischen Operators zu etablieren. Dies ermöglicht die Generalisierung der Negligibilitätsfunktion in Gegenwart von Rauschen.
3. Noisy Quantum Polynomial-Time (NQPT) Maschinen: Das Paper formalisiert das verrauschte Setting durch die Definition von Noisy Quantum Polynomial-Time (NQPT) Maschinen und Noisy Completely Positive Trace Preserving (CPTP) Abbildungen. Diese Objekte ersetzen ihre rauschfreien Gegenstücke, um das Verhalten von Alice, Bob und dem Angreifer (Eve) unter verrauschten Bedingungen zu modellieren.
4. Projektionsoperatoren und Zustandszerlegung: Die Analyse beinhaltet die Konstruktion verrauschter Projektionsoperatoren ($\tilde{\Pi}$), die Rauschterme (z. B. $|\sigma + \text{noise}\rangle$) in den Standard-Projektionsoperator $\Pi$ integrieren, der im rauschfreien QPKE-QKD-Protokoll verwendet wird. Die Autoren leiten obere Schranken für die Trace-Distanz ab, indem sie die Verhältnisse von rauschfreien und verrauschten Projektionsoperatoren, Spur-Operationen sowie Ket/Bra-Zuständen vergleichen.
5. Ressourcen-theoretischer Ansatz: Das Paper nutzt den ressourcentheoretischen Rahmen aus [9] und definiert Sicherheit und Verfügbarkeit in Bezug auf die Ununterscheidbarkeit der durch Protokolle konstruierten Ressourcen. Dies schließt die Analyse der Komposition von Protokollen und die Ununterscheidbarkeit von Hybrid-Experimenten ein.

Zentrale Beiträge

• Formalisierung der verrauschten ewigen Sicherheit: Das Paper definiert „ewige Sicherheit“ für ein verrauschtes QPKE-Protokoll (Definition 37) und stellt fest, dass die Trace-Distanz zwischen verrauschten Hybrid-Experimenten durch eine Negligibilitätsfunktion abhängig vom verrauschten Sicherheitsparameter $\lambda'$ begrenzt ist.
• Generalisierung der Negligibilitätsfunktion: Die Autoren leiten eine Beziehung zwischen der Trace-Distanz im verrauschten Setting und der Negligibilitätsfunktion $NEGL(\lambda')$ ab. Sie zeigen, dass unter spezifischen Annahmen über das Rauschen die Negligibilitätsfunktion im verrauschten Setting mit einer höheren Sicherheitsschwelle im Vergleich zum rauschfreien Fall zusammenhängt.
• Trace-Distanz-Schranken via GML: Ein primärer technischer Beitrag ist die Ableitung einer oberen Schranke für die Trace-Distanz mittels des Gentle Measurement Lemma. Die Autoren zeigen, dass:
  $$Td(\tilde{Exp}, Exp) \lesssim \sqrt{NEGL(\lambda' - \lambda)}$$
  Dies wird erreicht, indem eine untere Schranke für die Spur eines spezifischen Operators bewiesen wird, der die Differenz zwischen verrauschten und rauschfreien Zuständen ($\tilde{\rho} - \tau$) beinhaltet.
• Malleabilitäts-Annahmen: Die Arbeit verknüpft explizit die Sicherheit des Protokolls mit der Malleabilität von Geheimtexttransformationen. Sie quantifiziert, wie die Forwarding-, Deleting- und Reconstruction-Fehlerwahrscheinlichkeiten verrauschter Transformationen mit der Sicherheits-Schwellenwert-Differenz zwischen den rauschfreien ($\lambda$) und verrauschten ($\lambda'$) Protokollen zusammenhängen.
• Computational Runtime Trade-offs: Das Paper analysiert die Trade-offs zwischen der Rechenlaufzeit verrauschter versus rauschfreier Protokolle (Kodierung, Dekodierung und Schlüsselgenerierung). Es legt nahe, dass, falls die Laufzeit des verrauschten Protokolls signifikant größer ist, die Sicherheits-Schwellenwert-Differenz $\lambda' - \lambda$ in einer spezifischen Weise skaliert, die potenziell mit exponentiellen oder polynomischen Funktionen der Laufzeitdifferenz zusammenhängt.

Ergebnisse

• Haupttheorem: Das Paper beweist, dass für ein verrauschtes QPKE-QKD-Protokoll, das Korrektheitsbedingungen erfüllt, die Trace-Distanz zwischen den verrauschten Hybrid-Experimenten (initialisiert mit Bits 0 und 1) durch die Negligibilitätsfunktion des verrauschten Sicherheitsparameters begrenzt ist:
  $$Td(\tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 1), \tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 0)) \lesssim NEGL(\lambda')$$
• Korollar zu Advantage-Funktionen: Die Autoren zeigen, dass die verrauschten Advantage-Funktionen für verschiedene Hybrid-Experimente ($\tilde{Adv}(0), \tilde{Adv}(1), \tilde{Adv}(2)$) alle durch dieselbe Negligibilitätsfunktion $NEGL(\lambda')$ begrenzt sind, was die Konsistenz der Sicherheitsdefinition über verschiedene experimentelle Setups hinweg bestätigt.
• Untere Schranke der Spur: Das Paper liefert eine detaillierte Ableitung, die zeigt, dass die Spur eines spezifischen Operators, der die Differenz zwischen verrauschten und rauschfreien Zuständen beinhaltet, durch eine Konstante mal den Kehrwert der Negligibilitätsfunktion von unten begrenzt ist, was eine Voraussetzung für die Anwendung des Gentle Measurement Lemma darstellt.

Bedeutung und Behauptungen
Das Paper beansprucht, einen rigorosen mathematischen Rahmen für die Erweiterung des Konzepts der ewigen Sicherheit auf die verrauschte Quanten-Public-Key-Verschlüsselung zu liefern. Durch die Adaption des Gentle Measurement Lemma demonstrieren die Autoren, dass die Sicherheitsgarantien des rauschfreien Protokolls auf das verrauschte Setting generalisiert werden können, sofern das Rauschen durch Malleabilitäts-Annahmen auf Geheimtexttransformationen charakterisiert wird.

Die Autoren betonen, dass die Einführung von Rauschen generell zu einer höheren Sicherheitsschwelle führt (was eine potenziell schwächere Sicherheitsgarantie in Bezug auf den Parameter $\lambda'$ impliziert), aber die abgeleiteten Schranken einen quantitativen Vergleich zwischen verrauschten und rauschfreien Protokollen ermöglichen. Die Arbeit wird als theoretischer Zwischenschritt präsentiert, wobei angemerkt wird, dass die Anforderungen an unbedingte und ewige Sicherheit experimentell schwer zu realisieren sind; der vorgeschlagene Rahmen bietet jedoch einen wertvollen Ausgangspunkt für die Analyse der Limitationen verrauschter Quantenberechnungen in kryptographischen Kontexten. Das Paper schließt mit dem Hinweis, dass die abgeleiteten Berechnungen zur Begrenzung der Trace-Distanz in Settings, die auf spieltheoretischen Ansätzen basieren, weiter untersucht werden könnten, schlägt jedoch keine spezifischen experimentellen Implementierungen oder unmittelbaren Anwendungen jenseits der theoretischen Analyse vor.