Beyond Epsilon: A Principled QIF Framework for Local Differential Privacy

Titre : Au-delà d'Epsilon : Un Cadre QIF Principé pour la Confidentialité Différentielle Locale

Énoncé du problème
La Confidentialité Différentielle Locale (LDP) est devenue la norme pour la collecte de données préservant la vie privée dans les systèmes à grande échelle, en particulier pour l'estimation de fréquences. Cependant, le paysage actuel de comparaison des protocoles LDP repose fortement sur deux approches limitées :

1. Le paramètre $\epsilon$ : Il borne la discernabilité dans le pire des cas mais échoue à capturer la fuite d'information réelle sous des attaques d'inférence réalistes (par exemple, la reconstruction de données ou la ré-identification). Deux protocoles satisfaisant la même garantie $\epsilon$-LDP peuvent présenter des comportements de fuite significativement différents.
2. L'analyse axée sur l'utilité : Les protocoles sont classés en fonction de l'erreur d'estimation (par exemple, l'erreur quadratique moyenne) pour un $\epsilon$ fixe. Cette vue dépend de la métrique et ne fournit pas un ordre principé de la force de la confidentialité indépendant de la fonction d'utilité spécifique.

Par conséquent, il manque une méthode systématique et indépendante de l'adversaire pour déterminer quand un protocole LDP est intrinsèquement plus privé qu'un autre.

Méthodologie
Les auteurs proposent un cadre basé sur le Flux d'Information Quantitatif (QIF) pour analyser les protocoles d'estimation de fréquences LDP. La méthodologie centrale comprend :

• Modélisation des canaux : Représentation des mécanismes LDP comme des canaux probabilistes d'information définis par des matrices de canal stochastiques par lignes ($C_{x,y} = \Pr[Y=y|X=x]$).
• Relations de raffinement (Ordre de Blackwell) : Utilisation du concept de raffinement de canal ($B \sqsubseteq A$) pour établir un ordre partiel. Le protocole $A$ affine $B$ si $A$ ne fuit pas plus d'informations que $B$ à l'intention de n'importe quel adversaire du cas moyen, indépendamment de ses connaissances a priori ou de sa fonction de gain spécifique. Cela équivaut à ce que $A$ soit un « brouillage » de $B$ (c'est-à-dire $B \cdot W = A$ pour un certain canal $W$).
• Lien avec la $\epsilon$-Confidentialité Différentielle ($f$-DP) : Exploitation de l'équivalence entre le raffinement QIF et l'ordonnancement des fonctions de compromis dans la $f$-DP (dérivée du lemme de Neyman-Pearson) pour comparer les mécanismes, en particulier pour les canaux binaires.
• Mesures de vulnérabilité : Analyse des protocoles à l'aide de la capacité de Bayes (fuite moyenne maximale) et liaison directe des attaques de reconstruction de données à la vulnérabilité de Bayes sous une loi uniforme a priori.

Les auteurs appliquent ce cadre à sept protocoles de l'état de l'art : Réponse Randomisée Généralisée (GRR), Sélection de Sous-ensemble (SS), Hachage Local Binaire (BLH), Hachage Local Optimisé (OLH), Encodage Unaire Symétrique (SUE), Encodage Unaire Optimisé (OUE) et Seuillage avec Encodage d'Histogramme (THE).

Contributions clés

1. Cadre QIF unifié : L'article fournit un cadre indépendant de la métrique pour comparer les protocoles LDP via des matrices de canal et des relations de raffinement, permettant des comparaisons à travers divers adversaires et fonctions d'utilité.
2. Pont entre LDP et QIF : Les auteurs démontrent formellement que les attaques de reconstruction de données étudiées dans la littérature antérieure coïncident avec les notions QIF standard de vulnérabilité de Bayes. Plus précisément, le taux de réussite attendu de telles attaques correspond à la capacité de Bayes du canal LDP.
3. Correction de l'analyse du hachage local : L'article identifie et corrige une erreur dans l'analyse de l'attaque de reconstruction de données attendue pour les protocoles de Hachage Local (LH) (spécifiquement BLH et OLH) rapportée dans un travail précédent [8]. Les auteurs dérivent le risque de Bayes correct via la vulnérabilité moyennée, fournissant une formule qui correspond aux évaluations expérimentales pour toutes les tailles de domaine, contrairement à l'approximation précédente qui échouait pour les petits domaines.
4. Analyse de raffinement : L'étude établit des relations de raffinement entre les protocoles, révélant que :
   • Les familles GRR, SUE, OUE et THE forment des « familles de raffinement » où la monotonie de la confidentialité vaut par rapport à $\epsilon$.
   • OUE et SUE sont incomparables (aucun ne raffine l'autre) dans le contexte binaire.
   • THE affine SUE pour tout $\theta$, mais la relation entre THE et OUE dépend du seuil $\theta$ et de $\epsilon$.
   • Les protocoles précédemment jugés « optimaux » sur la base de métriques d'erreur sont parfois strictement dominés par ou incomparables à d'autres protocoles lorsqu'ils sont examinés à travers le prisme de la fuite d'information.

Résultats

• Validation expérimentale : En utilisant l'ensemble de données Kosarak, les auteurs ont corroboré expérimentalement les relations de raffinement théoriques. Par exemple, ils ont confirmé que lorsque le seuil $\theta$ dans THE satisfait des conditions spécifiques par rapport à $\epsilon$, OUE fuit plus d'informations que THE ; sinon, la relation n'est pas raffinée.
• Convergence de la capacité de Bayes : L'analyse des capacités de Bayes a révélé des comportements de convergence distincts à mesure que $\epsilon$ augmente :
  • GRR, SS et THE convergent vers $k$ (la taille du domaine).
  • SUE converge vers une valeur légèrement supérieure à $k$.
  • BLH converge vers 2 (en raison de sa sortie binaire).
  • OLH et OUE convergent vers environ $k/2$.
• Correction des formules LH : La nouvelle formule du Taux de Succès Adversarial (ASR) pour le Hachage Local (Éq. 26) a été montrée comme correspondant aux résultats expérimentaux pour tous les $k$ et $\epsilon$, tandis que la formule précédente (Éq. 25) s'écartait significativement pour les petits domaines.

Signification
L'article prétend combler le fossé entre les communautés LDP et des méthodes formelles. En allant au-delà du seul paramètre $\epsilon$ et des métriques spécifiques à l'utilité, l'approche basée sur le QIF proposée permet un « raisonnement principé et conscient de l'adversaire » sur les systèmes privés localement. Elle révèle que les classifications basées uniquement sur l'erreur d'estimation peuvent être trompeuses, car elles peuvent ignorer des cas où un protocole est strictement dominé par un autre en termes de fuite de confidentialité. Le cadre offre une méthode plus robuste et complète pour évaluer la supériorité des protocoles, garantissant que les garanties de confidentialité sont comprises non seulement comme des bornes du pire des cas, mais comme des mesures précises du flux d'information face à divers modèles de menace.