Universal Shuffle Asymptotics: Sharp Privacy Analysis in the Gaussian Regime
This provides foundational theoretical guarantees for privacy amplification techniques in distributed systems, with applications to frequency estimation and differential privacy mechanisms.
The paper develops a sharp privacy theory for amplification by shuffling in the Gaussian regime, proving exact likelihood-ratio identities and deriving sharp Jensen-Shannon divergence expansions that identify a universal leading constant I_pi/(8n) for proportional compositions. It establishes equivalence to Gaussian Differential Privacy with Berry-Esseen bounds and obtains the full limiting (epsilon,delta) privacy curve.
We develop a sharp, experiment-level privacy theory for amplification by shuffling in the Gaussian regime: a fixed finite-output local randomizer with full support and neighboring binary datasets differing in one user. We first prove exact likelihood-ratio identities for shuffled histograms and a complete conditional-expectation linearization theorem with explicit typical-set remainders. We then derive sharp Jensen-Shannon divergence expansions, identifying the universal leading constant I_pi/(8n) for proportional compositions and emphasizing the correct fixed-composition covariance Sigma_pi=(1-pi)Sigma_0+pi*Sigma_1. Next we establish equivalence to Gaussian Differential Privacy with Berry-Esseen bounds and obtain the full limiting (epsilon,delta) privacy curve. Finally, for unbundled multi-message shuffling we give an exact degree-m likelihood ratio, asymptotic GDP formulas, and a strict bundled-versus-unbundled comparison. Further results include Local Asymptotic Normality with quantitative Le Cam equivalence, exact finite-n privacy curves, a boundary Berry-Esseen theorem for randomized response, and a frequency-estimation application.