Local Differential Privacy (LDP)

The foundational mechanism for LDP, originating from survey methodology. For a binary value (e.g., 'Yes'/'No'), the client tells the truth with probability p and lies with probability 1-p. The aggregator can later correct for this known bias to estimate population statistics while never knowing any individual's true answer.

• Core Principle: Data owner flips a coin to decide whether to report truth.
• Example: In a survey for a sensitive attribute, a client answers truthfully 75% of the time and flips the answer 25% of the time. The server receives only the perturbed answers.

The primary methods for adding calibrated continuous noise to numerical values or model updates (gradients). Noise is drawn from a probability distribution whose scale is set by the privacy budget (epsilon) and the sensitivity of the function—the maximum possible change in its output from any single data point.

• Laplace Mechanism: Provides pure (ε,0)-differential privacy. Adds noise from the Laplace distribution. Used for counting queries and unbounded sensitivity.
• Gaussian Mechanism: Provides (ε, δ)-differential privacy. Adds noise from the Gaussian distribution. Preferred for high-dimensional vectors like gradients due to better composition properties and lighter tails.

A mechanism for privatizing categorical data, such as which website a user visited from a known set. The client encodes their true value as a one-hot vector (e.g., [0,0,1,0]), then flips each bit independently with a calibrated probability.

• Google's RAPPOR: A production system using this principle for longitudinal data collection from Chrome. It employs a two-step process: Permanent Randomized Response on the client's true value, followed by Instantaneous Randomized Response each time a report is sent.
• Utility: The server aggregates thousands of perturbed bit vectors to estimate frequency histograms for the entire population.

The systematic tracking of cumulative privacy loss across multiple queries or training rounds. In federated learning, each client participates in many rounds, each consuming a portion of their total privacy budget.

• Sequential Composition: The simplest rule: if a mechanism satisfying ε-DP is used k times, the total privacy loss is k*ε. Often too conservative.
• Advanced Composition & RDP: Rényi Differential Privacy (RDP) provides much tighter bounds for the composition of Gaussian mechanisms, making iterative training with LDP practically feasible. The server runs a privacy accountant to ensure the total (ε, δ) does not exceed the allowed limit.

The critical first step in applying the Laplace or Gaussian mechanism. Sensitivity (Δf) is the maximum possible L1 or L2 norm by which a single data point can change the output of a function f. It directly controls the noise magnitude.

• L1 Sensitivity (Δ₁f): Used for the Laplace Mechanism. For a gradient vector, it's the maximum possible L1 norm of the gradient contributed by one data sample.
• L2 Sensitivity (Δ₂f): Used for the Gaussian Mechanism. The maximum possible L2 norm.
• Clipping: To bound sensitivity, client updates are clipped to a maximum L2 norm C before noise addition. This is essential for training stability and predictable privacy cost.

LDP operates in a distrusted aggregator model, but can be combined with other technologies for enhanced security.

• LDP + Secure Aggregation: Clients send LDP-protected updates, which are then summed using multi-party computation (MPC) or homomorphic encryption. This hides which client sent which noisy update, providing privacy from the server and from other clients.
• LDP + Trusted Execution Environments (TEEs): The LDP noise addition can be performed inside a hardware-secured enclave (e.g., Intel SGX) on the client device, guaranteeing the code was executed correctly and the raw data was never accessible to the device OS.

The foundational mechanism for LDP, originally from survey methodology. For a binary value (e.g., 'Yes'/'No'), the client tells the truth with probability p and lies with probability 1-p. The aggregator can later correct for this known noise in the aggregated statistics.

• Example: A user's true answer is 'Yes'. With p=0.75, they report 'Yes' 75% of the time and 'No' 25% of the time.
• Key Property: Provides pure ε-LDP where ε = ln(p / (1-p)).
• Use Case: Collecting binary statistics like 'Has disease X?' or 'Visited website Y?' with strong deniability.

Adds noise drawn from a Laplace distribution to numerical values. The scale of the noise (λ) is calibrated to the sensitivity of the query (Δf) and the desired privacy parameter (ε): λ = Δf / ε.

• Sensitivity (Δf): The maximum possible change in the query's output when a single user's data is added or removed.
• Mechanism: Output = True Value + Laplace(0, λ).
• Use Case: Perturbing numerical model updates (gradients) or aggregated statistics like average age or income before sending to the server.

Adds noise drawn from a Gaussian (Normal) distribution to numerical values. Provides the relaxed (ε, δ)-differential privacy guarantee. The noise scale (σ) is calibrated to the sensitivity (Δf), ε, and δ.

• Formula: σ = Δf * √(2 * ln(1.25/δ)) / ε.
• Advantage over Laplace: Gaussian noise often has lighter tails, which can be preferable for machine learning optimization as it may produce less variance in the aggregated result.
• Use Case: Common in federated learning for perturbing high-dimensional gradient vectors where (ε, δ)-DP is an acceptable relaxation.

A technique for categorical data with a large domain (e.g., a set of visited websites). The client encodes their true value as a bit vector where only the index corresponding to their value is 1, and all others are 0. They then independently flip each bit with a probability derived from ε.

• Process: For each bit in the vector: if it is 1, keep it as 1 with probability p; if it is 0, keep it as 0 with probability q. Common schemes are Generalized Randomized Response (GRR) or Optimal Unary Encoding (OUE).
• Efficiency: More communication-efficient than sending the full categorical value for large domains.
• Use Case: Heavy hitter estimation, frequency estimation of items in a set (e.g., emojis used, apps installed).

A more advanced technique that applies a randomized Hadamard transform to the unary-encoded vector before perturbation. This spreads the user's single '1' bit across the entire vector, allowing for much less noise to be added per bit while achieving the same privacy guarantee.

• Core Idea: Transform the data into a different basis where it is 'sparse' in a randomized way, then apply basic bit flipping.
• Benefit: Dramatically improves the signal-to-noise ratio (utility) for the same privacy budget (ε), especially for large data domains.
• Use Case: Deployed in real-world systems (e.g., Apple's iOS) for collecting vocabulary and emoji frequency data from millions of users with strong LDP guarantees.

The standard technique for applying LDP to federated learning model updates. It involves two critical steps: norm clipping and noise addition.

• Norm Clipping: The client first clips the L2 norm of its local gradient vector to a bound S. This bounds the sensitivity (Δf = 2S).
• Noise Addition: The client then adds calibrated noise (typically Gaussian or Laplace) to the clipped gradient.
• Privacy Budget: Each round consumes a portion of the total (ε, δ) budget. Privacy accounting (like Rényi DP) tracks the cumulative spend across training rounds.
• Use Case: The primary method for providing formal LDP guarantees in federated learning workflows, preventing the server from inferring too much about any client's raw data from their update.

Differential Privacy (DP) is the gold-standard mathematical framework for quantifying and limiting privacy loss. Unlike LDP, which applies noise at the data source, central DP assumes a trusted curator who holds the raw dataset. The curator adds calibrated noise to the output of an analysis (e.g., a query result or aggregated model update).

• Trust Model: Requires a trusted central server.
• Mechanism: Noise applied after computation on the raw dataset.
• Use Case: Ideal for settings where data can be centralized under strict governance, such as within a single organization's secure data lake.

Secure Aggregation is a cryptographic protocol that allows a federated learning server to compute the sum of client model updates without being able to inspect any individual client's contribution. It ensures confidentiality of updates during transmission and aggregation.

• Goal: Prevent the server from performing model inversion or membership inference attacks on individual updates.
• Method: Uses techniques like multi-party computation (MPC) or homomorphic encryption to mask updates.
• Synergy with LDP: Often combined; LDP adds noise for privacy, Secure Aggregation hides which noise was added by whom.

The Gaussian Mechanism is a specific technique for achieving (ε, δ)-differential privacy. It works by adding noise drawn from a Gaussian (normal) distribution to a function's output. The scale of the noise is calibrated to the function's L2 sensitivity (the maximum change in output given a change in one input record).

• Common Use: The standard mechanism for privatizing high-dimensional vectors like neural network gradients or model weights in federated learning.
• Properties: Preferable over the Laplace mechanism for gradient vectors due to the nature of the L2 norm and better composition bounds.
• Implementation: A core building block for implementing LDP on continuous-valued model updates.

Privacy Accounting is the systematic process of tracking the cumulative privacy budget (ε, δ) consumed across multiple iterative computations, such as federated learning rounds. Each noisy update (via LDP) leaks a small amount of privacy; accounting compositions these leaks.

• Key Challenge: Determining when the total privacy loss exceeds a pre-defined, acceptable limit.
• Advanced Methods: Uses composition theorems, Rényi Differential Privacy (RDP), or the Moments Accountant to get tighter bounds than basic sequential composition.
• Output: Provides a formal, auditable guarantee: "After 100 training rounds, this model satisfies (2.5, 10^-5)-differential privacy."

Byzantine Robust Aggregation refers to algorithms designed to compute a correct global model update even when a fraction of clients are malicious (Byzantine) and send arbitrary or adversarial updates. It defends against data poisoning and model poisoning attacks.

• Contrast with LDP: LDP protects client data privacy from a curious server; Byzantine robustness protects the model integrity from malicious clients.
• Techniques: Includes Krum, Bulyan, trimmed mean, and median aggregation.
• Interaction: LDP's noise can interfere with robust aggregation's outlier detection. Co-design is necessary, often using norm bounding (clipping) before noise addition.

Rényi Differential Privacy (RDP) is a relaxation of pure (ε,0)-DP that uses Rényi divergence as its privacy measure. It is not a distinct privacy model but a powerful analytical tool for privacy accounting.

• Primary Advantage: Provides tighter composition bounds for the Gaussian mechanism compared to standard (ε,δ)-DP composition. This allows for more training rounds within the same final privacy budget.
• Workflow: Analyze each round's mechanism using RDP, compose the RDP orders easily, then convert the final RDP guarantee back to a standard (ε,δ)-DP guarantee for interpretation.
• Status: The de facto standard for advanced privacy accounting in iterative ML, including federated learning with LDP.