Universal Shuffle Asymptotics: Sharp Privacy Analysis in the Gaussian Regime

1. Problématique et Contexte

Le modèle de différential privacy par mélange (Shuffle Model) est une architecture intermédiaire entre les modèles locaux (LDP) et centraux (CDP). Dans ce modèle, $n$ utilisateurs appliquent un randomiseur local $W$ à leurs données binaires, envoient des messages à un shuffleur de confiance qui les permute uniformément, et un analyste observe uniquement l'histogramme des messages reçus (la distribution des fréquences).

Bien que l'amplification de la confidentialité par mélange soit bien établie, la littérature existante se concentre souvent sur des bornes de taux (ordre de grandeur) ou des approximations grossières. Il manque une théorie précise (sharp) au niveau de l'expérience pour :

• Obtenir les constantes exactes et les termes d'ordre supérieur.
• Décrire les courbes de confidentialité complètes $(\varepsilon, \delta)$ plutôt que des inégalités de type majoration.
• Comprendre rigoureusement le régime Gaussien, où les randomiseurs locaux ont un support complet et où les expériences de mélange adjacentes sont asymptotiquement équivalentes à un décalage gaussien unidimensionnel.

L'objectif de cet article est de combler ces lacunes en développant une théorie asymptotique précise pour ce régime, en corrigeant notamment des erreurs de covariance fréquentes dans la littérature.

2. Méthodologie

L'auteur développe une approche analytique basée sur la théorie des expériences statistiques et les expansions asymptotiques. Les piliers méthodologiques sont :

1. Identités exactes du rapport de vraisemblance :

   • Pour la paire canonique (0 vs 1 utilisateur différent), le rapport de vraisemblance est linéaire par rapport à l'histogramme.
   • Pour les paires générales ($k$ vs $k+1$), le rapport est exprimé comme une espérance conditionnelle d'une fonction de score, ce qui permet de linéariser le problème.

2. Linéarisation de l'espérance conditionnelle :

   • Un théorème central (Théorème 4.1) démontre que l'espérance conditionnelle peut être linéarisée avec un reste explicite sur un ensemble typique (typical set).
   • Cette preuve repose sur un lemme de rapport Edgeworth pour les sommes de vecteurs un-hot sur un réseau (lattice), permettant de contrôler les erreurs d'approximation locale.

3. Correction de la Covariance (Point Crucial) :

   • L'article identifie et corrige une erreur fondamentale : pour des compositions proportionnelles ($k/n \to \pi$), la covariance par utilisateur n'est pas celle du mélange i.i.d. ($\Sigma_{mix}$), mais la covariance de composition fixe :
     $$\Sigma_\pi = (1-\pi)\Sigma_0 + \pi\Sigma_1$$
   • La différence est un terme de rang un $\pi(1-\pi)vv^\top$ qui, s'il est ignoré, conduit à une constante de Fisher surestimée et donc à une confidentialité trop optimiste.

4. Approximation Gaussienne et LAN :

   • Utilisation du théorème de Berry-Esseen pour établir la convergence vers une loi normale.
   • Démonstration de la Normalité Asymptotique Locale (LAN) pour le modèle de mélange, établissant l'équivalence de Le Cam avec un décalage gaussien.

3. Contributions Clés et Résultats

A. Constantes Universelles et Divergences

• Constante de Fisher Correcte : L'article définit la constante de Fisher $I_\pi = v^\top \Sigma_\pi^+ v$ (où $v = W_1 - W_0$ et $\Sigma_\pi^+$ est la pseudo-inverse de Moore-Penrose).
• Expansion Sharp de la Divergence de Jensen-Shannon (JSD) :
  • Pour la paire canonique ($k=0$) : $JSD = \frac{\chi^2}{8n} - \frac{\mu_3}{16n^2} + O(n^{-3})$.
  • Pour les compositions proportionnelles ($k/n \to \pi$) : $JSD = \frac{I_\pi}{8n} + O(n^{-2})$.
  • Le terme dominant $\frac{I_\pi}{8n}$ est universel pour toutes les f-divergences lisses.

B. Équivalence à la Confidentialité Différentielle Gaussienne (GDP)

• L'article prouve que le rapport de vraisemblance normalisé converge vers une loi normale sous les deux hypothèses (null et alternative).
• Résultat : Le modèle de mélange est asymptotiquement équivalent à un test de décalage gaussien $G_{\mu_n}$ avec un paramètre $\mu_n = \sqrt{I_\pi/n}$.
• Courbe de Confidentialité : Cela permet de dériver la courbe de confidentialité limite complète $(\varepsilon, \delta)$ via la fonction de trade-off gaussienne, avec une erreur de contrôle $O(n^{-1/2})$.

C. Mélage Multi-Message (Unbundled vs Bundled)

• L'auteur analyse le cas où chaque utilisateur envoie $m$ messages indépendants (unbundled).
• Comparaison Quantitative : Le modèle "unbundled" offre une confidentialité strictement meilleure que le modèle "bundled" (où les $m$ messages sont traités comme un seul vecteur) pour $m \ge 2$.
• Le paramètre GDP pour le modèle unbundled est $\mu_{unb} = \sqrt{m I_\pi / n}$, tandis que le modèle bundled suit une loi multiplicative du $\chi^2$ qui est moins efficace.

D. Résultats aux Limites et Applications

• Randomized Response (RR) : Une analyse fine de la frontière du régime gaussien (quand le paramètre de confidentialité locale $\varepsilon_0$ croît avec $n$) montre une dégradation de la vitesse de convergence de Berry-Esseen en $\sqrt{a_n}$ (où $a_n = e^{\varepsilon_0}/n$).
• Estimation de Fréquence : L'article montre comment utiliser ces résultats exacts pour calibrer le bruit dans l'estimation de fréquence, obtenant une précision supérieure aux bornes d'amplification conservatrices.

4. Signification et Impact

Cet article représente une avancée majeure dans la théorie de la confidentialité différentielle pour plusieurs raisons :

1. Précision Théorique : Il passe des bornes d'ordre de grandeur ($O(\cdot)$) à des expansions asymptotiques précises avec des constantes explicites et des termes d'erreur contrôlés.
2. Correction d'Erreur Systématique : La mise en évidence de la covariance de composition fixe $\Sigma_\pi$ corrige des erreurs potentielles dans l'évaluation de la confidentialité dans de nombreux protocoles existants, évitant ainsi une surestimation de la protection.
3. Outils Pratiques : La dérivation de courbes $(\varepsilon, \delta)$ exactes et de formules binomiales pour les canaux à sortie binaire permet aux ingénieurs de calibrer les systèmes de manière optimale, réduisant le bruit ajouté sans compromettre la sécurité.
4. Unification : Le cadre unifie l'analyse des divergences (JSD, Rényi), de la confidentialité différentielle (GDP, $(\varepsilon, \delta)$) et de la théorie des expériences (LAN, Le Cam) sous un seul régime gaussien universel.

En résumé, ce travail fournit la "boîte à outils" mathématique définitive pour analyser la confidentialité dans le régime gaussien du modèle de mélange, en offrant des garanties rigoureuses et des constantes optimales pour la conception de protocoles.