# Shuffle Model of Differential Privacy: Numerical Composition for Federated Learning
## 3 Preliminaries
### The Shuffle Model of Differential Privacy  
Following conventions in the shuffle model based on randomize-then-shuffle [20; 22], we define a shuffle protocol \(\mathcal{P}\) to be a list of algorithms \(\mathcal{P}=(\{\mathcal{R}_{i}\}_{i\in[n]},\mathcal{A})\), where \(\mathcal{R}_{i}:\mathbb{X}\to\mathbb{Y}^{*}\) is the local randomizer of user \(i\), and \(\mathcal{A}:\mathbb{Y}^{*}\to\mathbb{Z}\) the analyzer in the data collector's side. In a single-message shuffle protocol, each \(\mathcal{R}_{i}\) produces one message; in a multi-message protocol, the randomizer might produce multiple messages each over domain \(\mathbb{Y}\). The overall protocol implements a mechanism \(\mathcal{P}:\mathbb{X}^{n}\to\mathbb{Z}\) as follows. Each user \(i\) holds a data record \(x_{i}\) and a local randomizer \(\mathcal{R}_{i}\), then computes message(s) \(y_{i}=\mathcal{R}_{i}(x_{i})\). The messages \(y_{1}\cup\cdots\cup y_{n}\) are then shuffled and submitted to the analyzer. We write \(\mathcal{S}(y_{1}\cup\cdots\cup y_{n})\) to denote the random shuffling step, where \(\mathcal{S}:\mathbb{Y}^{*}\to\mathbb{Y}^{*}\) is a _shuffler_ that applies a uniform-random permutation to its inputs. In summary, the output of \(\mathcal{P}(x_{1},\ldots,x_{n})\) is denoted by \(\mathcal{A}\circ\mathcal{S}\circ\mathcal{R}_{[n]}(X)=\mathcal{A}(\mathcal{S} (\mathcal{R}_{1}(x_{1})\cup\cdots\cup\mathcal{R}_{n}(x_{n})))\). **Security model. ** The shuffle model assumes that all parties involved in the protocol follow it faithfully and there is no collusion between them. From a privacy perspective, the goal is to ensure the differential privacy of the output \(\mathcal{P}(x_{1},\ldots,x_{n})\) for any analyzer \(\mathcal{A}\). By leveraging the post-processing property of the Hockey-stick divergence, it suffices to ensure that the shuffled messages \(\mathcal{S}\circ\mathcal{R}_{[n]}(X)=\mathcal{S}(\mathcal{R}_{1}(x_{1})\cup \cdots\cup\mathcal{R}_{n}(x_{n}))\) are differentially private. In the context of multi-round federated machine learning, we consider a stronger adversarial model. Specifically: (1) _Adversary capabilities_: The server is considered as an active adversary that can strategically specify the current model parameters or contaminatethe aggregated gradient. It can also eavesdrop on shuffled messages and observe outputs. However, direct linking of queries to users remains infeasible due to the anonymization provided by the shuffle protocol. (2) _Available information to attackers_: The adversary has access to all shuffled messages in each round and knows the number of participants. However, it cannot access the raw data of individual users. (3) _Defended attack vectors_: The protocol defends against linkability attacks, correlation between queries, and inference of individual user data through repeated interactions. These protections are achieved through differential privacy mechanisms and the anonymization properties of the shuffle protocol. We formally define differential privacy in the shuffle model in Definition 5. **Definition 5** (Differential privacy in the shuffle model). : _A protocol \(\mathcal{P}=(\left\{\mathcal{R}_{i}\right\}_{i\in[n]},\mathcal{A})\) satisfies \((\epsilon,\delta)\)-differential privacy in the shuffle model iff for all neighboring datasets \(X,X^{\prime}\in\mathbb{X}^{n}\), the \(\mathcal{S}\circ\mathcal{R}_{[n]}(X)\) and \(\mathcal{S}\circ\mathcal{R}_{[n]}(X^{\prime})\) are \((\epsilon,\delta)\)-indistinguishable._  
**Anonymization intermediary in practice. ** The privacy amplification guarantee in the shuffle model fundamentally relies on the shuffler's capability to execute independent operations without collusion with the analysis server--a persistent challenge in practical implementations. Existing solutions address this through distinct architectural paradigms: [23] implements basic shuffling via Tor's low-latency anonymous channels, while the ESA framework [24] achieves enterprise-grade efficiency through SGX-enabled oblivious shuffling with verifiable isolation.