# Shuffle Model of Differential Privacy: Numerical Composition for Federated Learning
## 1 Introduction  
Federated analytics and federated learning leverage data from multiple sources (e.g., individuals and organizations) to empower data mining and learning applications. They do not access the raw data to alleviate privacy concerns, allowing participants to contribute only summary statistics or intermediate information (e.g., gradient vectors). However, recent studies have demonstrated that summary statistics might still reveal sensitive attributes [1], and that the intermediate gradient vectors can be used to reconstruct raw data with high precision [2]. As a countermeasure, it is necessary to incorporate federated analytics and learning with theoretically rigorous notions of privacy protection (e.g., the de facto standard of differential privacy [3]). In federated settings, the shuffle model has emerged as one of the most appealing paradigms of differential privacy, showing excellent privacy-utility-complexity trade-offs and attracting much attention from both academia and industry [4, 5]. In the shuffle model, messages from users are first randomized locally, then anonymized and permuted by a shuffler, which can be implemented by anonymous channels, edge servers, or a set of non-colluding assisting parties. Since the server or statistician only observes shuffled messages, participants benefit from _privacy amplification via shuffling_[6]. That is, although themessages from each participant have low privacy protection (with little randomization noise), anonymously hiding among shuffled messages ensures stronger privacy protection. For example, shuffled \(\epsilon_{0}\)-LDP messages from \(n\) users satisfy \((O(\sqrt{\exp(\epsilon_{0})\log(1/\delta)/n}),\delta)\)-DP [7]. Much effort has been devoted to one-round privacy amplification analyses in the shuffle model (e.g., [6; 7; 8; 9]), which is a key ingredient for achieving excellent privacy-utility-complexity trade-offs in one-time data queries (e.g., distribution estimation and numerical value summation). Meanwhile, in federated analytics and learning tasks, there are normally multiple queries, and many depend on previous querying results, such as in frequent itemset mining, decision trees, and federated deep learning. It is urgent to derive tight sequential composition in the shuffle model (to obtain desirable privacy-utility trade-offs), but this can be challenging as the noise distributions involved can be sophisticated. The work of [10] resorts to Renyi differential privacy to approximate the Renyi divergence bound in the shuffle model with LDP messages. However, Renyi DP itself may not be tight under composition [11], and the Renyi divergence bound is overestimated for the noise distributions in shuffle protocols. A more recent work directly numerically analyzes the approximate privacy loss distribution of the shuffled LDP messages and derives tighter composition bounds via Fourier analysis, based on the clone reduction [8] of LDP messages. Nevertheless, their analysis is restricted to the single-message shuffle protocols (i.e., shuffled LDP messages), which suffer utility limitations compared to the more general multi-message protocols [12]. Furthermore, their analysis is not tight for prevalent local randomizers (e.g., vector randomized response), as their one-round reduction is not tight for them. In this work, we aim to numerically deduce tight sequential composition for both single-message and multi-message shuffle protocols. To this end, we first derive a tight total variation bound and reduce the privacy loss into parameterized binomial counts for the vector randomized response, which is prevalent in SOTA base shuffle protocols for numerical summation. For generalized and possibly heterogeneous binomial counts reductions that arise in multi-round single-message/multi-message protocols, we then derive the approximate privacy loss distribution (PLD) for them and employ Fourier composition on the PLDs from multiple rounds.