Résumé technique : Le Triade de Dépendance (DT) pour la quantification des dépendances dans la Confidentialité Différentielle Locale

1. Énoncé du problème

La collecte de données utilisateur multidimensionnelles sous Confidentialité Différentielle Locale (LDP) fait face à un défi critique : la Fuite de Confidentialité Induite par la Corrélation (CPL). Bien que les mécanismes LDP (par exemple, $\epsilon$-LDP) limitent la fuite pour les attributs individuels, les dépendances entre attributs peuvent involontairement révéler des informations corrélées, augmentant ainsi les vulnérabilités de confidentialité au-delà du budget prévu.

Les solutions existantes pour quantifier la CPL souffrent de deux limitations principales qui entravent leur applicabilité pratique :

1. Contraintes de scalabilité et de mécanisme : De nombreux algorithmes existants (par exemple, ITS, CBP, HCC-1/2, LTM) sont soit restreints à des mécanismes LDP spécifiques (par exemple, la perturbation à deux niveaux), soit souffrent de complexités temporelles et spatiales élevées (par exemple, $O(a^2b^2)$ ou $O(a^2b \log b)$) par rapport aux tailles d'alphabet des attributs ($a, b$). Cela les rend intraitables pour les attributs à haute cardinalité ou pour le calibrage itératif du budget de confidentialité.
2. Dépendance vis-à-vis des distributions de vérité terrain : Les méthodes actuelles supposent l'accès à la distribution de probabilité jointe exacte, de vérité terrain, entre les attributs. Dans les scénarios LDP réels, cette distribution est rarement connue ; elle est souvent estimée à partir de données antérieures, de jeux de données publics ou de sous-ensembles de la population. Les écarts entre le prior connu et la distribution réelle (dus à des changements démographiques, des biais d'échantillonnage ou une obsolescence) peuvent conduire à une sous-estimation de la fuite, créant des vulnérabilités de confidentialité, ou à une surestimation, réduisant l'utilité des données.

Le document pose qu'il est nécessaire d'avoir une métrique capable d'estimer la CPL en temps constant, qui soit compatible avec les distributions creuses et qui reste robuste à l'incertitude distributionnelle sans nécessiter la connaissance de la vérité terrain.

2. Méthodologie : La Triade de Dépendance (DT)

Les auteurs proposent la Triade de Dépendance (DT), une nouvelle métrique qui résume l'information de dépendance par paire pertinente pour la CPL en utilisant trois paramètres : $(\alpha, \beta, \delta)$.

A. Concept central

Au lieu de stocker la distribution jointe complète $a \times b$, la DT compresse la structure de dépendance en trois paramètres scalaires. Cela permet une estimation en temps constant ($O(1)$) de la CPL pour n'importe quel budget de confidentialité $\epsilon$.

B. Dérivation des paramètres

La dérivation implique l'approximation des vecteurs de probabilité conditionnelle $G$ et $G'$ (représentant $P(\hat{X}|X_k=x)$ et $P(\hat{X}|X_k=x')$) via leurs rapports élément par élément.

1. $\alpha$ (Borne supérieure des rapports) : Représente le rapport de vraisemblance maximal, régissant le comportement de fuite dans le régime de faible confidentialité (grand $\epsilon$). Il est défini comme :
   $$\alpha = \ln \left( \max_{\hat{x}, x, x'} \frac{p(\hat{x}|x) + \Delta_{\hat{x},x}}{p(\hat{x}|x') - \Delta_{\hat{x},x'}} \right)$$
   où $\Delta$ représente la matrice d'incertitude.

2. $\delta$ (Correction de la parcimonie) : Prend en compte les cas où la distribution est creuse (c'est-à-dire que les dénominateurs deviennent nuls). Il capture la concentration de masse dans les cas limites où $p(\hat{x}|x') = 0$.

3. $\beta$ (Borne inférieure calibrée) : À l'origine, un paramètre $\gamma$ (rapport minimum) était utilisé. Cependant, les auteurs ont constaté que $(\alpha, \gamma, \delta)$ pouvait entraîner des erreurs de surestimation. Pour améliorer la précision tout en maintenant une borne supérieure conservatrice, ils introduisent une étape de calibration. $\beta$ est dérivé en calibrant la borne inférieure à un budget de confidentialité spécifique $\epsilon_0$ (typiquement $\epsilon_0 \to 0$) pour correspondre à la CPL exacte ($CPL^\star$) de la distribution connue. Cela garantit que l'estimateur est une borne supérieure étroite pour tout $\epsilon \geq \epsilon_0$.

C. Gestion de l'incertitude distributionnelle

Pour répondre à l'absence de données de vérité terrain, la DT incorpore explicitement un ensemble d'incertitude $\Delta$ autour de la distribution connue $P_K$. Les paramètres $(\hat{\alpha}, \hat{\beta}, \hat{\delta})$ sont calculés en optimisant sur la région réalisable définie par $P_K \pm \Delta$. Cela garantit que l'estimation de la CPL résultante est une borne supérieure conservatrice, même si la distribution réelle $P_A$ dévie de $P_K$ à l'intérieur des limites d'incertitude.

D. Algorithmes

• Algorithme 1 : Calcule les paramètres $(\alpha, \beta, \delta)$ à partir d'une distribution connue et d'une matrice d'incertitude. Cela implique d'itérer sur les paires d'attributs et de résoudre un programme linéaire (LP) relaxé pour trouver $\phi$ (utilisé pour $\beta$), ce qui résulte en une complexité de pré-calcul de $O(a^2b^{3.5})$.
• Algorithme 2 : Estime la CPL en utilisant les paramètres DT pré-calculés et le budget de confidentialité $\epsilon$ en temps constant $O(1)$.

3. Principales contributions

1. Nouvelle métrique (DT) : La première métrique spécifiquement conçue pour résumer les dépendances par paire pour l'analyse de fuite LDP en utilisant seulement trois paramètres. Elle sert de substitut conservateur à la distribution jointe complète.
2. Garanties théoriques :
   • Borne supérieure : Les auteurs prouvent que l'estimateur basé sur la DT est une borne supérieure étroite sur la véritable CPL ($CPL^\star$), garantissant que les fuites rapportées ne sous-estiment jamais la perte de confidentialité réelle.
   • Robustesse à l'incertitude : La métrique est prouvée comme restant valide et conservatrice même lorsque le prior est incertain ou mal apparié.
   • Complexité : Elle réduit la complexité spatiale de $O(ab)$à$O(1)$ et le temps d'évaluation de polynomial à constant.
3. Mécanisme de calibration : Une méthode pour calibrer le paramètre $\beta$ afin de minimiser l'erreur d'estimation tout en préservant la garantie de confidentialité, traitant les lacunes de précision des simples approximations de rapports.
4. Validation empirique : Des expériences approfondies sur cinq jeux de données réels (SPM, CelebA, Adult, CVD, DSS) et des données synthétiques démontrent que la DT estime systématiquement la CPL avec une erreur quadratique moyenne normalisée très faible (NMSE < 0,025) à travers divers régimes de dépendance et budgets de confidentialité.

4. Résultats expérimentaux

• Précision : La DT atteint des erreurs d'estimation très faibles par rapport à la $CPL^\star$ optimale (calculée par des bases comme HCC-2 et LTM) sur des jeux de données réels. Dans les régimes de haute confidentialité ($\epsilon \in (0, 1]$), la NMSE est exceptionnellement basse (< 0,003).
• Scalabilité : Contra-irement aux modèles de référence qui nécessitent un nouveau calcul pour chaque budget de confidentialité, la DT permet une évaluation rapide. Dans un scénario de calibrage de budget, la DT a complété la tâche en 7 secondes contre 61 secondes pour la base LTM.
• Robustesse à l'incertitude : Testée avec des décalages distributionnels (simulés par des variations de marges d'erreur allant jusqu'à 10 %–20 %), la DT a maintenu une borne supérieure étroite sur la fuite réelle, tandis que les méthodes ignorant l'incertitude risquaient la sous-estimation.
• Régimes structurels : La DT a bien performé à travers diverses structures de dépendance (faible entropie, parcimonie, un-vers-plusieurs, etc.). Elle a été extrêmement précise pour les dépendances concentrées et conservatrice pour les distributions creuses ou sensibles aux queues de distribution.
• Compromis Confidentialité-Utilité : Dans les tâches d'attaque par inférence d'attribut et d'estimation de marges-$k$, le calibrage de budget enabled par la DT a obtenu une utilité comparable ou supérieure (distance de variation totale plus faible) aux méthodes de division standard (SPL) ou d'échantillonnage aléatoire (RS), particulièrement pour les marges d'ordre supérieur, tout en maintenant une résistance robuste aux attaques d'inférence.

5. Signification et affirmations

Le document affirme que la Triade de Dépendance (DT) comble le fossé entre l'analyse de confidentialité théorique et le déploiement pratique dans des contextes LDP multidimensionnels.

• Applicabilité pratique : En supprimant l'exigence de distributions de vérité terrain et en permettant l'estimation en temps constant, la DT rend l'analyse rigoureuse de la CPL réalisable pour les pipelines de collecte de données réels où les distributions sont incertaines et de haute dimension.
• Sécurité : La nature conservatrice de l'estimateur garantit que les garanties de confidentialité ne sont pas compromises par des décalages de distribution, une exigence critique pour le déploiement de la LDP dans des environnements non approuvés.
• Efficacité : La capacité de réaliser une estimation de fuite en temps constant permet un calibrage dynamique et itératif du budget de confidentialité, optimisant le compromis confidentialité-utilité sans engendrer de coûts de calcul prohibitifs.

Les auteurs concluent que, bien que la DT ne caractérise pas entièrement la distribution jointe sous-jacente, elle fournit un bloc de construction suffisant, traitable et théoriquement fondé pour évaluer la fuite de confidentialité totale dans des contextes multidimensionnels, surmontant les limitations de scalabilité et de disponibilité des données des méthodes existantes.