Differentially Private Federated Learning: A Systematic Review

HFL refers to the FL scenarios where participants hold different samples while sharing the same feature space. The objective of HFL is to collaboratively train a global model $\mathbf{w}^{\star}$ with all clients, aiming to minimize the global objective function $F\left(\cdot\right)$, essentially seeking to find:

Here, $t\in[T]$ donates the communication rounds, $k\in[K]$ donates the clients, $L_{k}(\cdot)$ donates the loss function of client $k$, $\mathbf{w}^{k}_{t}$ signifies the model uploaded by client $k$ at round $t$, while $\mathbf{w}_{t}$ denotes the server aggregated model. The weights are defined as $p_{k}=\frac{|D_{k}|}{|D|}$, $\sum_{k=1}^{K}p_{k}=1$, $D_{k}$ represents the local dataset of client $k$, and $D$ is the union of $D_{k}$.

Compared to HFL which processes data from multiple clients sharing the same feature set, VFL trains a better predictor by combining all features from different clients. VFL assumes that the data is partitioned across feature space. The data vector $x_{i}\in\mathbb{R}^{1\times d}$ is distributed among $K$ participants $\{x_{i,k}\in\mathbb{R}^{1\times d_{k}}\}_{k=1}^{K}$ in $D=\{x_{i},y_{i}\}_{i=1}^{N}$, where $d_{k}$ is the feature dimension of the $k^{th}$ participant, $k\in[K-1]$, and the $K^{th}$ participant has the label information $y_{i}=y_{i,K}$ (Yang et al., 2019). The participant with the label, the $K^{th}$ participant, is referred to as the server, while the others are referred to as clients ⁷⁷7 Some articles refer to them as “active” and “passive” parties (Liu et al., 2024); however, to maintain consistency with HFL, we refer to them as the “server” and “clients” here.. Each client $k$ has a dataset $D_{k}\triangleq\{x_{i,k}\}_{i=1}^{N}$, and the server has a dataset $D_{K}\triangleq\{x_{i,K},y_{i,K}\}_{i=1}^{N}$.

The global model $\mathbf{w}$ decomposes into the client models $\mathbf{w}_{k}$, $k\in[K-1]$, and the server model $\mathbf{w}_{K}$. Each $\mathbf{w}_{k}$ accesses dataset $D_{k}$ for forward propagation to yield the result $h_{k}$, while $\mathbf{w}_{K}$ accesses $D_{K}$ for both forward and backward propagation. The objective of VFL is to collaboratively train a global model $\mathbf{w}^{\star}$ with all clients, aiming to minimize the global objective function $F\left(\cdot\right)$, essentially seeking to find:

where $L_{K}(\cdot)$ donates the loss function of the server.

TFL was proposed by Liu et al. (Liu et al., 2020c), it refers to the scenario in FL settings where there is limited or no overlap in the feature space or sample space between clients. In this scenario, there are often multiple source domain datasets $D_{k}\triangleq\left\{\left(x_{i,k},y_{i,k}\right)\right\}_{i=1}^{N_{k}},k\in[K-1]$, and a target domain dataset $D_{K}\triangleq\left\{x_{i,K}\right\}_{i=1}^{N_{K}}$. Here, $D_{k}$ and $D_{K}$ are held by different participants, with those holding the source domain datasets called clients and those holding the target domain dataset called the server. Under this setup, the goal is to enable multiple parties to jointly train a model that can generalize to the target domain dataset held by the server, without exposing data to each other. In most cases, there are often few or even no labels in target domain dataset, in which case it need to use the source domain datasets from each client to generate pseudo-labels for the target domain dataset firstly.

Differential privacy (Dwork et al., 2006) is a rigorous mathematical framework that formally defines data privacy, originally used for privacy protection techniques on data collection servers. It can resist differential attacks using statistical queries by adding an appropriate amount of noise to the output of statistical queries, making it almost impossible for adversaries to discern the statistical differences between two adjacent datasets. There is a trusted server in DP setting. It requires that a single entry in the input dataset must not lead to statistically significant changes in the output if differential privacy holds (Dwork et al., 2006, 2014). The formal definition of DP is presented as follows.

Here, $\epsilon>0$ controls the level of privacy guarantee in the worst case. The smaller $\epsilon$, the stronger the privacy level is. The factor $\delta\geq 0$ is the failure probability that the property does not hold. In practice, the value of $\delta$ should be negligible (Papernot et al., 2018), particularly less than $\frac{1}{|D|}$. When $\delta=0$, we can call $(\epsilon,\delta)$-DP as $\epsilon$-DP.

Some new definitions have been derived from DP and applied in federated learning. For example, (Ghazi et al., 2021) defines label differential privacy (label DP) as follows. It consider the situation where only labels are sensitive information that should be protected and is usually applied to differentially private vertical federated learning.

On the other hand, Bayesian Differential Privacy (BDP) (Triastcyn and Faltings, 2020) is interested in the change in the posterior distribution of the attacker after observing the private model, compared to the prior. The original definition of BDP is very similar to DP, except that BDP assumes that all samples in the dataset are drawn from the same distribution $p(x)$.

Subsequent research introduced the concept of local differential privacy (LDP) framework, which is more stringent compared to DP. The difference between LDP and DP is that LDP does not require truthful data collectors. Therefore, data perturbation’s function is transferred from data collectors to each user. Each user perturbs original data by privacy-preserving algorithms and then uploads the disturbance data to data collectors. The formal definition of LDP is presented as follows.

Just like the DP, $0\leq\delta\leq 1$ indicates the failure probability that the property does not hold, and it should be negligible. And when $\delta=0$, we can call $(\epsilon,\delta)$-LDP as $\epsilon$-LDP. The definition we provided here is the general version, but the vast majority of works based on LDP utilize the definition of $\epsilon$-LDP.

From Definition 2.4, it can be seen that LDP ensures that algorithm $\mathcal{R}$ satisfies $(\epsilon,\delta)$-LDP by controlling the similarity of any two records’ output. In short, according to a certain output result of privacy algorithm $\mathcal{A}$, it is almost impossible to infer which record its input data is. In DP, its privacy algorithm $\mathcal{A}$ is defined by neighbor dataset, so it requires truthful third-party data collectors to protect data analysis results. We can see that the main difference between DP and LDP lies in the definition of neighboring datasets.

LDP requires that all pairs of sensitive data must satisfy the same $\epsilon$ privacy guarantee, which may hide too much information from the datasets, leading to insufficient utility for certain applications. Gursoy et al. (Gursoy et al., 2019) extended metric-based extensions of differetial privacy to LDP and proposed condensed LDP (CLDP) to improve the utility, which measures the level of privacy guarantee between any pair of sensitive data based on their distance.

In $\epsilon$-CLDP, the control of indistinguishability is influenced not only by $\epsilon$ but also by the input distance $d(\cdot,\cdot)$. Consequently, as $d$ increases, $\epsilon$ must decrease to maintain compensation.

In recent years, research has introduced the shuffle differential privacy model, built upon the foundation of LDP. It adds a trusted shuffler⁸⁸8Some researchers also assume the shuffler is semi-honest (Goldreich, 2009), where the cryptography-based protocol is required to perform a secure shuffle without accessing the values. Since there exist many secure shuffle protocols handling this case, we can simply assume it’s honest and pay attention on the part of DP. between the server and the clients, which shuffles the data items submitted by clients to achieve anonymization. In shuffle model, each client satisfies privacy guarantee of LDP when facing shuffler, and then achieves privacy guarantee of DP when facing the server since the shuffled data forms a dataset and generates the notion of neighborhood dataset.

The shuffle model originated from the framework of Encode, Shuffle, Analyze proposed by Bittau et al. (Bittau et al., 2017) and is formally defined by Cheu et al. (Cheu et al., 2019). Following these works, a protocol in the shuffle model consists of three components $\mathcal{P}={\mathcal{A}\circ\mathcal{S}\circ\mathcal{R}^{n}}$, aiming to achieve $(\epsilon_{c},\delta)$-DP. Here, $\mathcal{R}:\mathbb{X}\rightarrow\mathbb{Y}$ is a local randomizer executed on the client side, usually assumed to satisfy $\epsilon_{l}$-LDP. ${\mathcal{S}:\mathbb{Y}^{n}\to\mathbb{Y}^{n}}$ is a shuffler that applies a random permutation to its inputs, achieving anonymity. ${\mathcal{A}:\mathbb{Y}^{n}}\to\mathbb{Z}$ is the analyzer, aggregating the received values for statistics. According to the post-processing invariance, if the protocol $\mathcal{M}=\mathcal{S}\circ\mathcal{R}^{n}$ satisfies $(\epsilon_{c},\delta)$-DP, the whole protocol $P$ also satisfies $(\epsilon_{c},\delta)$-DP. Thanks to the anonymity brought by shuffling, each user’s privacy can be not only by their local randomization but also the randomness provided by other clients, leading to a smaller centralized privacy loss (i.e., $\epsilon_{c}$) compared to the used local privacy budget (i.e., $\epsilon_{l}$), just like the Figure 5 shown. In theory, we call this phenomenon privacy amplification, which leads to an around $O(\sqrt{n})$ more minor privacy loss $\epsilon_{c}$ (Balle et al., 2019; Erlingsson et al., 2019). This also reflects that to achieve a similar privacy level (corresponding to the same $\epsilon$), less noise is required for the local randomizer.

In this section, we will discuss the relationships and differences between the DP, LDP, and shuffle model.

DP and LDP. We can see that the main difference between DP and LDP lies in their definitions: DP relies on neighboring datasets as input, while LDP does not have the concept of neighboring datasets. Alternatively, from another perspective, when there is only one data sample, DP and LDP are equivalent. So, the LDP (definition  2.4) can be derived from the DP (definition 2.1) when the input $x$, $x^{\prime}$ are taken to be datasets of only one record. Since the size of local dataset is 1, $x$ and $x^{\prime}$ are neighbors for all $x,x^{\prime}\in\mathbb{X}$. Therefore LDP is a stronger condition as it requires the mechanism to satisfy DP for any two values of the domain of data $X$. As shown in Figure 2(a), LDP can compliant the DP, but the opposite doesn’t hold true (Paul and Mishra, 2020; Chen et al., 2023b).

Shuffle model, DP and LDP. The shuffle model encompasses both LDP and DP techniques and concepts. As shown in Figure 2(b), it begins with the definition of LDP, where each client satisfies $\epsilon_{l}$-LDP protection, and then sends to the server using the shuffle model. At this point, the shuffle model achieves anonymity of model parameters and forms a dataset, thereby generating the concept of neighborhood datasets. When facing the server, all uploaded model collections will be made to satisfy $(\epsilon_{c},\delta_{c})$-DP. As mentioned earlier, while LDP can compliant the DP, the shuffle model can achieve a tighter privacy budget bound in DP, meaning that $\epsilon_{c}\ll\epsilon_{l}$.

There are some basic properties that apply in both DP and LDP. The first one is post-processing, which means that any post-processing on the output of an $(\epsilon,\delta)$-DP algorithm will remain $(\epsilon,\delta)$-DP.

Form the Lemma 2.6, we can see that privacy cannot be weakened by any post-processing. For example in FL, we can let the gradients satisfy the $(\epsilon,\delta)$-DP firstly, and because the gradient decent is a post-processing operation, the model parameters also satisfy the $(\epsilon,\delta)$-DP. The second property is the parallel composition property, that divides the dataset into disjoint chunks, and a differential privacy mechanism is run separately on each chunk. Since these chunks are disjoint, each individual’s data appears in only one chunk. Therefore, even if the differential privacy mechanism is executed multiple times, it only runs once on the data of each individual.

In differentilly private HFL, the dataset held by each client can be considered as an independent disjoint dataset, making it compatible with the principle of parallel composition. In differentilly private TFL, dividing privacy data into disjoint teacher datasets, such that the aggregation complies with the principle of parallel composition, is also a common practice. The third property is the sequential composition property, which allows the combination of privacy budgets from multiple privacy algorithms to satisfy an overall privacy budget.

There are often multiple rounds of iteration required to obtain the model in differentilly private FL, where each iteration can be considered as a data access. By designing a differentially private algorithm $\mathcal{A}_{i,i\in[k]}$ that satisfies $(\epsilon,\delta)$-DP for the $k$ iteration, we can leverage the sequential composition theorem to compute the privacy budget $(k\epsilon,k\delta)$-DP for the entire process. But, this is not tight and we can use the advanced composition that could be improved to $(O(\sqrt{k\epsilon}),O(k\delta))$-DP (Dwork et al., 2010b).

More privacy loss composition mechanisms for DP. However, the number of iterations required for model convergence in differentilly private FL is often enormous. The advanced composition theorem no longer guarantees a more compact estimate of privacy loss, prompting the emergence of more compact measures for combining privacy loss, among which commonly used ones include Zero-Concentrated Differential Privacy (zCDP) (Bun and Steinke, 2016a), Moments Accountant (MA) (Abadi et al., 2016), Rényi Differential Privacy (RDP) (Mironov, 2017) and Gaussian Differential Privacy (GDP) (Dong et al., 2021). All these privacy composition measures mechanisms achieve a tighter analysis of cumulative privacy loss by leveraging the fact that the privacy loss random variable is strictly centered around the expected loss. It is important to note that these mechanisms are just different methods for analyzing privacy composition, and their purpose is to achieve a tighter analysis of the guaranteed privacy. And all these mechanisms can be converted to $(\epsilon,\delta)$-DP. This means that for a fixed privacy budget $(\epsilon,\delta)$, a relatively loose definition can be satisfied by adding relatively less noise, thus achieving less privacy for the same $(\epsilon,\delta)$ level. In practice, we often utilize these composition mechanisms to combine privacy losses and then convert them to $(\epsilon,\delta)$-DP for comparison.

The Moments Accountant (MA) technique (Abadi et al., 2016) used cumulative generating function (CGF) to characterize the privacy bounds of two privacy random distributions. The definition of CGF is as follows:

Based on CGF, the definition of privacy bounds for MA tracking is as follows:

Rényi divergence is another metric that measuring distinguishability of two random distributions, defined as follows:

Based on Rényi divergence, zCDP can be obtained as follows:

And the following Lemma 2.13 defines the standard form for converting $(\alpha,R)$-zCDP to ($\epsilon$, $\delta$)-DP.

Rényi differential privacy (RDP) is also based on the definition of Rényi divergence as follows:

And the following Lemma 2.15 defines the standard form for converting $(\alpha,R)$-RDP to ($\epsilon$, $\delta$)-DP.

Dong et al. (Dong et al., 2021) used hypothesis testing to quantify the distinguishability between $\mathcal{A}(D)$ and $\mathcal{A}(D^{\prime})$. They considerd a hypothesis problem $H_{0}:P\text{ v.s. }H_{1}:Q$ and a rejection rule $\phi\in[0,{1}]$. They defined the type I error as $\alpha_{\phi}=\mathbb{E}_{P}[\phi]$, which is the probability that rejecting the null hypothesis $H_{0}$ by mistake. And the type II error $\beta_{\phi}=1-\mathbb{E}_{Q}[\phi]$ is the probability that accepting the alternative $H_{1}$ wrongly. And the trade-off function aims to minimal type II error at level $\alpha$ of the type I error as follows.

Let $f$ be a trade-off function. Algorithm $\mathcal{A}$ is the $f$-differentially private if $T(\mathcal{A}(D),\mathcal{A}(D^{\prime}))\geq f$ for two neighboring datasets $D$ and $D^{\prime}$ (Dong et al., 2021). When the trade-off function is defined between two Gaussian distributions, can derive a subfamily of $f$-differential privacy guarantees called GDP as follows.

And the following Lemma 2.18 defines the standard form for converting $\mu$-GDP to ($\epsilon$, $\delta$)-DP.

Another popular property is subsampling, which achieves privacy amplification by running the differentially private algorithm on a subset of the privacy samples instead of all of them (Li et al., 2012). And the privacy amplification guarantee is different for different subsampling methods (Imola and Chaudhuri, 2021; Zhu and Wang, 2019).

In DP within FL, the Gaussian mechanism is most commonly used. Although the Laplace mechanism was originally defined within the context of DP, it is not widely utilized in this scenario. Subsequently, some discrete variants of the Gaussian mechanism have been widely applied in DP-FL, such as Discrete Gaussian and Skellam.

Gaussian Mechanism (Dwork et al., 2014) is the most popular mechanism for DP in FL. Assume $f:x\to\mathbb{X}$ be a function related to a query. For any $x\in\mathbb{X}$, this mechanism adds noise $n\sim\mathcal{N}(0,\sigma^{2})$ to the $f(x)$ to ensure $(\epsilon,\delta)$-DP. Here $\mathcal{N}(0,\sigma^{2})$ denotes the noise sample from the Gaussian (normal) distribution with mean $0$ and variance $\sigma^{2}$, where $\sigma^{2}=\frac{2\Delta f^{2}\log(1.25/\delta)}{\epsilon^{2}}$ and $\Delta f$ is the sensitivity of $f$.

More and more mechanisms are beginning to perform secure aggregation to satisfy differential privacy through encryption. The requirement for encryption to be performed over finite fields has led to the proposal of discrete noise mechanisms.

Discrete Gaussian Mechanism (Wang et al., 2020a) has been widely adopted for this purpose, operating by adding noise drawn from a Discrete Gaussian distribution. Assume $f:x\to\mathbb{X}$ be a function related to a query with sensitivity is 1. For any $x\in\mathbb{X}$, the Discrete Gaussian mechanism adds noise $N_{\mathbb{L}}(0,\sigma^{2})$ to the $f(x)$ to ensure $(\alpha,\alpha/(2\sigma^{2}))$-RDP. Here $N_{\mathbb{L}}(0,\sigma^{2})$ is Discrete Gaussian distribution with mean 0 and variance $\sigma^{2}$ as follows.

Skellam Mechanism (Agarwal et al., 2021) is a response to the issue of the Discrete Gaussian mechanism not being closed under summation. Let $\epsilon>0,\alpha>1$ and $f:x\to\mathbb{X}$ be a function related to a query. For any $x\in\mathbb{X}$, this mechanism adds noise $n\sim\mathrm{Sk}_{0,\mu}$ to $f(x)$ to satisfy $(\alpha,\frac{\alpha\Delta f^{2}}{2\mu}+\min\left(\frac{(2\alpha-1)\Delta f^{2}+6\Delta f}{4\mu^{2}},\frac{3\Delta f}{2\mu}\right))$-RDP. Here $\Delta f$ is the sensitivity of $f$ and $\mathrm{Sk}_{0,\mu}$ denotes sampling from the Skellam distribution with mean $0$ and variance $\mu$ as follows.

In addition to the above, there are Binomial Mechanism (Agarwal et al., 2021) and Poisson Binomial Mechanism (Chen et al., 2022b) also are discrete noise mechanisms for DP in FL, which we will not delve into here due to space constraints.

In LDP within FL, there are three fundamental mechanisms: Laplace Mechanism, Randomized Response (RR), and Exponential Mechanism (EM). The first two are typically used for value perturbation, with the former introducing unbounded noise and the latter bounded noise. The last one is commonly used for value selection, such as dimension selection in FL scenarios. We will first introduce these three basic mechanisms and then discuss some popular and advanced mechanisms built upon them.

Laplace Mechanism (Dwork et al., 2006) originates from data publication scenarios in DP, typically used for mean estimation. Given private data $x\in\mathbb{X}$, this mechanism adds noise $n\sim\text{Lap}(0,\frac{\Delta f}{\epsilon})$ to the aggregated value $f(x)$ of the private data, ensuring $\epsilon$-LDP. Here, $\Delta f$, referring to the $L_{1}$ sensitivity of $f$, is defined as $\Delta f=\max_{\|x-y\|_{1}=1}\|f(x)-f(y)\|_{1}$. In the FL scenario, $f(x)$ typically denotes the local FL model that outputs gradient updates.

Randomized Response (RR) (Warner, 1965) originates from data collection scenarios in LDP, typically used for count estimation of discrete values. This mechanism typically involves two steps: perturbation and calibration. In the perturbation step, each user perturbs their binary value $x\in\{0,1\}$ probabilistically according to Eq.(12), ensuring $\epsilon$-LDP. Assuming there are $n$ users’ perturbed data, in the aggregation step, the aggregator collects the perturbed count of 1 as $c$, and the actual count of 1 can be derived by calibration via $\hat{c}=\frac{c(e^{\epsilon}+1)-n}{e^{\epsilon}-1}$.

Exponential Mechanism (EM) (McSherry and Talwar, 2007) is used for discrete element selection. Given any utility function (also known as a scoring function), $u$, defined for each value, if the randomized algorithm $\mathcal{M}$ outputs result $r$ with a probability $\mathcal{M}_{E}(x,u,\mathcal{R})\sim\exp\left(\frac{\epsilon u(x,r)}{2\Delta u}\right)$, then $\mathcal{M}$ satisfies $\epsilon$-LDP.

In the context of mean estimation with continuous data during FL, except for the Laplace mechanism and RR, there are several advanced mechanisms.

Duchi’s Mechanism (Duchi et al., 2013) performs numeric mean estimation based on RR. Intuitively, it first randomly rounds the value $x\in[-1,1]$ to a discrete value $v\in\{-1,1\}$, then applies RR and calibrates it. Taken together, this mechanism perturbs $x\in[-1,1]$ to a value $\mathcal{R}_{Duchi}(x)\in\left\{\frac{e^{\epsilon}+1}{e^{\epsilon}-1},-\frac{e^{\epsilon}+1}{e^{\epsilon}-1}\right\}$ according to the probability defined in Eq.(13), where the output range of this mechanism is $\{-1,1\}$ times the calibration factor. The aggregator derives the mean by aggregating the sum of users’ perturbed values.

Harmony (Nguyên et al., 2016) based on Duchi’s mechanism, focuses on multi-dimensional vectors. For a bit vector with $d$ dimensions, each user samples only one bit to perturb with Duchi’s mechanism, replacing the output range from $\mathcal{R}_{Duchi}(x)\in\left\{\frac{e^{\epsilon}+1}{e^{\epsilon}-1},-\frac{e^{\epsilon}+1}{e^{\epsilon}-1}\right\}$ to $\mathcal{R}_{Duchi}(x)\in\left\{\frac{e^{\epsilon}+1}{e^{\epsilon}-1}\cdot d,-\frac{e^{\epsilon}+1}{e^{\epsilon}-1}\cdot d\right\}$.

Piecewise Mechanism (PM) (Wang et al., 2019b) combines the advantages of Laplace mechanism and Duchi’s mechanism by perturbing the private value $x$ to a range $[l(x),r(x)]$ with a larger probability. To ensure $\epsilon$-LDP, the range is defined as $l(x)=\frac{e^{\epsilon/2}\cdot x-1}{e^{\epsilon/2}-1}$ and $r(x)=\frac{e^{\epsilon/2}\cdot x+1}{e^{\epsilon/2}-1}$. The perturbation follows Eq.(14).

In the context of count estimation with discrete values, we list the advanced mechanisms as follows.

Generalized Randomized Response (GRR) (Wang et al., 2017) is an extension of traditional RR from binary values to discrete values in a domain of size $d$. Each user perturbs the value according to Eq.(15). The aggregator then calibrates the perturbed count $c_{x}$ of value $x$ as $\hat{c}_{x}=\frac{c_{x}(e^{\epsilon}+d-1)-n}{e^{\epsilon}-1}$.

RAPPOR (Erlingsson et al., 2014), also building on RR, incorporates a Bloom filter to facilitate discrete frequency estimation in large domains. Specifically, given a discrete domain $\{1,2,\ldots,d\}$, denoted as $[d]$, and $k$ hash functions $\mathbb{H}=\{H_{1},H_{2},\dots,H_{k}\}$ that map values from $[d]$ to $[k]$. Each user first uses these $k$ hash functions to map their value $v$ into the Bloom filter with $m$ bits and then perturbs each bit in the Bloom filter using RR. To reduce collisions, where two values are hashed to the same set of indices, RAPPOR allocates users into several cohorts, assigning a unique group of hash functions to each cohort. For longitudinal privacy, which protects against attacks during multiple accesses, RAPPOR splits $\epsilon$ into two parts: the first for permanent perturbation via RR and the second for instantaneous perturbation based on the permanent perturbation.

Under SL-DP, the data owner can be each local client. As shown in the Figure 3(a), each hospital participating in federated learning has a local database. For each client, the goal of SL-DP is to hide the presence of a single sample or record, or to be more specific, to bound the influence of any single sample or record on the learning outcome distribution (i.e. the distribution of the model parameters). It protects each local sample or record, so that the attackers could not identify one sample from the union of all local datasets.

Generally, at the SL-DP, we assume that the server is semi-honest (honest but curious). Therefore, each client cares about the privacy of their local dataset, and each client’s privacy budget is independent. The most mainstream approach to implementing SL-DP is to execute the Differentially Private Stochastic Gradient Descent (DPSGD) algorithm (Abadi et al., 2016) on each client ¹⁰¹⁰10If one wishes to define SL-DP under the aggregate samples held by all clients in FL, it requires the establishment of a secure third party. For example, Ruan et al. (Ruan et al., 2023) proposed a secure DPSGD algorithm by combining differential privacy and secure multiparty computation. They designed a secure inverse of square root method to securely clipping the gradient vectors and a secure Gaussian noise generation protocol. Their algorithm can efficiently perform DPSGD in ciphertext.. DPSGD is a widely-adopted training algorithm for deep neural networks with differential privacy guarantees. Specifically, in each iteration $t$, a batch of tuples $\mathcal{B}_{t}$ is sampled from $D$ with a fixed probability $\frac{b}{|D|}$, where $b$ is the batch size. After computing the gradient of each tuple $x_{i}\in\mathcal{B}_{t}$ as $g_{t}(x_{i})=\nabla_{\theta_{i}}L(\theta_{i},x_{i})$, where $\theta_{i}$ is model parameter for the i-th sample, DPSGD clips each per-sample gradient according to a fixed $\ell_{2}$ norm (Equation (16)).

In this way, for any two neighboring datasets, the sensitivity of the query $\sum_{i\in\mathcal{B}_{t}}g(x_{i})$ is bounded by $C$. Then, it adds Gaussian noise scaling with $C$ to the sum of the gradients when computing the batch-averaged gradients:

where $\sigma$ is the noise multiplier depending on the privacy budget. Last, the gradient descent is performed based on the batch-averaged gradients. Since initial models are randomly generated and independent of the sample data, and the batch-averaged gradients satisfy the differential privacy, the resulted models also satisfy the differential privacy due to the post-processing property. Many state-of-the-art variants of DPSGD (Fu et al., 2023; Wei et al., 2022; Papernot et al., 2021) can also be directly applied in the local client iterations to achieve more efficient model under SL-DP.

However, how to overcome the challenge of data heterogeneity of DP-FL is the concern of most of the work. Huang et al. (Huang et al., 2020) proposed differential privacy convolutional neural network with adaptive gradient descent algorithm (DPAGD-CNN) to update the training parameters of each client. They selected the best learning rate from a candidate set based on model evaluation in each round of local DPSGD. Noble et al. (Noble et al., 2022) introduced DP-SCAFFLOD, an extension of the SCAFFLOD algorithm (Karimireddy et al., 2020), which incorporates differential privacy. It employs a control variable to limit model drift during local DPSGD, aligning them more closely with the global model direction. And Using advanced results from DP theory and optimization to establish the convergence of DP-SCAFFLOD for convex and non-convex objectives. Wei et al. (Wei et al., 2021) found that there is an optimal number of communication rounds in terms of convergence performance for a given privacy budget $\epsilon$, which has motivated them to adaptively allocate privacy budgets in each round. Fu et al. (Fu et al., 2022a) proposed the Adap DP-FL algorithm, which includes adaptive gradient clipping and adaptive noise scale reduction methods. In the gradient clipping step of DPSGD, gradients are clipped using adaptive thresholds to account for the heterogeneity of gradient magnitudes across clients and training rounds. Additionally, during noise addition, the noise scale gradually decreases (or the privacy budget gradually increases) as gradients converge across training rounds. Yang et al. (Yang et al., 2023c) start from the Non-IID data itself, by concurrently updating local data transformation layers during local model training, thereby reducing the additional heterogeneity introduced by DP, and consequently improving the utility of FL models for Non-IID data. Their method was also applied to the CL-DP setting.

The allocation of privacy budget is also the focus of the study, as the privacy budget determines factors such as the number of iteration rounds and noise scale, it directly impacts the performance of the trained model. Ling et al. (Ling et al., 2023) investigated how to achieve better model performance under constraints of privacy budget and communication resources. They conducted convergence analysis of DP-HFL, derived the optimal number of local iterations before each aggregation. Liu et al. (Liu et al., 2021b) considered scenarios with heterogeneous privacy budgets and proposed the Projected Federated Averaging (PFA) algorithm. This algorithm utilizes the top singular subspace of model updates submitted by clients with higher privacy budgets to project them onto model updates from clients with lower privacy budgets. Furthermore, it reduces communication overhead by having clients with lower privacy budgets upload projected model updates instead of original model values. Zheng et al. (Zheng et al., 2021) integrated GDP privacy metric into DP-HFL, proposing a private federated learning framework called PriFedSync. While considering the cost of communication, Li et al. (Li et al., 2022c) proposed SoteriaFL, which is a unified framework for compressed private FL. They use shifted compression scheme (Horváth et al., 2023) to compress the perturbed parameters for efficient communication while maintaining high utility.

In addition to this, related articles have explored more complex attack scenarios under SL-DP protection. Xiang et al. (Xiang et al., 2023) proposed a method that combines local DPSGD with Byzantine fault tolerance techniques. By leveraging differential privacy’s random noise, they construct an aggregation approach that effectively thwarts many existing Byzantine attacks. This method ensures the privacy and stability of federated learning systems by introducing randomness that prevents Byzantine attackers from accurately interfering with gradient updates and aggregation processes. Wei et al. (Wei et al., 2020) assumed that downlink broadcast channels are more dangerous than uplink channels and proposed NBAFL, which not only add noise to the parameters before aggregation but also add noise again after aggregation to achieve a higher level of privacy protection. Naseri et al. (Naseri et al., 2020) proposed a analytical framework that empirically assesses the feasibility and effectiveness of SL-DP and CL-DP in protecting FL. Through many attack experiments, their results indicate that while SL-DP can defend membership inference attacks and backdoor attacks, it cannot resist attribute inference attacks.

In addition to the above stochastic gradient descent, alternating direction method of multipliers (ADMM) is also local optimization method for FL. ADMM introduces Lagrange multipliers to transform the original problem into a series of subproblems, which are then alternately solved until convergence (Zhang and Kwok, 2014). Huang et al. (Huang et al., 2019) utilize a first-order approximation function as the objective function for local clients. This first-order approximation function is convex and naturally constrains the $l_{2}$ norm of the gradient within a bound without clipping the gradient to get the sensitivity. Additionally, they devised an adaptive noise coefficient decay to facilitate the convergence of this first-order approximation function. Based on this, Ryu et al. (Ryu and Kim, 2022) proposed local multiple iterations to accelerate convergence speed and reduce privacy loss. However, ADMM-based optimization methods can only be used for convex optimization problems and are not widely applicable in FL.

Under general CL-DP, the server is often assumed to be completely honest (honest and not curious) and can be viewed a data owner. As shown in the figure 3(b), the central server can collect the parameters uploaded by each client in each round. The goal of CL-DP is to hide the presence of a single client or device, or to be more specific, to limit the impact of any single client or device on the distribution of aggregation results. It requires that the attackers cannot identify the participation of one client or device by observing the output of aggregated parameters ¹¹¹¹11It is worth noting that while some works locally clip and add noise, the amount of noise added is $\mathcal{N}(0,\sigma^{2}C^{2}/K)$, where $K$ is the number of clients participating in federated learning (Shi et al., 2023; Cheng et al., 2022). Each client model $\mathbf{w}_{k}$ satisfy weak LDP protection, but this is not the protection goal. The intention is for the uploaded data to the central aggregator to be equivalent to $\sum_{k=1}^{K}\mathbf{w}_{k}+\mathcal{N}(0,\mathbf{\sigma}^{2}C^{2})$, it can be seen that the definition of neighboring datasets is CL-DP (Definition 3.2)..

Geyer et al. (Geyer et al., 2017) introduced CL-DP in federated learning for the first time, assuming differential attacks from any participating client. The server perturbs the distribution of the summed parameters by limiting each client’s parameter contribution and then adding noise. Based on work of Geyer et al. (Geyer et al., 2017), Mcmahan et al. (McMahan et al., 2017b) proposed the DP-FedAvg and DP-FedSGD algorithms, which employ client sampling techniques for privacy amplification and utilize the moment accountant mechanism (Abadi et al., 2016) for privacy computation. Their algorithms achieved comparable performance of non-private models in Long Short-Term Memory (LSTM) language.

The previous work constrained each client’s model parameters to a fixed constant, while Andrew et al. (Andrew et al., 2021) proposed an adaptive clipping method. Their method uses an adaptive clipping bound based on a parameter’s norm distribution quantile, estimated with differential privacy, rather than a fixed bound. Their experiments demonstrate that adaptive clipping to the median update norm performs well across a range of federated learning tasks. Zhang et al. (Zhang et al., 2022) studied the impact of clipping on model parameters and gradients. They demonstrated that uploading clipped gradients leads a better performance than uploading clipped models on the client side, and provided a convergence analysis based on gradient clipping with noise, where the upper bound of convergence highlighted the additional terms introduced by differential privacy.

In addition to this, many studies have focused on reducing the impact of noise on uploaded model parameters. Chen et al. (Cheng et al., 2022) observed that using a small clipping threshold can decrease the injected noise volume. They reduced the norm of local updates by regularizing local models and making the local updates sparse. DP-FedSAM  (Shi et al., 2023) uses a SAM optimizer (Foret et al., 2020) to help model parameters escape saddle points and enhance the robustness of the model to noise, aiming to find more stable convergence points. Bietti et al. (Bietti et al., 2022) proposed PPSGD, which trains personalized local models and ensures global model privacy simultaneously. They utilized personalized models to enhance the global model’s performance. Similarly, Yang et al. (Yang et al., 2023b) dynamically preserved high-information model parameters locally from noise impact using layer-wise Fisher information. They also introduced an adaptive regularization strategy to impose differential constraints on model parameters uploaded to the server, enhancing robustness to clipping. Xu et al. (Xu et al., 2023a) took into account that the size of the softmax layer of model parameters is linearly related to the number of sample labels. By keeping the softmax layer local and not uploading it, the participation of more clients (i.e., more sample labels) in federated learning does not result in more noise injection. Triastcyn et al. (Triastcyn and Faltings, 2019) leveraged the assumption that data is distributed similarly across clients in HFL, which leads to their updates being highly consistent, and utilized BDP for privacy auditing to obtain tighter privacy bounds. Their assumption and method is not only used under the CL-DP, but also applied in SL-DP scenario.

CL-DP with Secure Aggregation (SA) ¹²¹²12Many works refer to this framework as “distributed dp” (Kairouz et al., 2021a; Agarwal et al., 2021; Yang et al., 2023c).. As mentioned above, CL-DP often requires a secure server for aggregation. In order to eliminate the reliance on a trusted central authority, many recent studies have combined differential privacy techniques with secure aggregation (Bonawitz et al., 2017) to achieve CL-DP. As shown in Figure 4, after local training, each client adds a small amount of differential privacy noise to the model parameters, then encrypts and sends them to the server. The server performs aggregation, enabling the aggregation of noise levels from each client, thereby ensuring that the encrypted model satisfies CL-DP. However, secure aggregation relies on modular arithmetic and cannot be directly compatible with continuous noise mechanisms (such as Laplace mechanism and Gaussian mechanism) currently used to implement differential privacy. This has led researchers to begin designing discrete noise addition mechanisms and integrating them with secure aggregation to characterize differential privacy.

Agarwal et al. (Agarwal et al., 2018) proposed and extended the first discrete mechanism, namely the binomial mechanism, in the federated setting. The discrete nature of binomial noise, along with quantization techniques (Suresh et al., 2017), enables efficient transmission. However, applying this mechanism to practical tasks faces limitations. Firstly, binomial noise can only achieve approximate differential privacy with nonzero probability of fully exposing private data, and the binomial mechanism does not achieve Renyi or concentrated differential privacy.

To address these issues, Wang et al. (Wang et al., 2020a) first discretized local parameters (McMahan et al., 2017a), then added noise from the Discrete Gaussian Distribution to satisfy differential privacy. Kairouz et al. (Kairouz et al., 2021a) also employed a Discrete Gaussian Mechanism, providing a novel privacy analysis associated with the proportion of malicious clients for the sum of Discrete Gaussian Mechanism. They extensively investigate the impact of discretization, noise, and modular clipping on model utility. However, the Discrete Gaussian Mechanism suffers from the problem of non-closure under addition. To address this, Agarwal et al. (Agarwal et al., 2021) proposed the Skellam Mechanism, which uses the difference of two independent Poisson distributed random variables as noise. The noise distribution of this mechanism naturally satisfies the property of closure under addition due to the first-kind modified Bessel function, thereby avoiding additional privacy budget for noise summation. However, the noise magnitude of the aforementioned discrete noise schemes is unbounded, thus requiring modular clipping for secure aggregation, leading to additional bias. Chen et al. (Chen et al., 2022b)introduced the multi-dimensional Poisson Binomial Mechanism, a unbiased and bounded discrete differential privacy mechanism. It treats model parameters as probabilities for a binomial distribution, and generates binomial noise based on these probabilities to control the noise bound.

However, the above methods rely on per-parameter quantization, resulting in significant communication overheads. To further explore the fundamental communication costs required for achieving optimal accuracy under centralized differential privacy, Chen et al. (Chen et al., 2022a) proposed using a linear scheme based on sparse random projection to reduce communication overheads. They utilize count sketch matrices and hash functions to obtain sparse projection matrices, thus reducing model parameter dimensionality. Kerkouche et al. (Kerkouche et al., 2021) also sparsify vectors by decomposing model parameters into a “sparse orthogonal basis matrix” and a “sparse signal” multiplied by the discrete Gaussian mechanism locally. The server can reconstruct the sparse gradient vector by solving a convex quadratic optimization problem. In addition to designing new discrete noise mechanisms to integrate secure aggregation techniques, Stevens et al. (Stevens et al., 2022) proposed a secure federated aggregation scheme based on the Learning With Errors (LWE) problem (Regev, 2009). It encrypts the model parameters of local clients using masks generated by the LWE problem before uploading. This method utilizes the random noise naturally introduced by LWE technology, ensuring that the sum of errors in the LWE problem satisfies differential privacy.

To achieve the shuffle model with CL-DP as shown in Figure 5 (a), each user randomizes their local updates with $(\epsilon_{l},\delta_{l})$-LDP, and the aggregated updates through shuffling satisfies $(\epsilon_{c},\delta_{c})$-DP. Typically, following the inertia of LDP, researchers consider $\epsilon_{l}$-LDP, setting $\delta_{l}=0$. Note that we are only discussing methods that benefit from privacy amplification of shuffling here. Some approaches, such as those in (Sun et al., 2021; Zhao et al., 2022), employ the shuffling step solely for breaking relations between dimensions, inherently belonging to the general CL-DP category.

Specifically, Liu et al. (Liu et al., 2021a) first consider FL in the shuffle model, proposing the FLAME algorithm. In this algorithm, each user samples the dimensions of local updates and perturbs the values in these dimensions for shuffling and aggregation. To simultaneously leverage the privacy amplification benefits of sampling and shuffling, where the privacy amplification from shuffling relies on a certain number of user samples, they further introduce the dummy padding strategy on the shuffler side, ensuring the sampling size remains constant across each dimension. Around the different sampling strategy, Liew et al. (Liew et al., 2022) proposed shuffled check-in protocol in CL-DP, which is similar to self sampling (Girgis et al., 2021a) in the aspect of methodology but achieves $(\epsilon_{l},\delta_{l})$-LDP in theory and deriving a tighter privacy amplification bound with RDP. Beyond the uniform $\epsilon_{l}$-LDP setting for each user, Liu et al. (Liu et al., 2023b) considered heterogeneous privacy budgets that assume different $\epsilon_{k}$-LDP for each client, deriving a tight $(\epsilon_{c},\delta_{c})$-DP bound in the analyzer side based the idea of hiding among clones (Feldman et al., 2022). To improve the utility, they proposed a Clip-Laplace mechanism to bound the Laplace noise in a finite range.

In the shuffle model using SL-DP, the neighboring databases for $(\epsilon_{c},\delta_{c})$-DP analysis are defined based on samples rather than clients’ data. To achieve it, a straightforward approach is to perturb each sample’s updates separately, then aggregate and shuffle these samples. Chen et al. (Chen et al., 2023a) adopt this method, further exploring its privacy amplification under a heterogeneous privacy scenario and achieving a tighter privacy bound by $f$-DP (also known as GDP) compared to Liu et al. (Liu et al., 2023b). More typically and beneficially, each user samples only one record to train and reports its corresponding local updates, as shown in Figure 5 (b).

Specifically, Girgis et al. (Girgis et al., 2021b) introduce the CLDP-SGD algorithm for SL-DP with shuffling, which involves sampling clients first and then sampling the user’s sample. Such a combination of dual sampling and shuffling enhances privacy amplification and reduces communication costs. Building on CLDP-SGD, Girgis et al. (Girgis et al., 2021a) introduce the dss-SGD algorithm. They employ Poisson sampling for client selection instead of uniformly sampling a fixed number of clients by the shuffler and demonstrate the corresponding privacy amplification effect.

These two modes are often confused, and many articles categorize SL-DP as LDP because they both assume a semi-honest server. However, in fact, they are different from the definition. There is a definition of neighboring datasets in DP, and always many samples in the neighboring datasets. So, clipping is performed on each sample to limit the sensitivity brought by each sample in SL-DP. In LDP, neighboring datasets degenerate into any two different inputs, so sensitivity is often obtained by directly clipping model parameters. In terms of the number of local iterations, in SL-DP, each round of local iteration is equivalent to accessing the local dataset, requiring noise to be added to it. In LDP, the privacy loss of LDP occurs at the moment of upload, and the perturbation occurs only at the moment before upload. Moreover, many LDP articles focus more on the issue of parameter dimensions because in LDP, dimensions divide the privacy budget, leading to privacy budget explosion. Although dimensions in SL-DP also affect performance, they do not have as much impact as in LDP. Generally, LDP mechanisms can achieve the protection of SL-DP, but the reverse is not true. In special cases, such as when a client has only one piece of data, we consider SL-DP to be equivalent to LDP, but such cases are rare in the HFL.

Both require local noise addition, but the scale of noise added locally differs. For example, using Laplace noise, in LDP, adding laplace noise $Lap(0,\epsilon/\Delta f)$, locally achieves $\epsilon$-LDP. In contrast, CL-DP only requires adding laplace noise $Lap(0,\epsilon/(K\Delta f))$, where $K$ is the number of clients, and secure aggregation ensures that the final aggregated weights satisfy $\epsilon$-DP. Although CL-DP with SA provides some level of LDP privacy protection locally, the amount of noise is too small, resulting in local privacy protection that is far less than that of $\epsilon$-LDP.