Differential Privacy

The privacy budget (epsilon ε) is the core parameter quantifying the maximum allowable privacy loss. It is a non-negative real number where smaller values indicate stronger privacy guarantees.

• Definition: An algorithm is (ε, δ)-differentially private if, for all neighboring datasets (differing by one record) and all possible outputs, the probability of any output changes by at most a factor of e^ε.
• Interpretation: An ε of 0.1 provides very strong privacy, while an ε of 10 is considered weak. The value is additive; running multiple queries consumes the budget.
• Role in Federated Learning: Applied to client updates before aggregation, ε controls how much noise is added, trading off privacy for model utility.

Sensitivity is the maximum possible change in a function's output when a single individual's data is added or removed from the dataset. It determines how much noise must be added to achieve differential privacy.

• L1 vs. L2 Sensitivity: L1 sensitivity (Δ₁f) is the maximum absolute change; L2 sensitivity (Δ₂f) is the maximum Euclidean norm change. The choice dictates which noise mechanism (Laplace or Gaussian) is used.
• Calculation: For a function f, Δf = max ||f(D) - f(D')|| over all neighboring datasets D, D'.
• Practical Impact: Functions with low sensitivity (e.g., averages of bounded values) require less noise to privatize, preserving more utility in the final output.

A post-processing guarantee states that any analysis performed solely on the output of a differentially private algorithm cannot weaken its privacy guarantee. No additional privacy loss occurs.

• Formal Guarantee: If algorithm M is (ε, δ)-differentially private, then for any arbitrary function g (deterministic or randomized), the composed algorithm g(M(x)) is also (ε, δ)-differentially private.
• Critical Implication: This allows the safe use, transformation, and publication of DP outputs without needing to re-analyze the privacy cost. It is a foundational property for building complex, multi-step private systems.
• System Design Benefit: Enables modular architecture where private outputs can be safely fed into downstream analytics or models.

Composition rules dictate how the privacy budget accumulates when multiple differentially private analyses are performed on the same dataset. They enable the design of complex, multi-query algorithms.

• Basic Sequential Composition: Running k algorithms with budgets ε₁...εₙ results in a total privacy cost of Σ εᵢ (sum of epsilons).
• Advanced Composition: Provides tighter bounds, especially for many queries (k >> 1). For (ε, δ)-DP algorithms, the total cost grows roughly with √(k log(1/δ'))ε.
• Parallel Composition: If analyses are performed on disjoint subsets of the data, the overall privacy cost is only the maximum of the individual ε values, not the sum. This is highly efficient for partitioned data.

Group privacy extends the core guarantee to protect the data of small groups of individuals, not just single records. The privacy loss scales linearly with the group size.

• Formal Extension: An algorithm that is ε-differentially private for neighboring datasets (differing by one record) is (kε)-differentially private for datasets differing by at most k records.
• Implication: Protecting large groups requires proportionally smaller ε (stronger noise) per query. This formalizes the intuition that hiding the participation of many people is harder than hiding one person.
• Design Consideration: For applications where user data may contain correlated records (e.g., family members), group privacy analysis is essential for meaningful guarantees.

Differential privacy provides a guarantee that holds regardless of an adversary's prior knowledge or auxiliary information. This is a key distinction from weaker anonymity-based approaches.

• Strong Guarantee: The privacy definition does not make assumptions about what other data an attacker might possess. Even with access to 99% of the dataset, an attacker cannot confidently infer the 1% remaining private record from the DP output.
• Contrast with k-Anonymity: Techniques like k-anonymity can be broken with auxiliary information linking "anonymous" records to external databases. DP is provably resilient to such linkage attacks.
• Foundation for Trust: This property is why DP is considered a gold standard for privacy in statistical databases and federated learning, as it provides a mathematical safety net against powerful, informed adversaries.

The Laplace Mechanism is the canonical method for achieving differential privacy for real-valued or integer-valued query outputs. It works by adding noise drawn from a Laplace distribution, where the scale of the noise is calibrated to the sensitivity of the query (the maximum change a single individual's data can cause in the output).

• Core Use: Releasing counts, averages, histograms, and other numerical statistics.
• Mathematical Basis: Adds noise Lap(Δf / ε), where Δf is the L1 sensitivity and ε is the privacy budget.
• Example: Releasing the average salary in a company database with formal privacy guarantees.

The Gaussian Mechanism achieves differential privacy by adding noise drawn from a Gaussian (normal) distribution. It is primarily used with the (ε, δ)-differential privacy definition, where δ is a small probability of privacy failure. The noise scale is calibrated to the L2 sensitivity of the query.

• Core Use: High-dimensional vector outputs common in machine learning, such as model gradients or embeddings.
• Mathematical Basis: Adds noise N(0, (σ^2) * I) where σ is scaled to Δf, ε, and δ.
• Advantage: Often provides better utility (less distortion) than the Laplace mechanism for high-dimensional vectors due to the lighter tails of the Gaussian distribution.

The Exponential Mechanism is used for queries with non-numeric outputs, such as selecting the best item from a set (e.g., the most frequent disease code or the optimal hyperparameter). It works by assigning a quality score to each possible output and then sampling an output with a probability exponentially proportional to its score and the privacy parameter.

• Core Use: Private selection problems, decision-making, and releasing categorical information.
• How it Works: Output r is chosen with probability proportional to exp(ε * u(D, r) / (2Δu)), where u is a utility function and Δu is its sensitivity.
• Example: Privately identifying the most common diagnosis in a set of medical records without revealing if any specific patient had that diagnosis.

Report Noisy Max is a simpler, highly efficient specialization of the Exponential Mechanism for identifying the maximum value among a set of numerical queries (e.g., which category has the highest count). It adds independent Laplace or Gaussian noise to each query's true answer and returns the index of the noisily largest value.

• Core Use: Private top-k selection, frequent itemset mining, and histogram queries.
• Process: 1) Add calibrated noise to each count. 2) Return the index of the maximum noisy count.
• Efficiency: More computationally efficient than the general Exponential Mechanism as it avoids sampling from a complex distribution over all possible outputs.

The Sparse Vector Technique (SVT) is an advanced composition mechanism designed for scenarios where many queries are asked, but only a small number are expected to be above a certain threshold. It pays privacy cost primarily for the queries that cross the threshold, allowing for a large number of below-threshold queries to be asked with minimal privacy loss.

• Core Use: Screening queries, adaptive data analysis, and private algorithm selection.
• Two Main Variants: Above Threshold and Numerical Sparse Vector.
• Key Insight: The algorithm's privacy cost scales with the number of positive discoveries (c), not the total number of queries (k), which can be a significant saving when c << k.

Randomized Response is a foundational, local model differential privacy mechanism where each individual perturbs their own data before sending it to the data collector. It is the basis for Local Differential Privacy (LDP). The individual answers a sensitive question (e.g., "Do you have disease X?") by flipping a coin to decide whether to tell the truth or lie.

• Core Use: LDP surveys, privacy-preserving data collection in untrusted settings (e.g., Google's RAPPOR).
• Process: With probability p, the respondent tells the truth; with probability 1-p, they give a random answer.
• Trust Model: Requires no trusted central server, as privacy is enforced at the edge device before any data leaves.

Local Differential Privacy is a decentralized privacy model where each data owner perturbs their data locally before sending it to an aggregator. Unlike central DP, which trusts a curator, LDP provides a strong guarantee even against a malicious central server.

• Key Mechanism: Each client applies a randomized algorithm (e.g., Randomized Response) to their data, ensuring the output is differentially private.
• Primary Use Case: Collecting statistics from a large population of untrusted users, such as telemetry data in web browsers or mobile apps.
• Trade-off: Provides stronger trust assumptions but often requires more noise per client to achieve the same utility as central DP, leading to less accurate aggregated results.

Secure Multi-Party Computation is a cryptographic subfield that enables multiple parties to jointly compute a function over their private inputs while revealing only the final output. It ensures no party learns anything about another's input beyond what is inferable from the result.

• Core Principle: Computations are performed on encrypted or secret-shared data.
• Relation to DP: While MPC provides computational privacy (hiding inputs during computation), DP provides statistical privacy (limiting inference from outputs). They are complementary: MPC can be used to compute a DP aggregate without any party seeing raw data.
• Example: Several hospitals can use MPC to compute the average patient treatment cost without sharing individual patient records.

Homomorphic Encryption is a form of encryption that allows specific types of computations to be performed directly on ciphertext. The encrypted result, when decrypted, matches the result of operations performed on the plaintext.

• Types: Partially Homomorphic Encryption (PHE) supports one operation (e.g., addition in Paillier). Fully Homomorphic Encryption (FHE) supports both addition and multiplication, enabling arbitrary computations.
• Role in Private ML: Enables a server to train a model or compute aggregates on encrypted client updates without ever decrypting them. It provides strong confidentiality but is computationally intensive.
• Synergy with DP: FHE can compute a function, and DP noise can be added to the encrypted result before decryption, yielding a private output.

The Gaussian Mechanism is a fundamental algorithm for achieving differential privacy by adding noise drawn from a Gaussian (normal) distribution to the output of a function. It is preferred over the Laplace Mechanism for multi-dimensional queries or when the output is a real-valued vector.

• Noise Calibration: The scale (standard deviation) of the noise is proportional to the L2-sensitivity of the function (the maximum change in the output's Euclidean norm when one input changes) and inversely proportional to the privacy parameters (epsilon, delta).
• Key Property: It provides (ε, δ)-differential privacy, where δ is a small probability of privacy failure. This is a slight relaxation of pure (ε)-DP.
• Common Application: Privately releasing gradient vectors in machine learning, where the sensitivity is bounded via gradient clipping.

A Trusted Execution Environment is a secure, isolated area within a main processor (e.g., Intel SGX, AMD SEV) that guarantees the confidentiality and integrity of code and data loaded inside it, even if the host operating system is compromised.

• Hardware-Based Isolation: Code and data within the TEE (an enclave) are encrypted in memory and can only be decrypted by the CPU inside the secure enclave.
• Use in Private Aggregation: Sensitive operations, like summing client updates in federated learning, can be performed inside a TEE. Clients encrypt their data for the TEE, which decrypts, processes, and outputs only the aggregated, potentially noised result.
• Trust Model: Shifts trust from software and cloud providers to the hardware manufacturer and the attestation mechanism that verifies the enclave's integrity.

In differential privacy, the privacy budget (epsilon, ε) is a non-negative parameter that quantifies the maximum allowable privacy loss for an individual when their data is included in an analysis. It is the core quantifier of the privacy guarantee.

• Interpretation: A smaller ε means stronger privacy (more noise, less accuracy). ε = 0 implies perfect privacy but no useful output. There is no universal "good" ε; it is a policy decision balancing risk and utility.
• Composition: The privacy budget is consumed over multiple queries. The Basic Composition Theorem states that running k ε-DP mechanisms results in kε-DP. Advanced composition allows for tighter bounds.
• Management: Systems must track ε consumption across all analyses on a dataset to prevent exceeding a pre-defined total budget, a concept known as privacy accounting.