# Shuffle Model of Differential Privacy: Numerical Composition for Federated Learning
## 5 A Tight Characterization of Vector Randomized Response
**Theorem 1** (Reduction of Shuffled Sampled Vector Randomized Response Messages). : _Given a \(d\)-dimension binary vector input domain \(\{0,1\}^{d}\), define a randomized response mechanism \(\mathcal{R}\) that outputs \(s\) dimensions \(S\subseteq[d]\) with some probability distribution \(p_{S}\in\Delta_{[d]^{s}}\), and for each dimension \(j\in[S]\), outputs the input \(x_{i,j}\in\{0,1\}\) with probability \(r\) (with \(r\geq 0.5\)), otherwise outputs \(1-x_{i,j}\). Then, for all possible \(X=\{x_{1}^{0},x_{2}\ldots,x_{n}\},X^{\prime}=\{x_{1}^{1},x_{2}\ldots,x_{n}\} \in\{0,1\}^{d\times n}\) and any measurement \(D\) satisfying the data-processing inequality:_  
\[D(\mathcal{S}(\mathcal{R}(x_{1}^{0}),\mathcal{R}(x_{2}),\ldots, \mathcal{R}(x_{n}))\|\mathcal{S}(\mathcal{R}(x_{1}^{1}),\mathcal{R}(x_{2}), \ldots,\mathcal{R}(x_{n})))\] \[\leq D(P_{p,\beta}^{l,n}\|Q_{p,\beta}^{l,n}),\]  
_with \(p=\frac{r^{s}}{(1-r)^{s}}\), \(q=p\), and \(\beta=(1-r)^{s}\sum_{k=\left\lfloor\frac{s}{2}\right\rfloor+1}^{s}\binom{s}{ k}\Big{(}(r/(1-r))^{k}-(r/(1-r))^{s-k}\Big{)}\)._  
Proof. : Recall that the randomizer outputs selected dimensions \(S\subseteq[d]\) and sanitized binary values on these dimensions. We denote the output as \(\mathcal{R}(x_{i})=(S,\{\mathsf{RR}(x_{i,j})\}_{j\in S})\), where \(\mathsf{RR}\) denotes the base randomized response randomizer that flips \(x_{i,j}\) with probability \(1-r\). Since the dimensions are selected using a public distribution \(p_{S}\) (and are uncorrelated with the input's value), it is obvious that \(\mathcal{R}\) satisfies \(s\cdot\log(\frac{r}{1-r})\)-LDP; thus, the \(p\) and \(q\) parameter are bounded by \(\frac{r^{s}}{(1-r)^{s}}\). As for the total variation parameter \(\beta\), we firstly consider a fixed value of \(S\). For any possible \(x_{1}^{0},x_{1}^{0}\in\{0,1\}^{d}\), the total variation \(D_{1}(\{\mathsf{RR}(x_{1,j}^{0})\}_{j\in S}\|\{\mathsf{RR}(x_{1,j}^{1})\}_{j\in S})\) is maximized when \(x_{1}^{0}\) and \(x_{1}^{1}\) differ at every bit on dimensions \(S\). Without loss of generality, we assume \(x_{1}^{0}\) take values of \(0\)s on these dimensions, and \(x_{1}^{1}\) take values of \(1\)s on these dimensions. Then, for a output value \(t\in\{0,1\}^{s}\) of \(\{\mathsf{RR}(x_{i,j})\}_{j\in S}\), if \(t\) have more zeros than ones, \(\mathbb{P}[\{\mathsf{RR}(x_{1,j}^{0})\}_{j\in S}=t]\geq\mathbb{P}[\{\mathsf{ RR}(x_{1,j}^{1})\}_{j\in S}=t]\). Let \(k\) denote the number of zeros in \(t\), we have:  
\[D_{1}(\{\mathsf{RR}(x_{1,j}^{0})\}_{j\in S}\|\{\mathsf{RR}(x_{1,j}^{1})\}_{j\in S})\] \[\leq \sum_{t\in[0,1]^{s}}\max\Bigl{\{}0,\mathbb{P}[\{\mathsf{RR}(x_{1,j}^{0})\}_{j\in S}=t]-\mathbb{P}[\{\mathsf{RR}(x_{1,j}^{1})\}_{j\in S}=t] \Bigr{\}}\] \[\leq (1-r)^{s}\sum_{k=\left\lfloor\frac{s}{2}\right\rfloor+1}^{s} \binom{s}{k}\Big{(}(r/(1-r))^{k}-(r/(1-r))^{s-k}\Big{)}.\]  
Now enumerating all possible \(S\), we have the total variation bound as:\[ \begin{split}&\quad D_{1}(\mathcal{R}(x_{1}^{0})\|\mathcal{R}(x_{1}^{1})) \\ \leq&\sum_{S\in[d]^{s}}p_{S}(S)\cdot D_{1}(\{\text{ RR}(x_{1,j}^{0})\}_{j\in S}\|\{\text{RR}(x_{1,j}^{1})\}_{j\in S})\\ \leq&(1-r)^{s}\sum_{k=\left\lfloor\frac{s}{2}\right\rfloor+ 1}^{s}\binom{s}{k}\Big{(}(r/(1-r))^{k}-(r/(1-r))^{s-k}\Big{)}.\end{split} \]  
Finally, utilizing the variation-ratio reduction in Lemma 4, we have the conclusion.