Computing Maximal Per-Record Leakage and Leakage-Distortion Functions for Privacy Mechanisms under Entropy-Constrained Adversaries

1. Problématique et Contexte

L'explosion des volumes de données collectées, propulsée par l'IA et l'analytique, crée une tension fondamentale entre l'utilité des données et la protection de la vie privée. Le modèle standard actuel, la Différentielle Privée (DP), repose sur une hypothèse d'indépendance statistique entre les enregistrements d'un jeu de données. Cette hypothèse est souvent irréaliste dans les scénarios réels où un adversaire possède une connaissance partielle mais corrélée des données.

L'article propose de dépasser ce cadre en adoptant le modèle de l'Information Privacy (IP) introduit dans une étude précédente [35]. Ce modèle remplace l'hypothèse d'indépendance par une contrainte d'entropie sur la connaissance a priori de l'adversaire : $H(X) \ge b$. Cela signifie que l'adversaire doit avoir au moins $b$ bits d'incertitude sur l'ensemble du jeu de données.

Le défi central identifié dans la littérature précédente était le calcul pratique des quantités clés de ce cadre théorique. Les problèmes d'optimisation sous-jacents sont de haute dimension, non convexes et contraints par l'entropie, rendant les solutions directes inaccessibles.

2. Formalisation des Problèmes

Les auteurs formalisent trois problèmes d'optimisation fondamentaux qui étendent les concepts de la théorie de l'information (capacité de canal, taux-distorsion) au domaine de la confidentialité :

1. Fuite Maximale par Enregistrement (Maximal Per-Record Leakage) :
   Calculer la pire fuite d'information $L(b)$ concernant un enregistrement individuel $X_i$ face à un adversaire contraint par l'entropie.
   $$L(b) = \max_{i \in [n]} \max_{p(x) \in \Delta(X), H(X) \ge b} I(X_i; Y)$$
   où $I(X_i; Y)$ est l'information mutuelle entre l'enregistrement et la sortie du mécanisme.

2. Fonction Primal Fuite-Distorsion (Primal Leakage-Distortion Tradeoff) :
   Concevoir un mécanisme de confidentialité $q(y|x)$ qui minimise la fuite maximale tout en respectant une contrainte d'utilité (distorsion maximale $D$).
   $$\epsilon(D, b) = \min_{q} \max_{i} \max_{p(x): H(X) \ge b} I(X_i; Y) \quad \text{s.t.} \quad E_{p_0}[d(f(X), Y)] \le D$$

3. Fonction Dual de Minimisation de la Distorsion (Dual Minimal-Distortion) :
   Minimiser la distorsion attendue (perte d'utilité) sous une contrainte stricte de fuite maximale $L$.
   $$D(L, b) = \min_{q} E_{p_0}[d(f(X), Y)] \quad \text{s.t.} \quad \max_{i} \max_{p(x): H(X) \ge b} I(X_i; Y) \le L$$

3. Méthodologie et Algorithmes

La contribution centrale de l'article réside dans le développement d'algorithmes d'optimisation alternée efficaces, exploitant la structure mathématique spécifique de ces problèmes.

Propriétés Structurelles Clés

Les auteurs s'appuient sur la dualité convexité-concavité de l'information mutuelle $I(X_i; Y)$ :

• Elle est concave par rapport à la distribution marginale $p(x_i)$ (pour des conditionnels fixes).
• Elle est convexe par rapport aux distributions conditionnelles $p(x_{-i}|x_i)$ et au mécanisme $q(y|x)$.
• Les ensembles de contraintes définis par l'entropie ($H(X) \ge b$) sont convexes.

Algorithmes Proposés

L'article présente une suite d'algorithmes (de 1 à 11) pour résoudre les trois problèmes :

• Algorithme 1 (Calcul de la Fuite Maximale) : Utilise une optimisation alternée entre la mise à jour de la distribution marginale $p(x_i)$ et des distributions conditionnelles $p(x_{-i}|x_i)$.

  • Pour la marginale : Une version modifiée de l'algorithme Blahut-Arimoto est utilisée, intégrant un multiplicateur de Lagrange pour respecter la contrainte d'entropie.
  • Pour les conditionnels : Une méthode de descente de gradient projetée par coordonnées est employée. Le théorème 3 montre que la solution optimale se trouve sur la frontière de l'ensemble d'entropie, permettant de décomposer le problème global en contraintes de ligne par ligne.

• Algorithme 6 (Optimisation Primal Fuite-Distorsion) : Alterne entre la mise à jour de la distribution a priori de l'adversaire (via l'Algorithme 1) et la mise à jour du mécanisme de confidentialité.

  • La mise à jour du mécanisme utilise une méthode de pénalité lisse (smooth penalty) avec une descente de gradient exponentielle (exponentiated gradient descent) et une recherche linéaire de type backtracking (Armijo) pour gérer les contraintes de distorsion.

• Algorithme 9 (Optimisation Dual) : Résout le problème inverse (minimiser la distorsion sous contrainte de fuite). Il utilise une approche similaire à l'Algorithme 6 mais avec une fonction de pénalité sur la contrainte de fuite plutôt que sur la distorsion.

Garanties de Convergence

Les auteurs prouvent théoriquement que :

• Les algorithmes convergent vers un point stationnaire satisfaisant les conditions KKT.
• Pour le problème de fuite maximale, la convergence est locale, avec une garantie de convergence globale dans le cas sans contrainte d'entropie ($b=0$).
• Les taux de convergence sont de l'ordre de $O(1/k)$ dans le cas général, et linéaires lorsque les contraintes sont inactives.

4. Résultats Expérimentaux

Les algorithmes ont été validés sur des canaux binaires symétriques (BSC) et des requêtes de somme modulaire, en comparaison avec les mécanismes classiques de DP (Laplace et Exponentielle).

• Impact de la Contrainte d'Entropie : Les résultats montrent que l'augmentation de la contrainte d'entropie $b$ (plus d'incertitude pour l'adversaire) réduit significativement la fuite d'information maximale $L(b)$, confirmant l'efficacité du modèle.
• Compromis Utilité-Confidentialité :
  • Pour une même distorsion attendue, le canal binaire symétrique optimisé sous le cadre IP nécessite un budget de confidentialité $\epsilon$ (fuite) plus faible que les mécanismes Laplace et Exponentielle classiques.
  • Inversement, pour un même niveau de fuite, le cadre IP permet d'obtenir une distorsion plus faible (meilleure utilité).
• Validation des Algorithmes : Les courbes de compromis (Pareto) générées par les algorithmes 6 et 9 montrent une convergence stable et une satisfaction stricte des contraintes, démontrant la capacité à auditer et concevoir des mécanismes certifiés.

5. Signification et Contributions

Cet article apporte plusieurs contributions majeures au domaine de la protection de la vie privée :

1. Cadre de Calcul Pratique : Il comble le fossé entre la théorie de l'information privée (IP) et son application pratique en fournissant des algorithmes convergents pour des problèmes d'optimisation complexes et de haute dimension.
2. Modélisation Réaliste : En abandonnant l'hypothèse d'indépendance de la DP au profit d'une contrainte d'entropie, le modèle capture mieux les scénarios réels où les attaquants ont une connaissance partielle mais corrélée des données.
3. Outils d'Audit et de Conception : Le cadre permet non seulement de concevoir de nouveaux mécanismes optimaux, mais aussi d'auditer précisément les risques de fuite des mécanismes existants (y compris ceux de la DP) sous des hypothèses d'adversaire réalistes.
4. Connexion Théorique : L'article établit un lien fort entre la théorie de l'information classique (capacité de canal, taux-distorsion) et la confidentialité des données, ouvrant la voie à de nouvelles analyses théoriques.

En conclusion, ce travail fournit une fondation computationnelle robuste pour l'audit des risques de confidentialité et la conception de mécanismes certifiés, démontrant que l'intégration de contraintes d'entropie permet d'obtenir de meilleurs compromis entre protection de la vie privée et utilité des données que les approches traditionnelles basées sur l'indépendance.