Résumé technique : Cryptanalyse des codes correcteurs d'erreurs pseudo-aléatoires basés sur les LDPC

Énoncé du problème

Les codes correcteurs d'erreurs pseudo-aléatoires (PRC), introduits à CRYPTO 2024, représentent une nouvelle primitive cryptographique conçue pour permettre un tatouage numérique (watermarking) indétectable pour les grands modèles génératifs (LLM) et les modèles d'images génératives (GIM). L'instanciation principale des PRC, connue sous le nom de LDPC-PRC, repose sur les codes de contrôle de parité à faible densité (LDPC) et revendique une sécurité basée sur la dureté des problèmes LPN (Learning Parity with Noise) et des XOR plantés.

Malgré de solides garanties asymptotiques théoriques, la sécurité concrète de LDPC-PRC sous des configurations de paramètres réalistes reste inexplorée. La littérature existante suggère que les PRC pourraient être vulnérables à des attaques de distinction en temps quasi-polynomial, pourtant aucune analyse rigoureuse n'a été menée pour quantifier ces vulnérabilités dans des scénarios de déploiement réels. Cette lacune laisse l'indétectabilité et la robustesse des schémas de tatouage numérique basés sur les PRC non vérifiées face à des adversaires pratiques.

Méthodologie

Ce travail présente la première cryptanalyse concrète de LDPC-PRC, en se concentrant sur deux schémas de tatouage spécifiques : $\Pi_{LLM}$ (pour la génération de texte) et $\Pi_{GIM}$ (pour la génération d'images). Les auteurs proposent trois nouvelles attaques ciblant l'indétectabilité et la robustesse du schéma, en analysant leur complexité sous des configurations de paramètres réalistes dérivées de modèles de pointe (DeepSeek et Stable Diffusion).

1. Nouvelles attaques cryptographiques

Les auteurs conçoivent trois attaques avec des objectifs variés :

• Attaque-I (Récupération partielle de la clé secrète) : Cette attaque cible la propriété d'indétectabilité. En adaptant les algorithmes de décodage de l'ensemble d'information (ISD) en utilisant une approche de type "rencontre dans le milieu" (Meet-in-the-Middle - MITM), l'adversaire récupère un sous-ensemble des vecteurs de lignes de la clé secrète à partir de la clé publique. Les vecteurs récupérés permettent à l'adversaire de distinguer les mots de code encodés par PRC des vecteurs aléatoires avec une probabilité écrasante, brisant ainsi l'indétectabilité.
• Attaque-II (Distinguateur de clé faible) : Cette attaque exploite une vulnérabilité dans la procédure de génération de clés ($KeyGen$). Les auteurs observent que dans les implémentations actuelles, la matrice de clé publique $G$ peut contenir des lignes identiques avec une probabilité non négligeable (une "clé faible"). Un adversaire peut détecter ces non-uniformités statistiques pour distinguer le contenu tatoué d'un bruit aléatoire en temps linéaire, contournant ainsi le besoin d'une récupération de clé complexe.
• Attaque-III (Attaque par superposition de bruit) : Cette attaque cible la propriété de robustesse. En récupérant le vecteur de bruit de Bernoulli original $e$ via le décodage de syndrome, un adversaire construit un vecteur de superposition malveillant $e'$. Ce vecteur est conçu de telle sorte que, lorsqu'il est ajouté au mot de code, le poids total du bruit dépasse le seuil de correction du décodeur, provoquant un échec de décodage (suppression du tatouage). Crucialement, cette attaque exploite l'écart entre les bornes théoriques du bruit et les taux de bruit concrets plus faibles observés dans les implémentations pratiques.

2. Analyse de la complexité concrète

Les auteurs analysent la complexité temporelle et de données de ces attaques en utilisant des ensembles de paramètres spécifiques pour $\Pi_{LLM}$ et $\Pi_{GIM}$. Ils dérivent des bornes théoriques (Théorèmes 1–3) et les valident par rapport à des paramètres concrets, calculant les niveaux de sécurité en bits (ex: $2^{46}$, $2^{60}$) plutôt que de se fier uniquement à la notation asymptotique.

3. Évaluation en conditions réelles

Pour valider les menaces pratiques, les auteurs ont implémenté $\Pi_{LLM}$ et $\Pi_{GIM}$ sur DeepSeek (LLM) et Stable Diffusion (GIM). Ils ont évalué les taux de succès des attaques et l'impact sur la qualité du contenu. Notamment, ils ont constaté que pour $\Pi_{LLM}$, l'obtention de tatouages détectables nécessite une entropie de jetons (tokens) élevée, ce qui dégrade sévèrement la lisibilité du texte, rendant le schéma impraticable pour la génération de texte de haute qualité.

Contributions clés et résultats

1. Rupture de l'indétectabilité

• Attaque-I : A démontré que la récupération partielle de la clé secrète est réalisable. Pour $\Pi_{GIM}$, le niveau de sécurité reste inférieur à 46 bits pour tous les choix de paramètres. Pour $\Pi_{LLM}$, l'attaque réussit avec une probabilité écrasante.
• Attaque-II : A révélé que les clés faibles surviennent avec une probabilité proche de 100 % pour des paramètres spécifiques (ex: $t=3, 4$) dans les schémas LLM et GIM. Cela permet des attaques de distinction en temps polynomial, sapant complètement l'indétectabilité dans ces régimes.

2. Rupture de la robustesse

• Attaque-III : A prouvé que le niveau de sécurité de $\Pi_{LLM}$ ne peut excéder 75 bits pour $n \le 2^{17}$ sous des attaques par superposition de bruit. Pour $\Pi_{GIM}$, le niveau de sécurité concrète est inférieur à 60 bits en raison du faible taux de bruit concret ($\eta \ll \rho$).
• Validation expérimentale : Sur Stable Diffusion, les auteurs ont atteint des taux de succès de suppression du tatouage de 67 % à 96 % selon la borne de perturbation ($\delta$), démontrant que la robustesse est facilement compromise.

3. Limitations pratiques de $\Pi_{LLM}$

L'évaluation sur DeepSeek a révélé un compromis fondamental : pour satisfaire les bornes de correction d'erreurs de LDPC-PRC, le LLM doit générer des jetons à haute entropie (faible confiance). Cela produit un texte qui est soit indétectable (basse entropie), soit illisible (haute entropie). Par conséquent, les auteurs concluent que $\Pi_{LLM}$ est impraticable pour le tatouage numérique de textes de haute qualité.

4. Défenses proposées

Le papier propose trois stratégies d'atténuation :

• Recommandations de paramètres : Augmenter la longueur du code $n$ et le poids de ligne $t$ peut augmenter la complexité de l'attaque. Cependant, atteindre une sécurité de 128 bits nécessite $n > 2^{24}$, ce qui dépasse la longueur de sortie maximale des LLM de pointe actuels ($2^{15}$).
• Révision de la génération de clés : Un algorithme $KeyGen$ modifié (Algorithme 2) utilisant l'élimination gaussienne est proposé pour éliminer la probabilité de générer des clés faibles, atténuant ainsi l'Attaque-II.
• Ajustements d'implémentation : Pour les GIM, il est suggéré d'augmenter le poids du vecteur de bruit ajouté pour combler l'écart entre les taux de bruit théoriques et concrets, augmentant ainsi la complexité de l'Attaque-III.

Signification et affirmations

Le papier affirme fournir la première évaluation de sécurité systématique des PRC, comblant le fossé entre la théorie asymptotique et le déploiement pratique. Les auteurs affirment que :

1. Les garanties de sécurité sont sapées : La sécurité revendiquée de LDPC-PRC est insuffisante dans tous les régimes pratiquement réalisables. Les attaques peuvent détecter les tatouages avec une probabilité écrasante à des coûts nettement inférieurs à 128 bits.
2. Impossibilité pratique pour les LLM : En raison des contraintes inhérentes aux grands modèles génératifs (spécifiquement la longueur de sortie et l'entropie des jetons), l'obtention d'une sécurité de 128 bits pour le tatouage des LLM via LDPC-PRC est actuellement impraticable.
3. Nécessité d'une évaluation rigoureuse : Ce travail souligne que les hypothèses de dureté théoriques (LPN/XOR planté) ne se traduisent pas automatiquement en sécurité concrète lorsque des détails d'implémentation spécifiques (comme les heuristiques de génération de clés et les taux de bruit) sont pris en compte.

Les auteurs concluent que, bien que le tatouage d'images par PRC puisse encore permettre des instanciations pratiques avec une qualité acceptable, l'état actuel des PRC pour les LLM nécessite une réévaluation significative des paramètres et des stratégies d'implémentation avant un déploiement généralisé.