# Shuffle Model of Differential Privacy: Numerical Composition for Federated Learning
## 6 Privacy Loss Distribution of Generalized Dominating Pairs  
**Generalized dominating pair for shuffle protocols. ** To cover the more general case and derive numerical composition bounds for various shuffle protocols (e.g., for both single-message and multi-message protocols), the aim of this work is to numerically derive the DP guarantee of the following \(K\)-wise composition of the dominating pair as follows:  
\[(P_{1},\ldots,P_{K}\|Q_{1},\ldots,Q_{K}),\]  
where \(P_{k}=P_{p^{(k)},p^{(k)}}^{q^{(k)},p^{(k)}}\) and \(Q_{k}=Q_{p^{(k)},p^{(k)}}^{q^{(k)},p^{(k)}}\) is the binomial variable defined as in Lemma 4 (and also in Theorem 1) with possibly heterogeneous parameters \(p^{(k)}>0\), \(\beta^{(k)}\leq(p^{(k)}-1)/(p^{(k)}+1)\), \(n^{(k)}\in\mathbb{Z}^{+}\), and \(q^{(k)}\geq 1\). Following the privacy composition methods in [13; 27], the privacy loss distribution (PLD) represents the distribution of the logarithm of probability ratios between a dominating pair of distributions. By constructing the PLD, we can use Fast Fourier Transform (FFT) to compose privacy losses and derive the overall privacy consumption. To approximate the PLD for each round's shuffle protocol, we consider the generalized binomial counts that tightly dominate many shuffle protocols: \(P_{p,\beta}^{q,n},Q_{p,\beta}^{q,n}\), defined as  
\[P_{p,\beta}^{q,n}=(A+\Delta_{1},\,C-A+\Delta_{2}),\,Q_{p,\beta}^{q,n}=(A+\Delta _{2},\,C-A+\Delta_{1}),\]  
where  
* \(C\sim\text{Binomial}(n-1,\frac{2\beta p}{(p-1)q})\),
* \(A\sim\text{Binomial}\Big{(}C,\frac{1}{2}\Big{)}\),
* \(\Delta_{1}\sim\text{Bernoulli}\Big{(}\frac{\beta p}{p-1}\Big{)}\),
* \(\Delta_{2}\sim\text{Binomial}\Big{(}1-\Delta_{1},\frac{\beta}{p-1-\beta p} \Big{)}\). Here, \(C\) represents the number of other users whose outputs are indistinguishable \"clones\" of the two users, and \(A\) denotes the random split between these clones. **The formula of probabilities and their ratios. ** The PLD measures the distribution of probability ratios. To analyze the probability ratios, we first consider \(P=(A,C-A)\), \(P_{0}=(A+1,C-A)\) and \(P_{1}=(A,C-A+1)\). Let \(s=\frac{2\beta p}{(p-1)q}\), then based on the above sampling process, we have:  
\[ \begin{split}\frac{\mathbb{P}[P_{1}=(a,b)]}{\mathbb{P}[P_{0}=(a,b)]}&=\frac{\binom{n-1}{a+b-1}s^{a+b-1}(1-s)^{n-a-b}\binom{a+b-1} {a}(1/2)^{a+b-1}}{\binom{n-1}{a+b-1}s^{a+b-1}(1-s)^{n-a-b}\binom{a+b-1}{a-1}(1 /2)^{a+b-1}}\\ &=\frac{b}{a},\end{split} \]\[\frac{\mathbb{P}[P=(a,b)]}{\mathbb{P}[P_{0}=(a,b)]} = \frac{(^{n-1}_{a+b})^{g+b}(1-s)^{n-a-b-1}(^{a+b}_{a})(1/2)^{a+b}}{ \binom{n-1}{a+b-1}^{n-1}s^{a+b-1}(1-s)^{n-a-b}(^{a+b-1}_{a-1})(1/2)^{a+b-1}}\] \[= \frac{n-a-b}{2a}\cdot\frac{s}{1-s},\]  
Now let \(\alpha=\beta/(p-1)\), then the ratio of probabilities on point \((a,b)\in[0,n]^{2}\) (with \(a+b\leq n\)) is given by:  
\[\frac{\mathbb{P}[P^{\prime,n}_{p,\beta}=(a,b)]}{\mathbb{P}[Q^{ \prime,n}_{p,\beta}=(a,b)]} \tag{4}\] \[= \frac{pa\mathbb{P}[P_{0}=(a,b)]+\alpha\mathbb{P}[P_{1}=(a,b)]+(1- \alpha(p+1))\mathbb{P}[P=(a,b)]}{\alpha\mathbb{P}[P_{0}=(a,b)]+p\alpha\mathbb{ P}[P_{1}=(a,b)]+(1-\alpha(p+1))\mathbb{P}[P=(a,b)]}\] (5) \[= \frac{2p\alpha\cdot a+2\alpha\cdot b+(1-\alpha(p+1))(n-a-b) \cdot s/(1-s)}{2\alpha\cdot a+2p\alpha\cdot b+(1-\alpha(p+1))(n-a-b)\cdot s/ (1-s)}, \tag{6}\]  
We denote this probability ratio as \(R_{a,b}\). Due to symmetry, the PLDs of \(P^{\prime,n}_{p,\beta}\), \(Q^{\prime,n}_{p,\beta}\) and \(Q^{\prime,n}_{p,\beta}\), \(P^{\prime,n}_{p,\beta}\) (e.g., these from Lemma 4 or Theorem 1) are the same. Computing the PLD directly involves iterating over a two-dimensional domain of size \(\Omega(n^{2})\), which is impractical for large \(n\). Following the approach in [13], we use [PERSON]'s tail bounds for the binomial distributions to limit our computation to regions where the probability mass is significant, neglecting negligible probabilities and adding their total mass to \(\omega_{P/Q}(\log p)\) or \(\omega_{P/Q}(\infty)\).