Technisches Resümee: Auf unbedingungslose unklonbare Verschlüsselung zugehend

1. Problemstellung

Unklonbare Verschlüsselung ist ein kryptographisches Primitiv, das darauf ausgelegt ist, klassische Nachrichten in Quanten-Ciphertexte zu verschlüsseln, sodass zwei Quanten-Adversäre, die den Entschlüsselungsschlüssel und die aus dem Ciphertext abgeleitete Quanten-Seiteninformation besitzen, die Nachricht nicht gleichzeitig entschlüsseln können. Während Verfahren, die diese Eigenschaft im Quantum Random Oracle Model (QROM) und unter spezifischen rechnerischen Annahmen (z. B. Obfuskation) erreichen, vorgeschlagen wurden, bleibt die Existenz eines unbedingungssicher unklonbaren Verschlüsselungsverfahrens im Plain Model ein offenes Problem.

Der Kern dieser Herausforderung ist das „unklonbare Bit“-Problem: der einfachste Fall, bei dem ein einzelnes klassisches Bit ($m \in \{0, 1\}$) verschlüsselt wird. Trotz seiner Einfachheit wurde bisher kein Verfahren nachgewiesen, das die Eigenschaft der unklonbaren Unterscheidbarkeit ohne rechnerische Annahmen erfüllt. Die Sicherheit eines solchen Verfahrens wird durch ein „No-Cloning-Spiel“ definiert, bei dem ein Pirat (P) versucht, einen Quanten-Ciphertext in zwei Register für Bob (B) und Charlie (C) aufzuspalten. B und C müssen, jeweils im Besitz des geheimen Schlüssels, das ursprüngliche Bit unabhängig vonean erraten. Das Verfahren ist sicher, wenn die Wahrscheinlichkeit, dass sowohl B als auch C korrekt raten, durch $1/2 + \text{negl}(\lambda)$ (starke Sicherheit) oder $1/2 + f(\lambda)$, wobei $f(\lambda) \to 0$, (schwache Sicherheit) begrenzt ist.

2. Methodik

Die Autoren schlagen ein Kandidatenverfahren für das unklonbare Bit vor, das auf der Struktur von Clifford-Algebren und paarweise antikommutierenden Pauli-Strings basiert.

Das Kandidatenverfahren

• Schlüsselgenerierung: Ein Schlüssel $k$ wird gleichmäßig aus einer Menge der Größe $K = 2^\lambda$ (für gerades $\lambda$) oder $K = 2^\lambda + 1$ (für ungerades $\lambda$) gezogen.
• Verschlüsselung: Die Nachricht $m \in \{0, 1\}$ wird in einen Quantenzustand $\rho_{m,k}$ kodiert, welcher der normierte Projektor auf den Eigenwert $(-1)^m$ eines spezifischen hermiteschen unitären Operators $\Gamma_k$ ist. Die Menge $\{\Gamma_1, \dots, \Gamma_K\}$ besteht aus paarweise antikommutierenden Operatoren (z. B. spezifischen Pauli-Strings), die auf einem Hilbertraum der Dimension $d = 2^\lambda$ wirken.
  $$\rho_{m,k} = \frac{I + (-1)^m \Gamma_k}{2}$$
• Entschlüsselung: Der Empfänger misst den Zustand in der Eigenbasis von $\Gamma_k$, die dem Schlüssel $k$ entspricht.

Analytischer Rahmen

Die Sicherheitsanalyse reduziert das No-Cloning-Spiel auf ein Optimierungsproblem über die Operatornorm eines spezifischen Operators $W_K$. Die Gewinnwahrscheinlichkeit wird nach oben begrenzt durch:
$$\Pr[\text{win}] \leq \frac{1}{2} + \frac{1}{2K} \sup_{\{U_k\}} \left\| \sum_{k=1}^K \left( \Gamma_k \otimes (U_k \otimes I + I \otimes U_k) + I \otimes U_k \otimes U_k \right) \right\|_{\text{op}}$$
wobei $U_k$ die Messstrategien der Adversäre darstellen.

Die Autoren formulieren Konjektur 1 und postulieren, dass für jede Menge von paarweise antikommutierenden hermiteschen unitären Operatoren $\Gamma_k$ und jede hermitesche unitäre Operatoren $U_k$ gilt:
$$\left\| \sum_{k=1}^K \left( \Gamma_k \otimes (U_k \otimes I + I \otimes U_k) + I \otimes U_k \otimes U_k \right) \right\|_{\text{op}} \leq K + 2\sqrt{K}$$
Falls dies wahr ist, impliziert dies eine obere Schranke für die Gewinnwahrscheinlichkeit von $1/2 + \frac{1}{2\sqrt{K}}$, was eine schwache Sicherheit demonstriert.

Um diese Konjektur zu verifizieren, setzen die Autoren folgende Methoden ein:

1. Sum-of-Squares (SoS) Dekompositionen: Konstruktion expliziter Polynomial-Zertifikate, um die Nicht-Negativität des Operators $P_K = (K + 2\sqrt{K})I - W_K$ zu beweisen.
2. NPA-Hierarchie (Navascués-Pironio-Acín): Nutzung der ersten und zweiten Ebene dieser Hierarchie (dual zu SoS), um semidefinierte Programme (SDPs) zu formulieren, die obere Schranken auf die Operatornorm liefern.
3. Seesaw (Alternierende Optimierung): Ein heuristischer numerischer Algorithmus, um untere Schranken auf das maximale Eigenwert von $W_K$ zu finden, indem iterativ über den Zustandsvektor und die Messoperatoren optimiert wird.

3. Zentrale Beiträge und Ergebnisse

Analytische Beweise

• Verifizierung für kleines $K$: Die Autoren liefern explizite SoS-Dekompositionen und analytische Beweise, die Konjektur 1 für $K \leq 7$ bestätigen.
• Asymptotische Schranke: Unter Verwendung der analytischen Lösung der ersten Ebene der NPA-Hierarchie leiten sie eine asymptotische obere Schranke für die Gewinnwahrscheinlichkeit ab. Für $K > 7$ beträgt die Schranke $5/8 + \frac{1}{2(K-2)} - \frac{1}{4K}$, welche gegen $5/8$ konvergiert, wenn $K \to \infty$. Dies ist eine signifikante Verbesserung gegenüber der trivialen Schranke von 1.

Numerische Evidenz

• NPA Ebene 2: Die Autoren erweitern die Analyse auf die zweite Ebene der NPA-Hierarchie und lösen die resultierenden SDPs numerisch. Sie bestätigen, dass die Konjektur für $K \leq 17$ gilt.
• Beste bekannte Schranke: Für $K=35$ liefert die NPA-Ebene-2-Optimierung eine numerische obere Schranke von etwa 0,5980. Die Autoren geben an, dass dies nach ihrem Kenntnisstand die beste bekannte unbedingte obere Schranke für die Sicherheit unklonbarer Verschlüsselung ist.
• Seesaw-Methode: Für $K=18$ fand der alternierende Optimierungsalgorithmus keine Instanzen, die die Konjektur verletzen, was heuristische Belege dafür liefert, dass die Schranke auch für größere $K$ hält.

Unterscheidbarkeit

Das Papier beweist, dass das Kandidatenverfahren eine relaxierte Form der Unterscheidbarkeits-Sicherheit erfüllt. Speziell konvergiert die Wahrscheinlichkeit, dass ein Adversär zwischen der Verschlüsselung eines zufälligen Bits und eines festen Bits unterscheidet, mit einer Rate von $O(1/\sqrt{K})$ gegen $1/2$.

4. Bedeutung und Ansprüche

Das Papier präsentiert ein Kandidatenverfahren für unbedingslos unklonbare Verschlüsselung und adressiert damit ein fundamentales offenes Problem der Quantenkryptographie. Obwohl die Autoren nicht behaupten, die Sicherheit für alle $K$ bewiesen zu haben, liefern sie:

1. Starke Evidenz: Eine Kombination aus rigorösen analytischen Beweisen für kleine Parameter und umfangreicher numerischer Verifizierung bis $K=17$ (sowie heuristischen Prüfungen für $K=18$).
2. Verbesserte Schranken: Die Ableitung einer asymptotischen oberen Schranke von $5/8$ und einer numerischen Schranke von $\sim 0,5980$, welche die engsten bekannten unbedingten Schranken für dieses Primitiv sind.
3. Fundament für zukünftige Arbeit: Die Arbeit etabliert einen konkreten Rahmen (basierend auf Clifford-Algebren und Operatornorm-Optimierung) zur Untersuchung unbedingter Unklonbarkeit, wodurch die Beschränkungen des QROM oder rechnerischer Annahmen überwunden werden.

Die Autoren merken explizit an, dass der Beweis der Konjektur für beliebig große $K$ eine offene Herausforderung bleibt, was den ersten unbedingten Beweis für unklonbare Verschlüsselung im Plain Model darstellen würde. Sie räumen zudem ein, dass ihr Verfahren eine „schwache“ Sicherheit (quadratische Konvergenz) statt der „starken“ Sicherheit (exponentieller Abfall) erreicht, wie sie in früheren Arbeiten definiert wurde, und lassen die Konstruktion eines stark sicheren Verfahrens als zukünftiges Ziel offen.