Decomposition-Based Optimal Bounds for Privacy Amplification via Shuffling

Shuffling has been shown to amplify differential privacy guarantees, enabling a more favorable privacy-utility trade-off. To characterize and compute this amplification, two fundamental analytical frameworks have been proposed: the privacy blanket by Balle et al. (CRYPTO 2019) and the clone--including both the standard and stronger variant--by Feldman et al. (FOCS 2021, SODA 2023). These frameworks share a common foundation: decomposing local randomizers into structured components for analysis. In this work, we introduce a unified analytical framework--the general clone paradigm--which subsumes all possible decompositions, with the clone and blanket decompositions arising as special cases. Within this framework, we identify the optimal decomposition, which is precisely the one used by the privacy blanket. Moreover, we develop a simple and efficient algorithm based on the Fast Fourier Transform (FFT) to compute optimal privacy amplification bounds. Experimental results show that our computed upper bounds nearly match the lower bounds, demonstrating the tightness of our method. Building on this method, we also derive optimal amplification bounds for both joint and parallel compositions of LDP mechanisms in the shuffle model.