Résumé Technique : RankGuard-Polar

Énoncé du Problème

L'article aborde le défi consistant à publier en toute sécurité un sous-ensemble de coordonnées de mots de code polaires sur des ressources publiques partagées (par exemple, liens de diffusion, stockage cloud) tout en maintenant la confidentialité informationnelle du message secret. Contrairement aux scénarios classiques de fil d'écoute où un espion observe la sortie d'un canal bruité, ce travail suppose un « espion fort » ayant un accès direct à l'entrée du canal de la ressource publique. La question opérationnelle centrale est : Quelle quantité d'informations sur le message confidentiel est divulguée lorsque des coordonnées spécifiques du mot de code sont intentionnellement exposées sur un canal public ?

Les auteurs se concentrent sur les codes polaires de longueur finie sur les corps binaires ($\mathbb{F}_2$), spécifiquement dans un cadre où un émetteur partage le temps entre des canaux privés et publics. L'objectif est de déterminer quels indices peuvent être publiés sans révéler de combinaisons linéaires indépendantes des bits d'information, en exploitant la structure inhérente des codes polaires où les « bits gelés » peuvent servir de nouvelle clé secrète aléatoire (masques) connue uniquement du récepteur légitime.

Méthodologie

Le cadre proposé, RankGuard-Polar, repose sur une caractérisation algébrique exacte de la fuite d'informations dérivée des propriétés de rang des sous-matrices de la matrice génératrice polaire.

1. Modèle du Système

• Encodeur : L'encodeur génère un mot de code $x = uG_N$, où $u = (u_A, u_F)$ est composé de bits d'information ($u_A$) et de bits gelés ($u_F$). Crucialement, $u_F$ est tiré i.i.d. d'une distribution uniforme ($\text{Bernoulli}(1/2)$) et agit comme une clé secrète partagée entre l'encodeur et le décodeur, mais reste inconnue de l'adversaire.
• Exposition Publique : Un sous-ensemble d'indices $P \subset [1:N]$ est publié. L'adversaire observe $x_P = u_A G_{A,P} \oplus u_F G_{F,P}$, où $G_{A,P}$ et $G_{F,P}$ sont des sous-matrices de la matrice génératrice restreintes respectivement aux lignes $P$ et aux colonnes $A$ et $F$.
• Définition de la Fuite : La fuite est définie comme l'information mutuelle $L(P) = I(u_A; x_P)$.

2. L'Identité de Fuite

L'article établit une identité fondamentale reliant l'information mutuelle aux rangs des matrices :
$$L(P) = \text{rang}(G_P) - \text{rang}(G_{F,P})$$
où $G_P$ est la sous-matrice de $G_N$ restreinte aux lignes $P$ et à toutes les colonnes, et $G_{F,P}$ est restreinte aux lignes $P$ et aux colonnes gelées $F$.

• Interprétation : $L(P)$ représente le nombre de combinaisons linéaires indépendantes du vecteur d'information $u_A$ qu'un adversaire peut récupérer à partir de l'observation publique $x_P$.
• Certificat de Fuite : Si $L(P) = 0$, aucune information sur $u_A$ n'est révélée (les colonnes de $G_{A,P}$ résident entièrement dans l'espace colonne de $G_{F,P}$). Si $L(P) = r > 0$, jusqu'à $r$ bits d'information indépendants sont exposés.

3. Extraction Constructive

L'article démontre que si $L(P) = r$, il existe une matrice d'extraction linéaire explicite $R$ telle que :

1. $G_{F,P} R = 0$ (éliminant l'effet des bits gelés).
2. $\text{rang}(G_{A,P} R) = r$.
   La multiplication de l'observation publique par $R$ donne $x_P R = u_A (G_{A,P} R)$, fournissant à l'adversaire $r$ équations linéaires indépendantes concernant les bits du message.

4. Algorithme de Sélection (ScoreGreedy)

Puisque la recherche exhaustive de l'ensemble optimal $P$ de taille $k$ pour minimiser la fuite est combinatoirement coûteuse ($O(\binom{N}{k} \cdot Nk^2)$), les auteurs proposent un algorithme ScoreGreedy (SG) :

• Notation : Chaque ligne $i$ est notée selon $s_i = f_i - a_i$, où $f_i$ est le nombre d'entrées non nulles dans les colonnes gelées et $a_i$ est le nombre d'entrées non nulles dans les colonnes d'information pour cette ligne.
• Sélection : L'algorithme sélectionne les $k$ premières lignes ayant les notations les plus élevées.
• Bornes Théoriques : Le théorème 3 fournit une borne supérieure déterministe, montrant que la somme des $a_i$ pour l'ensemble sélectionné borne la fuite, justifiant l'objectif substitutif de minimiser les contacts avec les colonnes d'information tout en maximisant les contacts avec les colonnes gelées.

Contributions Clés

1. Certificat de Fuite Exact : La dérivation de l'identité de différence de rangs $L(P) = \text{rang}(G_P) - \text{rang}(G_{F,P})$, qui fournit une mesure exacte, non asymptotique, de la fuite d'informations pour tout ensemble d'indices publié dans les codes polaires de longueur finie.
2. Extracteurs Constructifs : La preuve de l'existence d'une matrice $R$ qui construit explicitement les combinaisons linéaires de bits de message divulguées par un ensemble public spécifique $P$.
3. Procédures de Certification Efficaces : Le développement d'algorithmes efficaces pour calculer la fuite et certifier la sécurité pour tout ensemble d'indices, dépassant l'analyse asymptotique du taux de confidentialité pour atteindre des garanties de bloc fini.
4. Algorithme de Sélection Pratique : L'introduction de l'algorithme ScoreGreedy, une heuristique rapide ($O(N^2)$) pour sélectionner les indices publics minimisant la fuite, validée par une borne supérieure théorique.

Résultats et Exemples

L'article valide le cadre par des preuves théoriques et des exemples illustratifs (par exemple, codes polaires $N=4$) :

• Scénario 1 : Publier une coordonnée qui porte directement un bit d'information (par exemple, $x_4 = u_4$) résulte en $L(P)=1$, exposant pleinement le bit.
• Scénario 2 : Publier une coordonnée qui est une combinaison linéaire de bits d'information et de bits gelés (par exemple, $x_1 = u_4 \oplus u_3 \oplus u_2 \oplus u_1$) résulte en $L(P)=0$ si les bits gelés masquent efficacement l'information, ne révélant aucune combinaison linéaire indépendante.
• Ensembles Mixtes : Le cadre quantifie correctement la fuite partielle (par exemple, $L(P)=2$) lorsqu'un ensemble de coordonnées expose des relations linéaires entre les bits d'information, malgré le fait que certains soient masqués.

Importance et Revendications

Les auteurs positionnent RankGuard-Polar comme une couche opérationnelle d'audit et de contrôle pour les systèmes utilisant des ressources publiques.

• Focus sur la Longueur Finie : Contrairement à la littérature classique sur le fil d'écoute qui repose souvent sur des taux de confidentialité asymptotiques lorsque la longueur du bloc $N \to \infty$, ce travail fournit des garanties exactes pour un $N$ fini.
• Modèle d'Adversaire Fort : Le cadre est conçu pour un espion fort qui observe l'entrée du canal, un scénario distinct des modèles de fil d'écoute standard où l'adversaire observe une sortie de canal bruitée.
• Utilité Pratique : La méthode ne remplace pas les constructions de fil d'écoute asymptotiques mais offre un mécanisme pour certifier et contrôler la fuite dans les systèmes réels où l'utilisation mixte de canaux publics/privés est nécessaire pour le débit ou la réduction des coûts.
• Transparence Algébrique : En réduisant la confidentialité à l'algèbre linéaire (rangs de matrices), le cadre offre un moyen transparent et calculable de vérifier les propriétés de sécurité sans dépendre d'hypothèses cryptographiques complexes ou de matrices génératrices secrètes.

L'article conclut que RankGuard-Polar permet l'exploitation sûre des canaux publics en fournissant une méthode rigoureuse et constructive pour déterminer exactement quelles coordonnées de mots de code peuvent être exposées et quelle quantité d'informations est compromise.