Differential Privacy Mechanisms for FL

As highlighted in the chapter introduction, while federated learning avoids direct sharing of raw data, the model updates themselves can still leak sensitive information about the client's underlying dataset. An adversary observing these updates might infer properties about the data or even reconstruct parts of it. To provide mathematically rigorous privacy guarantees against such threats, we turn to Differential Privacy (DP).

Differential Privacy offers a strong standard for privacy protection. At its core, it ensures that the outcome of an analysis (like computing an aggregate model update in FL) is statistically similar whether any particular individual's data is included in the dataset or not. This prevents an adversary from confidently inferring the presence or specific details of any single participant's data by observing the output.

Defining Differential Privacy

Formally, a randomized algorithm $\mathcal{M}$ satisfies $(\epsilon, \delta)$-differential privacy if, for any two adjacent datasets $D_1$ and $D_2$ that differ by only one individual's data, and for any possible set of outputs $S$, the following inequality holds:

$$P[\mathcal{M}(D_1) \in S] \leq e^{\epsilon} P[\mathcal{M}(D_2) \in S] + \delta$$

Let's break down the components:

• $\mathcal{M}$: The randomized algorithm. In FL, this could be the entire process of clients computing updates and the server aggregating them. Randomness is typically introduced by adding noise.
• Adjacent Datasets $D_1, D_2$: Two datasets where one can be formed from the other by adding or removing the data of a single individual (or a single data point, depending on the granularity of protection).
• $\epsilon$ (Epsilon): The privacy loss parameter, often called the "privacy budget". It's a non-negative value that bounds how much the probability of any given output can change when a single individual's data is modified. A smaller $\epsilon$ implies stronger privacy, meaning the output distribution changes less drastically, making it harder to distinguish between $D_1$ and $D_2$. If $\epsilon = 0$, the output distribution must be identical, providing perfect privacy but likely no utility.
• $\delta$ (Delta): Represents the probability that the strict $\epsilon$-privacy guarantee might be broken. It should typically be a very small number, often less than the inverse of the dataset size (e.g., $1/N$ where $N$ is the number of participants). When $\delta = 0$, the algorithm satisfies pure $\epsilon$-differential privacy. When $\delta > 0$, it's often referred to as approximate $(\epsilon, \delta)$-differential privacy.

The intuition is that if $\epsilon$ and $\delta$ are small, an observer seeing the output $\mathcal{M}(D)$ cannot confidently determine whether any specific individual's data was used in the computation.

Achieving Differential Privacy via Noise Addition

The most common way to make an algorithm differentially private is to inject carefully calibrated random noise into its output. The amount of noise required depends on how much the output could change if one individual's data were different. This maximum possible change is called the sensitivity of the function.

Consider a function $f$ that maps datasets to real-valued vectors (like computing an average gradient).

• $L_1$ Sensitivity ($\Delta_1 f$): The maximum possible change in the $L_1$ norm of the output when one individual's data is changed: $$\Delta_1 f = \max_{D_1, D_2} \| f(D_1) - f(D_2) \|_1$$
• $L_2$ Sensitivity ($\Delta_2 f$): The maximum possible change in the $L_2$ norm of the output: $$\Delta_2 f = \max_{D_1, D_2} \| f(D_1) - f(D_2) \|_2$$

To ensure the sensitivity is bounded, a common prerequisite in FL is gradient clipping. Before noise is added, each client's update vector $u_i$ is scaled down if its norm exceeds a predefined threshold $C$: $u_i \leftarrow u_i / \max(1, \|u_i\|_2 / C)$. This ensures that the maximum influence of any single client's update on the sum is bounded (e.g., the $L_2$ sensitivity of the sum is at most $C$ if we consider adding/removing one client's entire clipped update).

Two primary noise-adding mechanisms are widely used:

1. Laplace Mechanism: Adds noise drawn from a Laplace distribution $\text{Lap}(b)$, where the scale parameter $b$ is set based on the $L_1$ sensitivity and the desired $\epsilon$. To achieve $\epsilon$-DP for a function $f$, noise with scale $b = \Delta_1 f / \epsilon$ is added to each component of the output $f(D)$.
2. Gaussian Mechanism: Adds noise drawn from a Gaussian distribution $\mathcal{N}(0, \sigma^2 I)$, where the standard deviation $\sigma$ depends on the $L_2$ sensitivity, $\epsilon$, and $\delta$. To achieve $(\epsilon, \delta)$-DP for a function $f$, noise with $\sigma \ge \frac{\Delta_2 f \sqrt{2 \ln(1.25/\delta)}}{\epsilon}$ is added to the output $f(D)$. This is often preferred for high-dimensional outputs like model gradients.

Application Models in Federated Learning

Differential privacy can be applied in FL in two main ways, differing in where the noise is added:

• Central Differential Privacy (CDP):

  • Clients compute their updates (e.g., gradients or model weights) based on their local data.
  • These exact, sensitive updates are sent to the central server (potentially protected during transit by standard encryption like TLS).
  • The server aggregates the updates (e.g., by averaging).
  • Before using the aggregate or sharing it (e.g., to update the global model), the server adds calibrated noise (Laplace or Gaussian) to the aggregated result. The amount of noise depends on the sensitivity of the aggregation function with respect to a single client's entire contribution.
  • Trust Assumption: Requires trusting the central server not to misuse the individual, un-noised updates it receives before aggregation and noise addition.
  • Noise Level: Generally requires less noise compared to Local DP for the same privacy level, as noise is added only once to the sum, leading to potentially higher model utility. Often combined with Secure Aggregation (SMC) to protect updates before they reach the server for aggregation.

• Local Differential Privacy (LDP):

  • Each client computes its update based on its local data.
  • Before sending the update to the server, each client individually adds calibrated noise to its own update to make it differentially private with respect to its own local data. The sensitivity here relates to changes within a single client's dataset.
  • The noisy updates are sent to the server.
  • The server aggregates these already-noisy updates. No further noise is needed by the server for privacy.
  • Trust Assumption: Does not require trusting the server; privacy is enforced at the client level before data leaves the device. Offers stronger protection against a malicious or compromised server.
  • Noise Level: Requires significantly more noise per client. The aggregation of many noisy updates can lead to a very noisy overall result, often substantially impacting model convergence and final accuracy. The "noise cancels out" effect is less pronounced than the accumulation of noise variance.

The choice between Central and Local DP involves a fundamental trade-off between the strength of the privacy guarantee (especially regarding trust in the server) and the impact on model performance.

Comparison of Central DP and Local DP workflows in Federated Learning. In CDP, noise is added centrally after aggregation. In LDP, noise is added locally by each client before sending updates.

Understanding these DP mechanisms and application models is foundational for building FL systems that offer quantifiable privacy protections alongside collaborative model training. The next sections will explore applying these concepts, specifically adding noise to gradient updates and managing the privacy budget over multiple training rounds.