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

Protection Quantique Unique de tout Algorithme Aléatoire

Informations Fondamentales

  • ID de l'article: 2411.03305
  • Titre: Quantum One-Time Protection of any Randomized Algorithm
  • Auteurs: Sam Gunn, Ramis Movassagh (Google Quantum AI)
  • Classification: quant-ph cs.CR
  • Date de publication: 3 janvier 2025 (arXiv v2)
  • Lien de l'article: https://arxiv.org/abs/2411.03305v2

Résumé

Le développement rapide des modèles d'apprentissage automatique et la dépendance envers les données d'entraînement précieuses ont ravivé la contradiction fondamentale entre la commodité d'exécuter des programmes localement et le risque d'exposer les détails du programme aux utilisateurs. Simultanément, les propriétés fondamentales des états quantiques offrent de nouvelles solutions pour la sécurité des données et des programmes, nécessitant des ressources quantiques minimales et offrant des avantages au-delà du temps d'exécution classique. Ce travail démontre une telle solution par le biais de jetons quantiques uniques.

Les jetons quantiques uniques sont des états quantiques permettant l'évaluation d'un programme spécifique exactement une fois. La sécurité unique garantit que le jeton ne peut pas être utilisé pour évaluer le programme plusieurs fois. Les auteurs proposent un schéma de construction de jetons quantiques uniques pour tout programme classique aléatoire arbitraire (y compris les modèles d'IA générative) et prouvent que le schéma satisfait une définition de sécurité unique intéressante dans le modèle boîte noire, à condition que la sortie de l'algorithme classique possède une entropie minimale suffisamment élevée.

Contexte et Motivation de la Recherche

Définition du Problème

La commercialisation des logiciels fait face à un dilemme fondamental : comment distribuer les logiciels sans abandonner la propriété ? Les solutions traditionnelles présentent un compromis inhérent entre disponibilité et exclusivité :

  1. Schémas d'obfuscation de programme : distribuer une version obfusquée du logiciel, mais avec des risques de piratage et permettant aux utilisateurs d'exécuter indéfiniment
  2. Schémas de requête serveur : maintenir le logiciel sur un serveur répondant aux requêtes des utilisateurs, mais réduisant la disponibilité et nécessitant une communication continue

Importance du Problème

À l'ère de l'IA générative, ce problème devient plus critique car :

  • Les logiciels peuvent être extrêmement précieux
  • Ils peuvent divulguer des informations privées
  • Les modèles de paiement par requête deviennent de plus en plus courants

Limitations des Approches Existantes

L'information classique peut toujours être copiée ; une fois le logiciel distribué, les utilisateurs peuvent l'interroger ou le copier un nombre arbitraire de fois. Cette limitation empêche les approches traditionnelles de réaliser simultanément une haute disponibilité et une forte exclusivité.

Avantages de la Solution Quantique

L'impossibilité de cloner l'information quantique offre la possibilité d'améliorer les solutions existantes :

  • Protection quantique contre la copie : améliorer l'approche (1), empêchant la copie du programme tout en permettant une exécution illimitée
  • Programmes quantiques uniques : améliorer l'approche (2), éliminant la communication en ligne dans les modèles de paiement par requête

Contributions Principales

  1. Premier schéma universel de tokenisation quantique de programme : propose le premier schéma universel utilisant l'information quantique pour protéger tout algorithme aléatoire arbitraire, sans restriction à des fonctionnalités cryptographiques spécifiques
  2. Exigences de ressources quantiques indépendantes de la complexité du programme : la taille et la complexité du jeton quantique sont complètement indépendantes du programme protégé
  3. Preuve théorique de sécurité : prouve que le schéma satisfait la définition de sécurité unique dans le modèle boîte noire
  4. Considérations pratiques : le schéma est suffisamment simple pour être implémentable à l'ère NISQ ou du calcul quantique tolérant aux pannes précoce

Détails de la Méthode

Définition de la Tâche

Construire des jetons quantiques uniques pour protéger tout algorithme aléatoire f : X × R → Y, tel que :

  • Le jeton permet l'évaluation du programme exactement une fois
  • Fournit une garantie de sécurité unique
  • Ne nécessite pas une implémentation cohérente du programme sur un ordinateur quantique

Construction Principale (Construction 2)

Primitives Cryptographiques

Le schéma dépend de trois primitives cryptographiques :

  1. (AuthKeyGen, AuthTokenGen, Sign, Verify) : schéma d'authentification quantique unique
  2. Obf : obfuscateur de programme classique
  3. H : fonction de hachage (modélisée comme un oracle aléatoire)

Structure du Jeton

Le jeton de programme contient deux parties :

  • |ψ⟩ : état quantique non-clonable indépendant de f
  • Obf(P) : circuit classique obfusqué P dépendant de f

Flux d'Algorithme

KeyGen(1^λ, f) :

  1. Échantillonner sk ← AuthKeyGen(1^λ)
  2. Définir le circuit classique P : X × {0,1}^m → Y ∪ {⊥}
    • Calculer Verify(sk, (x,z)), sortir ⊥ si rejeté
    • Sinon sortir f(x; H(x,z))
  3. Calculer l'obfuscation P̂ = Obf(P)
  4. Sortir (sk, P̂)

TokenGen(sk) :

  1. Calculer le jeton d'authentification unique |tk⟩ ← AuthTokenGen(sk)
  2. Sortir |tk⟩

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

  1. Calculer z ← Sign(x, |tk⟩)
  2. Calculer et sortir P̂(x,z)

Schéma d'Authentification Quantique Unique

Définition (Définition 1)

Un schéma d'authentification quantique unique doit satisfaire :

  • Correction : les signatures légitimes passent la vérification
  • Non-falsifiabilité unique : aucun adversaire en temps polynomial ne peut générer deux paires de signatures valides différentes

Construction Concrète (Construction 1)

Basée sur l'authentification à un bit d'états de sous-espace caché :

AuthKeyGen(1^λ) : échantillonner un sous-espace aléatoire A ⊆ F₂^λ, de dimension λ/2

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

Sign(x, |A⟩) :

  • Si x = 0 : mesurer dans la base standard et sortir le résultat
  • Si x = 1 : mesurer dans la base Hadamard et sortir le résultat

Verify(A, (x,z)) : vérifier si z est dans le sous-espace correspondant

Points d'Innovation Technique

  1. Ressources quantiques indépendantes du programme : l'état quantique |ψ⟩ ne dépend pas du programme protégé, permettant de protéger des programmes complexes avec de petits appareils quantiques
  2. Mécanisme de liaison d'aléatoire : H(x,z) détermine l'aléatoire, "mélangeant" efficacement l'entrée, l'authentification et la sortie
  3. Propriété de fonction de hachage effondrée : exploite la propriété quantique que la mesure de la sortie provoque l'effondrement de l'entrée et de l'étiquette d'authentification

Analyse Théorique

Définitions de Sécurité

Jeu de Programme Unique Boîte Noire G^BB-OTP

  1. L'adversaire obtient |ψ⟩ et un accès oracle quantique à P̂
  2. L'adversaire soumet une requête quantique, le challenger calcule P̂ et mesure le résultat y
  3. Si y = ⊥ le jeu s'arrête, l'adversaire échoue
  4. L'adversaire soumet une deuxième requête, le challenger mesure y'
  5. Si y' ∉ {y, ⊥} l'adversaire gagne

Théorème Principal

Théorème 2 : Si pour chaque x ∈ X, f(x;r) possède une entropie minimale d'au moins poly(λ) sur r aléatoire, et le schéma d'authentification quantique unique est sûr, alors la Construction 2 est sûre pour f en tant que programme unique boîte noire.

Cœur de la Preuve : Fonction de Hachage Effondrée

Lemme 1 : Soit f : {0,1}^m × {0,1}^n → Y. Si pour tout x, f(x;r) possède une entropie minimale d'au moins τ sur r aléatoire, alors lorsque H est un oracle aléatoire, la fonction g^H : x ↦ f(x;H(x)) est effondrée, avec un avantage de O(q³·2^(-τ)).

Esquisse de Preuve

Utilisant la technique d'oracle compressé :

  1. Prouver que Invert_f et CPhsO sont presque échangeables
  2. Utiliser la condition d'entropie minimale pour limiter la probabilité de collision
  3. Réaliser l'effondrement d'entrée par mesure de sortie

Expériences et Applications

Exigences de Ressources Quantiques

  • En utilisant le schéma de signature unique de CLLZ21, l'utilisateur a seulement besoin de :
    • Stocker un état quantique de taille constante
    • Effectuer des mesures dans la base standard et la base Hadamard

Considérations Pratiques

  1. Faisabilité à court terme : les exigences de capacité quantique sont indépendantes de la complexité du programme
  2. Sécurité extensible : les ressources quantiques supplémentaires ne servent qu'à augmenter la sécurité
  3. Remplacement de communication classique : peut remplacer la communication quantique par des protocoles de préparation d'état à distance

Scénarios d'Application

  • Protection des modèles d'IA générative
  • Services logiciels payants par requête
  • Programmes sensibles nécessitant une exécution hors ligne

Travaux Connexes

Développement Historique

  • GKR08 : étude initiale des programmes uniques (sans calcul quantique)
  • BGS13 : propose le concept de programmes quantiques uniques, prouve l'impossibilité pour les programmes déterministes
  • BS23 : protège les fonctions de signature dans le modèle standard
  • GLR+24 : travail parallèle indépendant, fournissant des définitions de sécurité plus fortes

Comparaison des Contributions

  • Premier schéma universel protégeant tout algorithme aléatoire arbitraire
  • Preuve de sécurité simple et autonome
  • Considérations de conception orientées vers la praticité

Conclusion et Discussion

Conclusions Principales

  1. Les jetons quantiques uniques peuvent protéger tout programme classique aléatoire arbitraire
  2. La sécurité dépend de l'entropie minimale élevée de la sortie du programme
  3. Les exigences de ressources quantiques sont indépendantes de la complexité du programme
  4. Le schéma est réalisable à l'ère NISQ

Limitations

  1. Exigence d'entropie élevée : la sortie du programme doit posséder une entropie minimale suffisamment élevée
  2. Modèle boîte noire : la preuve de sécurité est dans le modèle boîte noire idéalisé
  3. Restriction aux programmes déterministes : ne s'applique pas aux programmes déterministes (limité par le résultat d'impossibilité de BGS13)
  4. Protocoles de communication classique complexes : bien que théoriquement possible de remplacer la communication quantique par une communication classique, les protocoles sont extrêmement complexes

Directions Futures

  1. Analyse de sécurité dans le modèle standard
  2. Réduction des exigences d'entropie de sortie du programme
  3. Implémentation et test sur des appareils quantiques réels
  4. Analyse de la relation avec le travail GLR+24

Évaluation Approfondie

Avantages

  1. Innovation théorique : première proposition d'un schéma quantique universel protégeant tout algorithme aléatoire arbitraire
  2. Conception pratique : les exigences de ressources quantiques sont découplées de la complexité du programme, améliorant la praticité
  3. Preuve rigoureuse : fournit une preuve de sécurité simple basée sur les fonctions de hachage effondrées
  4. Perspectives d'application : directement applicable aux besoins actuels de protection de l'IA générative

Insuffisances

  1. Hypothèses idéalisées : dépend du modèle boîte noire et du modèle oracle aléatoire
  2. Limitation de la condition d'entropie : l'exigence d'entropie minimale élevée peut limiter la portée des applications pratiques
  3. Complexité d'implémentation : bien que théoriquement élégant, l'implémentation pratique fait face à des défis d'ingénierie
  4. Définition de sécurité : les auteurs reconnaissent que ce n'est pas la définition finale de sécurité unique

Impact

  1. Valeur académique : fournit un nouveau cadre théorique pour le problème de protection de programme en cryptographie quantique
  2. Potentiel pratique : fournit une solution quantique possible pour protéger les modèles d'IA précieux
  3. Avancement technologique : fait progresser le développement de la cryptographie non-clonable
  4. Signification inspirante : fournit de nouvelles perspectives pour les applications pratiques à court terme du calcul quantique

Scénarios d'Application

  • Fournisseurs de services d'IA ayant besoin de protéger la propriété intellectuelle
  • Modèles de licence logicielle payants à l'utilisation
  • Protection d'algorithmes sensibles avec des exigences de sécurité extrêmement élevées
  • Candidats d'application pour la démonstration d'avantage quantique

Références

Cet article cite des travaux importants en cryptographie quantique, cryptographie non-clonable et théorie de la complexité du calcul quantique, notamment :

  • Aar09 Travail fondateur d'Aaronson sur la protection quantique contre la copie
  • BS23 Travail de Ben-David et Sattath sur les signatures numériques quantiques
  • CLLZ21 Constructions concernant les cosets cachés et la cryptographie non-clonable
  • Zha19 Travail de Zhandry sur la technique d'oracle compressé

Cet article apporte une contribution importante au domaine de la cryptographie quantique théorique, fournissant une solution élégante pour équilibrer la contradiction entre disponibilité et sécurité dans la distribution de logiciels. Bien que des défis de mise en pratique subsistent, il fournit une direction prometteuse pour la réalisation à court terme du calcul quantique dans les applications cryptographiques.