💻 computer science

Improved Pseudorandom Codes from Permuted Puzzles

Cet article introduit une nouvelle construction de codes pseudorandom basés sur la conjecture des codes permutés qui atteint simultanément une sécurité sous-exponentielle, une robustesse contre les éditions du pire cas sur un alphabet binaire, et une résistance face aux adversaires possédant la clé de détection, surmontant ainsi les limitations critiques des schémas de tatouage numérique antérieurs.

Auteurs originaux : Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs

Publié 2026-06-23

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous soyez un auteur célèbre écrivant un roman. Vous voulez prouver qu'un paragraphe spécifique a été écrit par vous et non par un imitateur ou une IA, mais vous ne voulez pas modifier l'histoire ni la rendre étrange. Vous avez besoin d'un moyen de cacher une « signature » secrète à l'intérieur du texte que vous seul pouvez trouver, même si quelqu'un tente de l'éditer, de la supprimer ou de la mélanger.

Ce document traite de la construction d'une version bien meilleure de ce système de signature secrète, appelé un Code Pseudorandom (PRC). Considérez un PRC comme une machine de chiffrement magique qui transforme un message secret en une longue chaîne de charabia. Si vous possédez la clé, vous pouvez transformer le charabia pour retrouver le message, même si celui-ci a été altéré.

Voici la répartition des accomplissements de ce document en utilisant des analogies simples :

1. Le Problème : Les anciennes signatures étaient trop faciles à briser

Auparavant, des chercheurs ont construit ces systèmes de signature, mais ils présentaient trois défauts majeurs :

Le défaut « Quasipolynomial » : Imaginez un verrou qui prendrait environ un million d'années à un ordinateur pour être forcé. C'est bien, n'est-ce pas ? Mais ces anciens verrous pouvaient en réalité être brisés en un temps « quasipolynomial » — imaginez un verrou qui prendrait quelques jours au lieu d'un million d'années. Ce n'était pas assez sécurisé pour le long terme.
Le défaut d'« Alphabet » : Les anciens systèmes fonctionnaient bien si vous pouviez changer l'alphabet entier (comme remplacer chaque « A » par un « Z »). Mais un texte réel (comme l'anglais) possède un alphabet petit et fixe (26 lettres). Les anciens systèmes ne pouvaient pas gérer le fait de simplement changer quelques lettres ou de supprimer un mot sans que la signature ne se brise.
Le défaut de la « Clé » : Si un pirate connaissait votre clé secrète, il pouvait facilement trouver de minuscules changements pour supprimer votre signature. Les anciens systèmes partaient du principe que le pirate était les yeux bandés ; ils ne fonctionnaient pas si le pirate portait des lunettes.

2. La Solution : Le « Puzzle Permuté »

Les auteurs ont créé un nouveau système basé sur un concept qu'ils appellent la « Conjecture des Codes Permutés ».

Imaginez que vous avez une mosaïque magnifique et complexe (le code).

Mélanger les tuiles : Vous prenez la mosaïque et mélangez aléatoirement la position des tuiles (Permutation d'Index).
Peindre les tuiles : Vous prenez un pinceau et repeignez aléatoirement la couleur de chaque tuile (Permutation d'Alphabet).
Saupoudrer de la poussière : Vous saupoudrez un peu de poussière aléatoire sur l'ensemble (Bruit).

Les auteurs affirment que si vous effectuez ces trois étapes, le résultat ressemble exactement à un tas de poussière aléatoire et sans signification. Pour quiconque ne possède pas la clé, il est impossible de faire la différence entre la « mosaïque mélangée » et la « poussière aléatoire ». Cela rend la signature indétectable (elle ne dégrade pas la qualité du texte).

3. Les Trois Grandes Victoires

Le document prétend résoudre simultanément tous les problèmes mentionnés ci-dessus :

Une Sécurité Super Forte : Ils affirment que leur nouveau verrou est si robuste que même un superordinateur tournant pendant une très longue période (temps sous-exponentiel) ne pourrait pas distinguer leur mosaïque mélangée de la poussière aléatoire.
Robuste aux Éditions (Le problème de l'« Édition ») : C'est la plus grande percée. Leur système peut survivre aux éditions. Si un pirate supprime un mot, ajoute une faute de frappe ou déplace une phrase, le système peut toujours trouver la signature.
- Analogie : Imaginez un message écrit sur une longue bande de papier. Si quelqu'un découpe quelques mots, en colle de nouveaux ou mélange l'ordre, l'ancien système échouerait. Le nouveau système est comme un puzzle qui peut encore être résolu même si les pièces sont légèrement endommagées ou déplacées.
Robuste face au Hacker « Connaissant la Clé » : Leur système fonctionne même si le hacker connaît la clé secrète.
- Analogie : Habituellement, si un voleur connaît la combinaison de votre coffre-fort, il peut l'ouvrir et en retirer le contenu. Les auteurs ont construit un coffre-fort où, même si le voleur connaît la combinaison, il ne peut pas retirer l'objet caché sans détruire le coffre lui-même. Cela permet à n'importe qui de vérifier le filigrane, pas seulement à une partie de confiance, sans pour autant briser le système.

4. Comment ils ont fait (L'astuce du « Pliage »)

Pour que cela fonctionne pour du texte réel (qui possède une faible « entropie » ou un faible caractère aléatoire par mot), ils ont utilisé un type spécial de code mathématique appelé codes Reed-Solomon repliés (Folded Reed-Solomon codes).

Analogie : Imaginez que vous essayez d'envoyer un message secret, mais que vous ne pouvez envoyer que de courts éclats de données saccadés. L'ancienne méthode consistait à envoyer une lettre à la fois. La nouvelle méthode consiste à « plier » le message. Au lieu d'envoyer « A, B, C », vous envoyez un seul bloc qui représente « A, B et C » en même temps. Cela permet au système de compacter plus d'informations dans le texte sans avoir besoin que le texte soit hautement aléatoire ou chaotique.

5. Le « Piège » (L'Hypothèse)

Les auteurs admettent faire une hypothèse majeure. Ils parient que le « Puzzle Permuté » (la mosaïque mélangée) est véritablement impossible à distinguer de la poussière aléatoire.

Ils n'ont pas prouvé que cela est mathématiquement impossible à briser (personne n'a encore prouvé cela pour ce type spécifique de puzzle).
Cependant, ils ont montré que :
1. C'est impliqué par une autre hypothèse célèbre et très étudiée en cryptographie (les Puzzles Permutés).
2. Ils ont tenté de briser le système avec de nombreux types d'attaques différentes (comme essayer de trouver des motifs dans la poussière) et ont échoué.
3. Ils ont prouvé que si vous omettez n'importe laquelle des trois étapes (mélange, peinture ou saupoudrage), le système devient facile à briser. Cela suggère que les trois étapes sont nécessaires et que le système est robuste.

Résumé

Ce document présente une nouvelle façon super sécurisée de tatouer numériquement (watermarking) le texte généré par IA. Il prétend être le premier système qui :

Est presque impossible à détecter (il ressemble à du texte normal).
Survit à des éditions lourdes (fautes de frappe, suppressions, réécritures).
Fonctionne même si l'attaquant connaît la clé secrète.

Ils y parviennent en transformant le texte en un « puzzle mélangé » qui repose sur une nouvelle hypothèse mathématique, qu'ils soutiennent être très probablement vraie sur la base de tests approfondis et de connexions avec d'autres théories mathématiques établies.

Résumé Technique : Codes Pseudorandoms Améliorés à partir de Puzzles Permutés

Énoncé du Problème

La prolifération du contenu généré par l'IA nécessite des schémas de tatouage numérique (watermarking) robustes pour identifier la provenance. Des travaux récents ont établi que les Codes Pseudorandoms (PRC) sont équivalents à des schémas de tatouage numérique dotés de fortes garanties de robustesse et de qualité. Un PRC est un schéma de chiffrement à clé secrète dont les texte chiffrés sont calculablement indiscernables d'une distribution uniforme (garantissant l'indétectabilité/la qualité) et dont l'algorithme de déchiffrement tolère un taux élevé d'erreurs (garantissant la robustesse).

Cependant, les constructions existantes de PRC souffrent de trois limitations critiques :

Sécurité Faible : Toutes les constructions antérieures sont vulnérables à des attaques de distinction en temps quasi-polynomial. Elles reposent sur la dissimulation de structures $(\log n)$ -parciles, ce qui permet des attaques par recherche par force brute.
Robustesse d'Alphabet Limitée : Bien que certaines constructions gèrent les erreurs d'édition, elles nécessitent un alphabet de taille polynomiale. Le texte réaliste (ex: issu de modèles de langage de grande taille) possède une faible entropie (environ 1 bit par mot), ce qui nécessite un PRC robuste aux éditions sur un alphabet de taille constante (idéalement binaire).
Modèles Adversaires Faibles : Les travaux précédents supposent que les adversaires sont bornés par le calcul ou ne possèdent pas la clé de détection. Il n'était pas clair si les PRC pouvaient rester robustes face à des adversaires à puissance de calcul illimitée possédant la clé de détection (robustesse fortement-adaptative).

La question centrale était de savoir si une construction unique pouvait simultanément atteindre une sécurité sous-exponentielle, une robustesse d'édition sur un alphabet binaire, et une robustesse contre les adversaires détenant la clé.

Méthodologie

1. La Conjecture des Codes Permutés

Les auteurs introduisent une nouvelle hypothèse de dureté computationnelle, la Conjecture des Codes Permutés. Cette conjecture pose qu'une distribution de mots de code "brouillés" et bruités est calculablement indiscernable d'une distribution uniforme.

La distribution $D_{n,\Sigma,C,\eta,T}$ est générée comme suit :

Échantillonner une permutation d'indice aléatoire $\sigma \in S_n$ et des permutations d'alphabet $\pi_1, \dots, \pi_n \in S_\Sigma$ .
Échantillonner $T$ mots de code $c_1, \dots, c_T$ uniformément à partir d'un code linéaire $C \subseteq \Sigma^n$ .
Pour chaque mot de code, permuter les indices via $\sigma$ et les symboles à chaque position via $\pi_j$ , produisant $\hat{c}$ .
Appliquer un canal de substitution avec un taux de bruit $\eta$ à $\hat{c}$ .

Idée Clé : Les auteurs prouvent que cette conjecture est impliquée par la Conjecture des Puzzles Permutés (utilisée précédemment pour la Récupération d'Information Privée doublement efficace). Ils fournissent des preuves statistiques que, pour des alphabets de taille constante et des codes à haute distance duale, un nombre logarithmique d'échantillons est statistiquement uniforme. De plus, ils démontrent que les trois composantes (permutation d'indice, permutation d'alphabet et bruit) sont nécessaires ; omettre la permutation d'alphabet (comme dans une version "jouet") rend les codes de Reed-Solomon distinguables via des attaques par polynômes de bas degré.

2. Construction de PRC Robustes aux Éditions

Pour atteindre la robustesse aux éditions sur un alphabet binaire, les auteurs construisent un PRC basé sur des codes de Reed-Solomon Repliés (Folded Reed-Solomon - FRS).

Encodage : La clé secrète consiste en les permutations et un masque jetable (one-time pad). Pour encoder, un mot de code aléatoire du code sous-jacent est permuté, bruité, puis un sous-ensemble de symboles est sélectionné. Crucialement, chaque symbole sélectionné est produit sous la forme d'une chaîne binaire contenant à la fois la valeur du symbole et son indice.
Décodage : Le décodeur reçoit une chaîne potentiellement corrompue par des éditions (insertions/suppressions). Il scanne toutes les sous-chaînes d'une longueur spécifique, tentant de "brutaliser" la distance d'édition pour récupérer des paires potentielles $(indice, symbole)$. Ces candidats forment une liste pour chaque position. Un algorithme de récupération de liste (list-recovery) pour le code sous-jacent est ensuite appliqué à ces listes pour récupérer le mot de code original.
Mécanisme de Robustesse : En incluant les indices dans la sortie, le décodeur peut récupérer le symbole correct même si la position a été décalée par des insertions ou des suppressions, à condition que le nombre d'éditions soit borné. L'utilisation des codes FRS permet au système de tolérer une fraction constante d'éditions même lorsque l'alphabet est effectivement binaire (via la transformation).

3. Transformation de Tatouage Numérique (Watermarking)

En utilisant le cadre établi par Christ et Gunn (CRYPTO '24), les auteurs transforment leur PRC en un schéma de tatouage numérique pour les modèles de langage autorégressifs. Le schéma génère du texte tatoué en biaisant la sélection de tokens vers les bits du mot de code du PRC. La robustesse du PRC face aux éditions se traduit directement par la capacité du tatouage à survivre aux modifications adverses du texte, à condition que le modèle possède une entropie par token suffisante.

Contributions Clés et Résultats

1. Nouvelle Construction de PRC avec Trois Propriétés

Le papier présente la première construction de PRC satisfaisant simultanément :

Sécurité Sous-Exponentielle Plausible : Basée sur la Conjecture des Codes Permutés, qui évite les structures creuses vulnérables aux attaques en temps quasi-polynomial.
Robustesse aux Éditions sur Alphabet Binaire : La construction tolère un taux constant d'éditions (insertions, suppressions, substitutions) sur un alphabet binaire.
Robustesse Fortement-Adaptative : Le schéma reste robuste même contre des adversaires qui connaissent la clé de détection et sont à puissance de calcul illimitée.

2. Garanties Théoriques

Théorème 5.6 : Sous la Conjecture des Codes Permutés, il existe un PRC à alphabet binaire qui est fortement-adaptatif à un taux constant d'éditions avec une sécurité sous-exponentielle.
Théorème 5.14 : Sous une variante de la conjecture pour les codes de Reed-Solomon Repliés, il existe un tatouage numérique de LLM indétectable qui est robuste à un taux constant d'éditions ( $\tilde{O}(\alpha^7)$ ) ne nécessitant qu'un taux d'entropie par token constant $\alpha$ . C'est le premier tatouage de ce type qui est à la fois indétectable et robuste aux éditions de pire cas sous des contraintes d'entropie réalistes.

3. Cryptanalyse et Preuves

Nécessité de la Permutation d'Alphabet : Les auteurs prouvent que sans les permutations d'alphabet, les codes de Reed-Solomon sont efficacement distinguables du hasard, même avec les permutations d'indice et le bruit.
Attaques Quasi-Polynomiales sur les Travaux Antérieurs : Ils montrent qu'une large classe de constructions de PRC précédentes (celles reposant sur des structures creuses plantées ou des prédicats tolérants au bruit) sont intrinsèquement vulnérables aux attaques en temps quasi-polynomial.
Uniformité Statistique : Ils prouvent que pour des alphabets de taille constante, un petit nombre de mots de code permutés sont statistiquement indiscernables d'une distribution uniforme, fournissant une preuve de la validité de la conjecture face à des distingueurs simples.

Signification

Le papier prétend résoudre la tension entre les trois propriétés désirables des PRC qui étaient auparavant considérées comme mutuellement exclusives ou inaccessibles. En formalisant la Conjecture des Codes Permutés et en exploitant les codes de Reed-Solomon Repliés, les auteurs fournissent une fondation théorique pour des schémas de tatouage numérique qui sont :

Indétectables : Indiscernables de la sortie réelle du modèle de langage.
Robustes : Capables de résister aux éditions adverses (insertions/suppressions) du texte.
Sécurisés : Résilients face aux attaquants possédant la clé de détection, permettant une vérification publique sans compromettre la robustesse.

Le travail établit que l'atteinte de ces propriétés nécessite de dépasser les structures creuses et d'embrasser la difficulté de distinguer des mots de code permutés et bruités du hasard. Bien que la sécurité repose sur une nouvelle conjecture, les auteurs fournissent des preuves solides de sa validité et démontrent qu'elle implique l'existence de tatouages numériques pratiques et robustes pour le texte généré par IA.