# Shuffle Model of Differential Privacy: Numerical Composition for Federated Learning
## 5 A Tight Characterization of Vector Randomized Response  
In this work, we adopt variation-ratio reduction [9] for tightly characterizing a vector randomized response, a prevalent randomizer in shuffle protocols (e.g., in [15; 19]). Considering two neighboring datasets \(X\) and \(X^{\prime}\) that differ only in the \(v\)-th user's data (i.e., \(X\sim_{v}X^{\prime}\), \(v\in[n]\), the \(v\)-th user is considered as the victim in DP), i.e., \(X=\{x_{1},\ldots,x_{v},\ldots,x_{n}\}\) and \(X^{\prime}=\{x_{1},\ldots,x^{\prime}_{v},\ldots,x_{n}\}\), where \(x_{1},\ldots,x_{v},x^{\prime}_{v},\ldots,x_{n}\in\mathbb{X}\). One can define the following properties on (independent) local randomizers \(\{R_{i}\}_{i\in[n]}\) with some parameters \(p>1\), \(\beta\in[0,\frac{p-1}{p+1}]\), and \(q\geq 1\):  
1. \((p,\beta)\)-_variation property_: we say that the \((p,\beta)\)-variation property holds if \(D_{p}(R_{v}(x_{v}))\|\)\(R_{v}(x^{\prime}_{v}))=0\) and \(D_{1}(R_{v}(x_{v})\|R_{v}(x^{\prime}_{v}))\leq\beta\) for all possible \(x_{v},x^{\prime}_{v}\in\mathbb{X}\). 2. \(q\)-_ratio property_: we say that the \(q\)-ratio property holds if \(D_{q}(R_{v}(x_{v})\|R_{i}(x_{i}))=0\) and \(D_{q}(R_{v}(x^{\prime}_{v})\|R_{i}(x_{i}))=0\) hold for all possible \(\{x_{i}\}_{i\in[n]\setminus\{v\}}\in\mathbb{X}^{n-1}\) and all \(\{R_{i}\}_{i\in[n]\setminus\{v\}}\). The parameter \(\beta\) represents the pairwise total variation bound of the randomizer \(R_{v}\), and implies that the randomizer \(R_{v}\) satisfies \((0,\beta)\)-LDP. Let \(\mathcal{R}_{[n]}(X)\) denote the sanitized messages of \(X\) by \(\{R_{i}\}_{i\in[n]}\), and the variation-ratio analyses [9] reduce the privacy amplification problem into a divergence bound between two binomial counts (see Lemma 4). **Lemma 4** (Variation-ratio reduction [9]). : _For \(p>1,\beta\in[0,\frac{p-1}{p+1}],q\geq 1\), let \(C\sim Binomial(n-1,\frac{2\beta p}{(p-1)q})\), \(A\sim Binomial(C,1/2)\) and \(\Delta_{1}\sim Bernoulli(\frac{\beta p}{p-1})\) and \(\Delta_{2}\sim Binomial(1-\Delta_{1},\frac{\beta}{p-1-\beta p})\); let \(p^{\alpha,n}_{p,\beta}\) denote \((A+\Delta_{1},C-A+\Delta_{2})\) and \(Q^{\alpha,n}_{p,\beta}\) denote \((A+\Delta_{2},C-A+\Delta_{1})\). If randomizers \(\{R_{i}\}_{i\in[n]}\) satisfy the \((p,\beta)\)-variation property and the \(q\)-ratio property for all possible \(X,X^{\prime}\in\mathbb{X}^{n}\) that \(X\sim_{v}X^{\prime}\) (\(v\in[n]\)), then for any measurement \(D\) satisfying the data-processing inequality:_  
\[D(\mathcal{S}\circ\mathcal{R}_{[n]}(X)\|\mathcal{S}\circ\mathcal{R}_{[n]}(X^{ \prime}))\leq D(p^{\alpha,n}_{p,\beta}\|Q^{\alpha,n}_{p,\beta}).\]  
Many prevalent multi-message shuffle protocols can be reduced to the dominating pair \((P^{\alpha,n}_{p,\beta}Q^{\alpha,n}_{p,\beta})\) with varying \(p,\beta,q,n\) parameters, including the optimal privacy-utility  
Figure 1: An overview of the K-round shuffle model, illustrating the randomization and shuffling process in the shuffle model. communication protocols of [19; 28] that are based on randomized response on each bit, the SOTA message-complexity-efficient frequency oracle of [14] based on binary vector randomized response, and the communication efficient frequency oracle of [16; 29]. In the protocol of [16; 29], the corresponding \(p,\beta,q,n\) parameters are obvious, and the variation-ratio reduction is essentially tight (i.e., there are neighboring datasets that reach the dominating pair). Meanwhile, in the vector-randomized-response-based numerical gradient summation protocol [19] designated for federated learning, computing the total variation bound parameter \(\beta\) is non-trivial. Specifically, the protocol first samples \(s\) dimensions from \(d\) dimensions and then sanitizes each dimension using a randomized response. Due to the vast applications of such vector randomized responses in shuffle protocols (also seen in the recursive protocol in [15]), we derive tight total variation bound and a dominating pair for them in Theorem 1.