Better Privacy Guarantees for Larger Groups

Résumé Technique : Meilleures Garanties de Confidentialité pour des Groupes Plus Grands

Énoncé du Problème
Cet article traite d'un problème ouvert posé par Pujol et Desfontaines [2023] concernant la conception d'histogrammes privés pour des groupes fixes et disjoints. Les mécanismes classiques de confidentialité différentielle ajoutent généralement un bruit d'une magnitude fixe à chaque décompte, ce qui fournit une confidentialité absolue uniforme mais entraîne des erreurs relatives nettement plus petites pour les grands groupes par rapport aux petits. La question centrale est de savoir si l'on peut « dépenser » cet excédent de précision différemment : en permettant à l'erreur d'un groupe de croître proportionnellement à son décompte ($x_i$), afin de fournir des garanties de confidentialité plus fortes (un budget de confidentialité plus faible) pour les membres des groupes plus importants.

L'article étudie cela sous le modèle d'adjacence « ajouter ou supprimer un élément » (add-or-remove-one). L'objectif est de trouver un mécanisme dont le budget de confidentialité $v(n)$ ne dépend que du nombre de membres du groupe $n$, est non croissant, et satisfait la zCDP (zero-concentrated differential privacy) par groupe dépendante du décompte. Cela nécessite de borner la divergence de Rényi dans les deux directions pour tout ordre $\alpha > 1$ entre des jeux de données voisins.

Un obstacle technique critique identifié est la condition limite à zéro. La formulation originale exigeait que l'erreur absolue attendue soit strictement inférieure à $r x_i$. Pour $x_i = 0$, cela implique $E|\hat{x}_i| < 0$, ce qui est impossible. De plus, relaxer l'inégalité en $\leq$ tout en maintenant une divergence de Rényi deux-faces finie à travers l'arête $0 \leftrightarrow 1$ mène à une contradiction (forçant la sortie au décompte 1 à être déterministe, violant ainsi la borne d'erreur).

Méthodologie et Formulation Réparée
Pour résoudre le problème de la limite, les auteurs proposent une « formulation réparée » de l'exigence d'utilité :
$$E|\hat{x}_i - x_i| < r \max\{x_i, 1\}$$
Cela maintient la cible d'erreur relative pour tous les décomptes positifs tout en introduisant une tolérance absolue fixe à zéro, rendant le problème réalisable.

L'article emploie deux approches méthodologiques principales :

1. Faisabilité (Borne Supérieure) : Les auteurs spécialisent un cadre existant de « transformation décalée » (shifted-transformation) (Finley et al. [2026]). Ils transforment l'espace des décomptes via un logarithme avec un décalage $c$ (soit $\log(x_i + c)$), ajoutent un bruit gaussien à variance fixe, et appliquent une dérive déterministe avant l'exponentiation et le tronquage (clipping).

   • Innovation Clé : Contrairement aux mécanismes log-normaux standards qui utilisent une dérive de $-\sigma^2/2$ pour assurer l'absence de biais de la moyenne, ce mécanisme utilise une dérive de $-\sigma^2$. Cette dérive spécifique est choisie pour minimiser l'erreur multiplicative absolue attendue, ce qui s'aligne sur la métrique d'utilité de l'article.
   • Mécanisme de Confidentialité : En travaillant dans l'espace logarithmique avec une variance égale, le mécanisme garantit que la divergence de Rényi entre les décomptes adjacents est finie pour tous les ordres $\alpha$, évitant ainsi l'« obstruction de queue » (tail obstruction) où des variances inégales causent une divergence infinie dans une direction.

2. Impossibilité (Borne Inférieure) : Les auteurs prouvent qu'aucun mécanisme satisfaisant la l'utilité réparée et les exigences de zCDP dépendante du décompte ne peut atteindre un taux de décroissance du budget de confidentialité plus rapide que l'inverse du carré du décompte.

   • Argument à deux décomptes : Un test entre deux décomptes spécifiques établit l'exposant $n^{-2}$.
   • Argument à plusieurs décomptes : En utilisant une variable aléatoire de « décalage caché » (hidden offset) et des arguments d'information théorique (liant l'erreur absolue attendue à l'information mutuelle), les auteurs dérivent une borne inférieure plus serrée sur le coefficient principal du budget de confidentialité.

Résultats Clés

• Taux Asymptotique Optimal : Pour tout $r$ fixé tel que $0 < r < 1$, le budget de confidentialité optimal $v(n)$ décroît selon $\Theta_r(n^{-2})$.

  • Borne Supérieure : Le mécanisme gaussien log-décalé (shifted-log Gaussian) atteint $v(n) = O_r(n^{-2})$. Plus précisément, quand $n \to \infty$, $v(n) \approx \frac{1}{2\sigma^2 n^2}$.
  • Borne Inférieure : Tout mécanisme satisfaisant les exigences doit avoir $\liminf_{n \to \infty} n^2 v(n) \geq \frac{(1-r)^6}{128r^2(1+r)^2}$. Cela confirme que le taux en inverse du carré est intrinsèque et n'est pas un artefact de la construction.

• Coefficients Principaux : L'article réduit l'écart entre la meilleure borne supérieure et la meilleure borne inférieure pour le coefficient principal $C^*$ dans la limite de petits $r$ et de grands $n$ :
  $$\frac{\pi}{4e^2} \leq C^* \leq \frac{1}{\pi}$$
  Le ratio entre ces bornes est d'environ 2,995, indiquant que les bornes sont à moins d'un facteur trois de l'une de l'autre.

• Échec de la Gaussienne à Variance Inégale : L'article démontre qu'un mécanisme naïf publiant $N(n, r^2 n^2)$ (bruit gaussien avec une variance proportionnelle au carré du décompte) échoue à la définition de la zCDP. Bien qu'il possède la bonne échelle d'erreur, les variances inégales entre les décomptes adjacents font que la divergence de Rényi dans une direction devient infinie pour des ordres $\alpha$ suffisamment élevés, violant l'exigence de « tous les ordres » de la zCDP.

• Cas Trivial : À $r=1$, une publication indépendante des données (par exemple, toujours publier $0,5$) satisfait le critère réparé avec une perte de confidentialité nulle ($v \equiv 0$).

Signification et Revendications
L'article affirme fournir la première preuve indépendante du mécanisme montrant que le taux de l'inverse du carré est optimal pour cette formulation spécifique de la confidentialité par groupe.

• Faisabilité : Il établit que la formulation « réparée » est soluble et fournit un mécanisme concret et composable (log-gaussien décalé) qui atteint le taux optimal.
• Optimalité : Il prouve qu'aucun mécanisme, quelle que soit sa complexité ou sa structure de corrélation, ne peut améliorer le taux de décroissance en $n^{-2}$.
• Précision : En employant des arguments d'information sur de nombreux décomptes, l'article resserre considérablement les bornes sur le coefficient constant par rapport aux analyses précédentes basées sur deux décomptes, réduisant l'incertitude à un facteur de moins de trois.

Les auteurs déclarent explicitement que déterminer la valeur exacte du coefficient optimal $C^*$ reste une question ouverte. Ils notent également que leurs résultats s'appliquent à des groupes fixes et disjoints ; les groupes chevauchants ou dépendants des données nécessiteraient une analyse de sensibilité distincte. Le mécanisme est biaisé (en raison de la dérive $-\sigma^2$) mais est calibré spécifiquement pour minimiser l'erreur absolue attendue, et non pour être sans biais.