2025-11-14T17:16:11.719199

Quantum One-Time Protection of any Randomized Algorithm

Gunn, Movassagh
The meteoric rise in power and popularity of machine learning models dependent on valuable training data has reignited a basic tension between the power of running a program locally and the risk of exposing details of that program to the user. At the same time, fundamental properties of quantum states offer new solutions to data and program security that can require strikingly few quantum resources to exploit, and offer advantages outside of mere computational run time. In this work, we demonstrate such a solution with quantum one-time tokens. A quantum one-time token is a quantum state that permits a certain program to be evaluated exactly once. One-time security guarantees, roughly, that the token cannot be used to evaluate the program more than once. We propose a scheme for building quantum one-time tokens for any randomized classical program, which include generative AI models. We prove that the scheme satisfies an interesting definition of one-time security as long as outputs of the classical algorithm have high enough min-entropy, in a black box model. Importantly, the classical program being protected does not need to be implemented coherently on a quantum computer. In fact, the size and complexity of the quantum one-time token is independent of the program being protected, and additional quantum resources serve only to increase the security of the protocol. Due to this flexibility in adjusting the security, we believe that our proposal is parsimonious enough to serve as a promising candidate for a near-term useful demonstration of quantum computing in either the NISQ or early fault tolerant regime.
academic

Quantenschutz mit einmaliger Verwendung für beliebige randomisierte Algorithmen

Grundlegende Informationen

  • Paper-ID: 2411.03305
  • Titel: Quantum One-Time Protection of any Randomized Algorithm
  • Autoren: Sam Gunn, Ramis Movassagh (Google Quantum AI)
  • Klassifizierung: quant-ph cs.CR
  • Veröffentlichungsdatum: 3. Januar 2025 (arXiv v2)
  • Paper-Link: https://arxiv.org/abs/2411.03305v2

Zusammenfassung

Die schnelle Entwicklung von Machine-Learning-Modellen und die Abhängigkeit von wertvollen Trainingsdaten haben den grundlegenden Widerspruch zwischen der Bequemlichkeit der lokalen Programmausführung und dem Risiko der Preisgabe von Programmdetails an Benutzer erneut verschärft. Gleichzeitig bieten die fundamentalen Eigenschaften von Quantenzuständen neue Lösungsansätze für die Sicherheit von Daten und Programmen, die nur minimale Quantenressourcen erfordern und Vorteile jenseits der Rechenzeit bieten. Diese Arbeit demonstriert solche Lösungen durch Quantenschutz mit einmaliger Verwendung.

Quantenschutz mit einmaliger Verwendung ist ein Quantenzustand, der es ermöglicht, dass ein bestimmtes Programm genau einmal ausgewertet wird. Die Sicherheit mit einmaliger Verwendung garantiert, dass das Token nicht für mehrfache Programmauswertungen verwendet werden kann. Die Autoren präsentieren ein Schema zur Konstruktion von Quantenschutz-Tokens mit einmaliger Verwendung für beliebige randomisierte klassische Programme (einschließlich generativer KI-Modelle) und beweisen im Black-Box-Modell, dass das Schema eine interessante Sicherheitsdefinition mit einmaliger Verwendung erfüllt, vorausgesetzt, die Ausgabe des klassischen Algorithmus hat ausreichend hohe Minentropie.

Forschungshintergrund und Motivation

Problemdefinition

Die Kommerzialisierung von Software steht vor einem grundlegenden Dilemma: Wie kann Software verteilt werden, ohne die Eigentumsrechte aufzugeben? Traditionelle Lösungen weisen inhärente Kompromisse zwischen Verfügbarkeit und Exklusivität auf:

  1. Programmverschleierungsschema: Verteilung verschleierter Softwareversionen, aber mit Piraterie-Risiko und unbegrenzter Ausführung durch Benutzer
  2. Server-Abfrage-Schema: Software auf dem Server halten und auf Benutzerabfragen reagieren, aber mit verminderter Verfügbarkeit und erforderlicher kontinuierlicher Kommunikation

Bedeutung des Problems

Im Zeitalter generativer KI wird dieses Problem noch kritischer, da:

  • Software möglicherweise äußerst wertvoll ist
  • Private Informationen preisgegeben werden könnten
  • Pay-per-Query-Modelle zunehmend verbreitet sind

Einschränkungen bestehender Methoden

Klassische Informationen können immer kopiert werden; sobald Software verteilt ist, können Benutzer sie beliebig oft abfragen oder kopieren. Diese Einschränkung macht es unmöglich, dass traditionelle Ansätze gleichzeitig hohe Verfügbarkeit und starke Exklusivität erreichen.

Vorteile der Quantenlösung

Die Nicht-Klonbarkeit von Quanteninformation bietet Möglichkeiten zur Verbesserung bestehender Lösungen:

  • Quantenkopierungsschutz: Verbesserung von Schema (1), Verhinderung von Programmkopien bei unbegrenzter Ausführung
  • Quantenprogramme mit einmaliger Verwendung: Verbesserung von Schema (2), Beseitigung der Online-Kommunikation in Pay-per-Query-Modellen

Kernbeiträge

  1. Erstes universelles Quantentokenisierungsschema für Programme: Präsentation des ersten universellen Schemas zur Verwendung von Quanteninformation zum Schutz beliebiger randomisierter Algorithmen, nicht beschränkt auf spezifische kryptographische Funktionen
  2. Quantenressourcenbedarf unabhängig von Programm-Komplexität: Größe und Komplexität des Quantentokens sind völlig unabhängig vom geschützten Programm
  3. Theoretischer Sicherheitsbeweis: Beweis, dass das Schema im Black-Box-Modell die Sicherheitsdefinition mit einmaliger Verwendung erfüllt
  4. Praktische Überlegungen: Das Schema ist ausreichend prägnant für eine Implementierung in der NISQ- oder frühen fehlertoleranten Quantencomputing-Ära

Methodische Details

Aufgabendefinition

Konstruktion von Quantenschutz-Tokens mit einmaliger Verwendung zum Schutz beliebiger randomisierter Algorithmen f: X × R → Y, so dass:

  • Das Token ermöglicht die Auswertung des Programms genau einmal
  • Sicherheitsgarantie mit einmaliger Verwendung bietet
  • Keine kohärente Implementierung des Programms auf dem Quantencomputer erforderlich ist

Kernkonstruktion (Construction 2)

Kryptographische Primitive

Das Schema basiert auf drei kryptographischen Primitiven:

  1. (AuthKeyGen, AuthTokenGen, Sign, Verify): Quantenauthentifizierungsschema mit einmaliger Verwendung
  2. Obf: Klassischer Programmverschleierungsmechanismus
  3. H: Hash-Funktion (modelliert als Zufallsorakel)

Token-Struktur

Das Programmtoken besteht aus zwei Teilen:

  • |ψ⟩: Nicht-klonbarer Quantenzustand unabhängig von f
  • Obf(P): Verschleierter klassischer Schaltkreis P abhängig von f

Algorithmus-Ablauf

KeyGen(1^λ, f):

  1. Stichprobe sk ← AuthKeyGen(1^λ)
  2. Definition des klassischen Schaltkreises P: X × {0,1}^m → Y ∪ {⊥}
    • Berechnung von Verify(sk, (x,z)), Ausgabe ⊥ bei Ablehnung
    • Andernfalls Ausgabe von f(x; H(x,z))
  3. Berechnung der Verschleierung P̂ = Obf(P)
  4. Ausgabe von (sk, P̂)

TokenGen(sk):

  1. Berechnung des Authentifizierungstokens mit einmaliger Verwendung |tk⟩ ← AuthTokenGen(sk)
  2. Ausgabe von |tk⟩

TokenEval(x, |tk⟩, P̂):

  1. Berechnung von z ← Sign(x, |tk⟩)
  2. Berechnung und Ausgabe von P̂(x,z)

Quantenauthentifizierungsschema mit einmaliger Verwendung

Definition (Definition 1)

Das Quantenauthentifizierungsschema mit einmaliger Verwendung muss erfüllen:

  • Korrektheit: Legitime Signaturen bestehen die Verifikation
  • Nicht-Fälschbarkeit mit einmaliger Verwendung: Kein polynomieller Gegner kann zwei verschiedene gültige Signaturpaare erzeugen

Konkrete Konstruktion (Construction 1)

Basierend auf versteckten Unterraum-Zuständen für Single-Bit-Authentifizierung:

AuthKeyGen(1^λ): Stichprobe des zufälligen Unterraums A ⊆ F₂^λ mit Dimension λ/2

AuthTokenGen(A): Ausgabe von |A⟩ = 2^(-λ/4) ∑_{a∈A} |a⟩

Sign(x, |A⟩):

  • Falls x = 0: Messung in der Standardbasis und Ausgabe des Ergebnisses
  • Falls x = 1: Messung in der Hadamard-Basis und Ausgabe des Ergebnisses

Verify(A, (x,z)): Verifikation, ob z im entsprechenden Unterraum liegt

Technische Innovationen

  1. Programmunabhängige Quantenressourcen: Der Quantenzustand |ψ⟩ ist unabhängig vom geschützten Programm, was den Schutz komplexer Programme mit kleinen Quantengeräten ermöglicht
  2. Zufallsbindungsmechanismus: Durch H(x,z) wird die Zufälligkeit bestimmt und Eingabe, Authentifizierung und Ausgabe effektiv "vermischt"
  3. Kollaps-Hash-Funktionseigenschaft: Nutzung der Quanteneigenschaft, dass die Messung der Ausgabe Eingabe und Authentifizierungsetikett kollabiert

Theoretische Analyse

Sicherheitsdefinitionen

Black-Box-Spiel für Programme mit einmaliger Verwendung G^BB-OTP

  1. Der Gegner erhält |ψ⟩ und Quantenorakel-Zugriff auf P̂
  2. Der Gegner reicht Quantenabfragen ein, der Herausforderer berechnet P̂ und misst das Ergebnis y
  3. Falls y = ⊥, bricht das Spiel ab und der Gegner verliert
  4. Der Gegner reicht die zweite Abfrage ein, der Herausforderer misst y'
  5. Falls y' ∉ {y, ⊥}, gewinnt der Gegner

Hauptsätze

Satz 2: Wenn für jedes x ∈ X die Minentropie von f(x;r) über zufälliges r mindestens poly(λ) beträgt und das Quantenauthentifizierungsschema mit einmaliger Verwendung sicher ist, dann ist Construction 2 für f Black-Box-sicher mit einmaliger Verwendung.

Beweis-Kern: Kollaps-Hash-Funktionen

Lemma 1: Sei f: {0,1}^m × {0,1}^n → Y. Wenn für alle x die Minentropie von f(x;r) über zufälliges r mindestens τ beträgt, dann ist die Funktion g^H: x ↦ f(x;H(x)) kollapsierbar, wenn H ein Zufallsorakel ist, mit Vorteil O(q³·2^(-τ)).

Beweis-Strategie

Verwendung der Komprimierungs-Orakel-Technik:

  1. Beweis, dass Invert_f und CPhsO fast austauschbar sind
  2. Nutzung der Minentropie-Bedingung zur Begrenzung der Kollisionswahrscheinlichkeit
  3. Realisierung des Eingabe-Kollapses durch Messung der Ausgabe

Experimente und Anwendungen

Quantenressourcenbedarf

  • Bei Verwendung des Authentifizierungsschemas mit einmaliger Verwendung von CLLZ21 benötigt der Benutzer nur:
    • Speicherung eines Quantenzustands konstanter Größe
    • Messungen in der Standardbasis und Hadamard-Basis

Praktische Überlegungen

  1. Kurzfristige Machbarkeit: Quantenressourcen-Anforderungen unabhängig von Programm-Komplexität
  2. Skalierbare Sicherheit: Zusätzliche Quantenressourcen nur zur Erhöhung der Sicherheit
  3. Ersatz klassischer Kommunikation: Quantenkommunikation kann durch Remote-State-Preparation-Protokolle durch klassische Kommunikation ersetzt werden

Anwendungsszenarien

  • Schutz generativer KI-Modelle
  • Pay-per-Query-Softwaredienste
  • Sensible Programme, die offline ausgeführt werden müssen

Verwandte Arbeiten

Historische Entwicklung

  • GKR08: Ursprüngliche Untersuchung von Programmen mit einmaliger Verwendung (ohne Quantencomputing)
  • BGS13: Konzept von Quantenprogrammen mit einmaliger Verwendung, Beweis der Unmöglichkeit für deterministische Programme
  • BS23: Schutz von Signaturfunktionen im Standardmodell
  • GLR+24: Parallele unabhängige Arbeit mit stärkeren Sicherheitsdefinitionen

Beitrag dieses Papers im Vergleich

  • Erstes universelles Schema zum Schutz beliebiger randomisierter Algorithmen
  • Prägnanter eigenständiger Sicherheitsbeweis
  • Praktisch orientierte Designüberlegungen

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Quantenschutz-Tokens mit einmaliger Verwendung können beliebige randomisierte klassische Programme schützen
  2. Sicherheit hängt von hoher Minentropie der Programmausgabe ab
  3. Quantenressourcenbedarf ist unabhängig von Programm-Komplexität
  4. Das Schema ist in der NISQ-Ära implementierbar

Einschränkungen

  1. Hohe Entropie-Anforderung: Programmausgabe muss ausreichend hohe Minentropie haben
  2. Black-Box-Modell: Sicherheitsbeweis im idealisierten Black-Box-Modell
  3. Einschränkung auf randomisierte Programme: Nicht anwendbar auf deterministische Programme (durch Unmöglichkeitsergebnis von BGS13 begrenzt)
  4. Komplexe klassische Kommunikationsprotokolle: Obwohl theoretisch möglich, Quantenkommunikation durch klassische zu ersetzen, sind die Protokolle äußerst komplex

Zukünftige Richtungen

  1. Sicherheitsanalyse im Standardmodell
  2. Reduzierung der Anforderungen an Programmausgabe-Entropie
  3. Implementierung und Tests auf echten Quantengeräten
  4. Analyse der Beziehung zur Arbeit GLR+24

Tiefgreifende Bewertung

Stärken

  1. Theoretische Innovation: Erste Präsentation eines universellen Quantenschemas zum Schutz beliebiger randomisierter Algorithmen
  2. Praktisches Design: Quantenressourcenbedarf entkoppelt von Programm-Komplexität, erhöhte Praktikabilität
  3. Strenger Beweis: Prägnanter Sicherheitsbeweis basierend auf Kollaps-Hash-Funktionen
  4. Anwendungsperspektive: Direkt anwendbar auf aktuelle Anforderungen zum Schutz generativer KI

Schwächen

  1. Idealisierte Annahmen: Abhängigkeit vom Black-Box-Modell und Zufallsorakel-Modell
  2. Entropie-Bedingungsbeschränkung: Hohe Minentropie-Anforderung kann praktische Anwendungsreichweite begrenzen
  3. Implementierungskomplexität: Obwohl theoretisch elegant, stehen praktische Implementierungen vor Ingenieursherausforderungen
  4. Sicherheitsdefinition: Autoren geben zu, dass dies nicht die endgültige Definition für Sicherheit mit einmaliger Verwendung ist

Einflussfähigkeit

  1. Akademischer Wert: Bietet neuen theoretischen Rahmen für Programmschutzprobleme in der Quantenkryptographie
  2. Praktisches Potenzial: Bietet mögliche Quantenlösung zum Schutz wertvoller KI-Modelle
  3. Technologischer Fortschritt: Fördert die Entwicklung der nicht-klonbaren Kryptographie
  4. Inspirationswert: Bietet neue Perspektiven für praktische Anwendungen des Quantencomputing in der nahen Zukunft

Anwendungsszenarien

  • KI-Dienstanbieter, die Geistiges Eigentum schützen müssen
  • Software-Lizenzmodelle mit Nutzungsgebühren
  • Algorithmusschutz mit extrem hohen Sicherheitsanforderungen
  • Kandidaten-Anwendungen für Quantenvorteil-Demonstrationen

Literaturverzeichnis

Dieses Paper zitiert wichtige Arbeiten aus Quantenkryptographie, nicht-klonbarer Kryptographie und Quantenberechnungskomplexitätstheorie, insbesondere:

  • Aar09 Aaromsons Pionierarbeit zum Quantenkopierungsschutz
  • BS23 Ben-David und Sattaths Arbeit zu Quantendigitalsignaturen
  • CLLZ21 Konstruktionen zu versteckten Nebenklassen und nicht-klonbarer Kryptographie
  • Zha19 Zhandrys Arbeit zur Komprimierungs-Orakel-Technik

Dieses Paper leistet einen wichtigen Beitrag im Bereich der theoretischen Quantenkryptographie und bietet eine elegante Lösung zur Ausbalancierung des Widerspruchs zwischen Verfügbarkeit und Sicherheit in der Softwareverteilung. Obwohl noch praktische Herausforderungen bestehen, bietet es eine vielversprechende Richtung für die nahe Zukunft der Quantencomputing-Anwendungen in der Kryptographie.