# Privacy Amplification via Shuffling: Unified, Simplified, and Tightened

arXiv: https://arxiv.org/abs/2304.05007 · HTML: https://mlsanity.com/paper/2304.05007/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2023.

## Built on by (most cited first, 4 of 4)

- [P2NIA: Privacy-Preserving Non-Iterative Auditing](https://mlsanity.com/paper/2504.00874/) (2025)
- [Beyond Statistical Estimation: Differentially Private Individual Computation via Shuffling](https://mlsanity.com/paper/2406.18145/) (2024)
- [Analysis of Shuffling Beyond Pure Local Differential Privacy](https://mlsanity.com/paper/2601.19154/) (2026)
- [Dithered Gaussian Mechanism for Randomness-Efficient Differential Privacy](https://mlsanity.com/paper/2607.06320/) (2026)

## Abstract (arXiv)

The shuffle model of differential privacy provides promising privacy-utility balances in decentralized, privacy-preserving data analysis. However, the current analyses of privacy amplification via shuffling lack both tightness and generality. To address this issue, we propose the variation-ratio reduction as a comprehensive framework for privacy amplification in both single-message and multi-message shuffle protocols. It leverages two new parameterizations: the total variation bounds of local messages and the probability ratio bounds of blanket messages, to determine indistinguishability levels. Our theoretical results demonstrate that our framework provides tighter bounds, especially for local randomizers with extremal probability design, where our bounds are exactly tight. Additionally, variation-ratio reduction complements parallel composition in the shuffle model, yielding enhanced privacy accounting for popular sampling-based randomizers employed in statistical queries (e.g., range queries, marginal queries, and frequent itemset mining). Empirical findings demonstrate that our numerical amplification bounds surpass existing ones, conserving up to 30% of the budget for single-message protocols, 75% for multi-message ones, and a striking 75%-95% for parallel composition. Our bounds also result in a remarkably efficient tildeO(n) algorithm that numerically amplifies privacy in less than 10 seconds for n=108 users.