# Shuffle Model of Differential Privacy: Numerical Composition for Federated Learning
## 4 Problem Formulation  
Considering \(K\) sequential (and possibly adaptive) queries over a dataset \(X\in\mathbb{X}^{n}\) in the shuffle model, there are \(K\) rounds of randomization and shuffling, and the shuffling is independent across rounds. Figure 1 provides a detailed visual representation of the K-round shuffle model, highlighting the flow from user input to local randomizers, through shufflers, and finally to the cumulative outputs across K rounds. This complements the mathematical framework described below. Let \(\mathcal{R}^{k}_{[n]}=\{\mathcal{R}^{k}_{1},\ldots,\mathcal{R}^{k}_{n}\}\) denote the local randomizers used in the \(k\)-th round, where \(\mathcal{R}^{k}_{i}:\mathbb{X}\times\mathbb{Y}^{n\times(k-1)}\mapsto\mathbb{Y}\) takes the data \(x_{i}\) and the outputs of the previous \((k-1)\) rounds \(\{\mathcal{S}\circ\mathcal{R}^{k}_{[n]}(X)\}_{k^{\prime}\in[k-1]}\) as input. We use \(\mathcal{S}\circ\mathcal{R}^{k}_{[n]}(X)\) to denote the query result of the \(k\)-th round and \(\mathcal{S}\circ\mathcal{R}^{[k]}_{[n]}(X)\) to denote the outputs during \(1\) to \(k\) rounds:  
\[\{\mathcal{S}\circ\mathcal{R}^{1}_{[n]}(X),\ldots,\mathcal{S}\circ\mathcal{R} ^{k}_{[n]}(X)\}.\]  
Assuming that the dominating pair of the \(k\)-th round is \((P_{k},Q_{k})\), that is,  
\[D(\mathcal{S}\circ\mathcal{R}^{[k]}_{[n]}(X)\|\mathcal{S}\circ\mathcal{R}^{[ k]}_{[n]}(X^{\prime}))\leq D(P_{k}\|Q_{k})\]  
holds for any neighboring datasets \(X,X^{\prime}\in\mathbb{X}^{n}\) and for any distance measure \(D\) that satisfy the data processing inequality. Then, using the following lemma from [11] (Theorem 10) and [13] (Corollary 8), we can conclude that the divergence of \(K\)-wise sequential composition, \(D(\mathcal{S}\circ\mathcal{R}^{[K]}_{[n]}(X)\|\mathcal{S}\circ\mathcal{R}^{[ K]}_{[n]}(X^{\prime}))\), is dominated by  
\[D(P_{1},\ldots,P_{K}\|Q_{1},\ldots,Q_{K}).\]  
For simplicity, we use \(P_{[K]}\) to denote variables \(P_{1},\ldots,P_{K}\), and \(Q_{[K]}\) to denote variables \(Q_{1},\ldots,Q_{K}\).  
**Lemma 3** (Reduction of sequential composition [13]).: _Given any distance measure \(D\) that satisfies the data processing inequality, if \(D(\mathcal{S}\circ\mathcal{R}^{k}_{[n]}(X)\|\mathcal{S}\circ\mathcal{R}^{k}_{ [n]}(X^{\prime}))\leq D(P_{k}\|Q_{k})\) holds for all \(k\in[K]\) and for all neighboring datasets \(X\) and \(X^{\prime}\), then_  
\[D(\mathcal{S}\circ\mathcal{R}^{[K]}_{[n]}(X)\parallel\mathcal{S} \circ\mathcal{R}^{[K]}_{[n]}(X^{\prime}))\leq D(P_{[K]}\|Q_{[K]}). \tag{3}\]  
**Goal of numerical composition of differential privacy for multi-message shuffle protocols.** We aim to upper-bound the overall differential privacy consumption of shuffle protocols with \(K\) sequential rounds, having broad applications to iterative gradient aggregation in federated learning and various data mining tasks (e.g., building decision tree/forest and a-priori-based frequent itemset mining that compose several sequentialsteps). Specifically, we analyze the divergence and indistinguishable level of the joint dominating pair:  
\[(P_{1},\ldots,P_{K}\|Q_{1},\ldots,Q_{K}).\]