Résumé Technique : Copie-Protection avec Défis Corrélés

1. Énoncé du Problème

La copie-protection quantique vise à encoder une fonctionnalité dans un état quantique réutilisable de telle sorte qu'il ne peut être divisé en deux états distincts (détenus par des adversaires « profiteurs ») qui restent simultanément utiles. Bien que des progrès significatifs aient été réalisés dans la construction de schémas de copie-protection pour des fonctionnalités générales et des clés de déchiffrement, le domaine fait face à deux limitations critiques :

1. Fragmentation Définitionnelle : Pour les primitives fondamentales comme le Chiffrement à Déchiffreur Unique (SDE - Single-Decryptor Encryption), il existe sept notions de sécurité distinctes dans la littérature. Les relations entre ces notions sont obscures, et aucune définition unique de « référence » (gold standard) n'est connue pour impliquer toutes les autres. Crucialement, on ignore si la sécurité d'indistinguabilité standard implique la sécurité de recherche (search security) pour le SDE.
2. L'Écart des Défis Identiques : Les constructions existantes parviennent principalement à assurer la sécurité contre des défis échantillonnés indépendamment. Cependant, une notion de sécurité plus naturelle et pratiquement pertinente est la sécurité à défis identiques, où deux adversaires reçoivent exactement le même défi (par exemple, le même ciphertext ou le même point d'entrée). Cette notion est liée aux bits non clonables et à la copie-protection de fonctions ponctuelles. Bien qu'il s'agisse d'une question ouverte depuis Georgiou et Zhandry (2020), aucune construction prouvable de SDE à défis identiques ou de copie-protection générale n'existe dans le modèle pur sous des hypothèses standards.

Le problème central abordé est de savoir si l'on peut définir une notion de sécurité unifiée et forte qui capture ces cas d'utilisation naturels (y compris les défis identiques) et parvenir à des constructions satisfaisant cette notion dans le modèle pur.

2. Méthodologie et Cœur Technique

Les auteurs résolvent ces problèmes grâce à une combinaison d'unification définitionnelle et d'un nouvel outil d'information quantique.

A. Unification Définitionnelle

Le papier introduit la Sécurité à Défis Corrélés pour le SDE et l'Obfuscation Poncturableable Non-Clonable (UPO - Unclonable Puncturable Obfuscation).

• SDE à Défis Corrélés (SDE-CORR) : Cette définition permet aux bits de défi pour les deux adversaires d'être arbitrairement corrélés, à condition que leurs distributions marginales restent uniformes. Elle englobe à la fois les contextes de défis indépendants et de défis identiques.
• UPO à Défis Corrélés : De même, cette définition permet aux points de défi et aux informations auxiliaires d'être arbitrairement corrélés. Elle généralise les définitions précédentes de l'UPO pour inclure la fuite d'informations auxiliaires, ce qui est crucial pour des applications comme les programmes de type « calculer-et-comparer » (compute-and-compare).

Les auteurs établissent une hiérarchie de définitions, prouvant que le SDE-CORR implique les sept notions de sécurité antérieures du SDE, y compris la tant recherchée sécurité à défis identiques. Ils clarifient également que la sécurité d'indistinguabilité standard (CPA) n'implique pas la sécurité de recherche en général, et que la sécurité à défis indépendants n'implique pas la sécurité à défis identiques.

B. Le Théorème de Monogamie de Coset Décisionnel

Le cœur technique du papier est un nouveau Théorème de Monogamie de l'Intrication (MOE) de Coset Décisionnel.

• La Configuration : Un adversaire reçoit un état de coset $|A_{s,t}\rangle$ (une superposition sur un sous-espace décalé $A+s$ avec des déphasages déterminés par $t$). L'adversaire divise cet état entre deux parties non communicantes, B et C.
• Le Défi : Le challengeur échantillonne un vecteur non nul $u \in A$ et un vecteur non nul $v \in A^\perp$, et envoie le même couple $(u, v)$ à la fois à B et C.
• L'Objectif : B et C doivent produire un bit unique $e = \langle u, t \rangle \oplus \langle v, s \rangle$.
• Le Résultat : Les auteurs prouvent que la probabilité que B et C produisent tous deux le bit correct est au plus $1/2 + 2^{-\Omega(n)}$.

Innovations Clés de la Preuve :

1. Décisionnel vs Recherche : Contrairement aux précédents théorèmes MOE (par exemple, Culf et Vidick) qui sont de type « recherche » (nécessitant la production de vecteurs complets), celui-ci est un jeu « décisionnel » où les parties produisent un seul bit.
2. Défis Identiques : Le défi $(u, v)$ est identique pour les deux parties. Les précédents résultats MOE décisionnels reposaient sur des états apprenables (comme BB84) ou des défis indépendants. Il s'agit du premier théorème MOE décisionnel pour des états identiques appliqué à une famille d'états non apprenables (états de coset).
3. Absence d'Extraction : La preuve évite les techniques complexes d'« extraction » (mesures de seuil, rewinding) requises dans les travaux précédents pour convertir les garanties de recherche en garanties décisionnelles. Au lieu de cela, elle utilise un argument d'information-théorique montrant que, conditionnellement à la clé et au message, le ciphertext est un état uniformément mixte sur un espace propre spécifique, en exploitant la structure des opérateurs de Pauli.
4. Variante Computationnelle : Les auteurs étendent cela au cadre computationnel en utilisant l'Obfuscation par Indistinguabilité (iO) et l'Obfuscation de Masquage de Sous-espace (Subspace-Hiding Obfuscation), en gérant les informations auxiliaires corrélées.

C. Stratégie de Construction

En utilisant le nouveau théorème MOE de Coset Décisionnel, les auteurs construisent :

1. SDE à Défis Corrélés : Ils adaptent la construction de Kitagawa-Yamakawa (2025). En réécrivant les bits de défi à l'aide d'un bit identique caché et d'un paramètre de corrélation, ils réduisent directement la sécurité du schéma SDE au jeu MOE de Coset Décisionnel.
2. UPO à Défis Corrélés : Ils construisent un schéma UPO pour des circuits clés de taille polynomiale arbitraire. La preuve de sécurité implique une séquence d'hybrides où les points de défi sont ponctués, et les valeurs sont remplacées par des fonctions injectives/perdues (lossy) et du hachage universel pour simuler l'information auxiliaire pré-divisée. L'hybride final réduit au jeu MOE de Coset Décisionnel computationnel.

3. Résultats Clés

Le papier fournit les résultats concrets suivants dans le modèle pur :

• Sécurité SDE : En supposant l'Obfuscation par Indistinguabilité (iO) post-quantique et les Fonctions à Sens Unique (OWF), il existe un schéma SDE satisfaisant le SDE-CORR. C'est la première construction de SDE à ciphertext classique satisfaisant la sécurité à défis identiques à partir d'hypothèses standards.
• Sécurité UPO : En supposant l'iO post-quantique et la dureté quantique de l'apprentissage avec erreurs (LWE), il existe un schéma UPO Corréler pour des circuits de taille polynomiale arbitraire. Ce schéma satisfait la sécurité contre des distributions de défis arbitrairement corrélées avec une haute entropie minimale.
  • Note : Pour le cas spécifique de distributions de défis uniformes identiques, l'hypothèse LWE peut être remplacée par une OWF post-quantique.
• Applications de Copie-Protection : À travers le cadre UPO, les auteurs dérivent les premières constructions de copie-protection en modèle pur pour :
  • Fonctions Ponctuelles : Avec des distributions de défis identiques naturelles (résolvant la question ouverte d'Aaronson de 2009).
  • Fonctions à $k$-Points : Généralisations des fonctions ponctuelles.
  • Programmes de Calcul-et-Comparaison : Avec des distributions de défis identiques naturelles.
  • Fonctionnalités Ponctualisables Générales : Avec une sécurité de type imprévisibilité et de type pseudo-aléatorité, incluant la sécurité oraculaire (où les adversaires ont un accès oracle à la fonction) pour les défis identiques.

4. Signification et Revendications

Le papier affirme résoudre plusieurs problèmes de longue date en cryptographie quantique :

1. Résolution de la Question Ouverte des Défis Identiques : Il fournit la première copie-protection prouvable pour les fonctions ponctuelles et les clés de déchiffrement sous la notion de sécurité à défis identiques dans le modèle pur, un problème qui reste ouvert depuis plus d'une décennie.
2. Clarté Définitionnelle : Il établit une définition de « référence » (SDE-CORR) qui englobe toutes les définitions antérieures, clarifiant la hiérarchie des notions de sécurité et prouvant que les définitions précédentes étaient insuffisantes pour capturer les intuitions de sécurité naturelles (par exemple, que le CPA n'implique pas la recherche).
3. Avancement Technique : Le nouveau Théorème de Monogamie de Coset Décisionnel est présenté comme un résultat d'intérêt indépendant. Il unifie l'étude des jeux de monogamie, de l'encryption non-clonable et de la copie-protection en fournissant une garantie décisionnelle pour des états non apprenables avec des défis identiques, simplifiant les preuves futures en supprimant le besoin de techniques d'extraction complexes.
4. Cadre Modulaire : En introduisant l'UPO Corréler, le papier fournit une voie modulaire pour atteindre la copie-protection pour un large éventail de fonctionnalités (au-delà des simples fonctions ponctuelles) sous des définitions de sécurité naturelles, y compris celles nécessitant une fuite d'informations auxiliaires.

Les auteurs soulignent que leurs résultats reposent sur des hypothèses post-quantiques standards (iO, OWF, LWE) et opèrent dans le modèle pur, sans dépendre de modèles idéalisés comme le Modèle de l'Oracle Aléatoire Quantique (QROM) pour ces résultats spécifiques.