Differential Privacy

The epsilon (ε) parameter is the core metric of privacy loss. It quantifies the maximum distance between the probability distributions of a query's output on two datasets that differ by a single record.

• A lower ε (e.g., 0.1) provides stronger privacy by injecting more noise.
• A higher ε (e.g., 10) provides weaker privacy but higher utility.
• The privacy budget is a finite, cumulative limit on total ε expenditure across all queries, preventing eventual re-identification through repeated analysis.

The delta (δ) parameter allows for a small probability that the strict ε guarantee is violated. (ε, δ)-differential privacy is a relaxed definition where the privacy loss bound holds with probability 1 - δ.

• δ is typically chosen to be cryptographically small, much less than the inverse of the dataset size.
• This relaxation enables mechanisms like the Gaussian Mechanism, which are essential for many real-world machine learning applications.

Sensitivity measures the maximum impact a single record can have on the output of a query function. It is the crucial calibration factor for determining the scale of noise required.

• Global Sensitivity: The worst-case change over all possible neighboring datasets.
• Local Sensitivity: The maximum change specific to a given dataset, which can leak information if used directly.
• Noise is scaled proportionally to sensitivity; a query with a sensitivity of 1 requires less noise than one with a sensitivity of 100 to achieve the same ε.

The Laplace Mechanism is the foundational technique for achieving pure ε-differential privacy for numerical queries. It works by adding random noise drawn from a Laplace distribution.

• The noise is centered at zero and scaled by the query's sensitivity (Δf) divided by ε.
• It is optimal for queries that output a single real number, such as a count or a sum.
• For example, to release a differentially private average salary, the Laplace Mechanism adds calibrated noise to the true sum before dividing by the count.

The Gaussian Mechanism adds noise drawn from a Gaussian (normal) distribution and is used to achieve (ε, δ)-differential privacy. It is the workhorse of differentially private machine learning.

• It is less brittle than the Laplace Mechanism for complex, multi-dimensional queries.
• The Gaussian Mechanism is fundamental to the DP-SGD (Differentially Private Stochastic Gradient Descent) algorithm, where noise is added to gradients during model training.
• It leverages the additive property of Gaussian noise to compose privacy loss across many training iterations.

A defining property of differential privacy is its resilience to post-processing. Any arbitrary computation applied to the output of a differentially private mechanism does not degrade the privacy guarantee.

• An analyst cannot take a private statistic and make it less private through further calculation.
• This holds even if the post-processing function is malicious or computationally unbounded.
• This guarantee is critical for enabling safe, open-ended data analysis and visualization on released private outputs without requiring additional privacy auditing.

Apple deploys local differential privacy across iOS and macOS to collect user behavior data without accessing raw individual records. The system applies randomized response techniques directly on-device before transmission, ensuring that even Apple's servers never observe the true value.

• Emoji suggestions: Learns popular usage patterns privately
• Safari energy drain: Identifies problematic domains without browsing history exposure
• Privacy parameter: Epsilon values typically between 2 and 8 per day

During the pandemic, Google published Community Mobility Reports using differential privacy to reveal movement trends across 131 countries without exposing individual location histories. The system added Laplace noise to aggregated visit counts for retail, transit, and workplace categories.

• Mechanism: Laplace noise addition to location category counts
• Thresholding: Suppressed outputs for low-density regions to prevent inference
• Scale: Processed billions of location data points daily

LinkedIn applies differential privacy to its Audience Engagement API, allowing advertisers to query aggregate demographic insights about campaign performance without accessing individual member profiles. The system enforces a strict privacy budget per advertiser, exhausting queries that exceed the epsilon threshold.

• Query restriction: Hard limits on total privacy loss per campaign
• Noise calibration: Proportional to query sensitivity, not dataset size
• Use case: Enables ROI measurement while preserving member trust

A finite, quantifiable limit on the total privacy loss allowed over a series of queries against a sensitive dataset. The epsilon (ε) parameter controls the trade-off between privacy and accuracy—lower epsilon values (e.g., ε=0.1) provide stronger privacy guarantees but introduce more noise, while higher values (e.g., ε=10) yield more accurate results with weaker privacy protection.

• Composition theorems track cumulative privacy loss across multiple queries
• Once the budget is exhausted, no further queries are permitted on that dataset
• Administrators must carefully allocate epsilon across analysts and use cases

The statistical probability that an attacker can successfully link de-identified or anonymous data back to a specific individual using auxiliary information or linkage attacks. Differential privacy provides a formal mathematical guarantee against re-identification, unlike ad-hoc anonymization techniques such as k-anonymity.

• Prosecutor risk: Attacker knows a specific individual is in the dataset
• Journalist risk: Attacker attempts to re-identify any individual in the dataset
• Marketer risk: Attacker attempts to match as many records as possible at scale

A data de-identification technique that replaces direct identifiers (names, email addresses, social security numbers) with artificial pseudonyms or tokens. Unlike differential privacy, pseudonymized data remains linkable for analysis purposes and is still considered personal data under GDPR because re-identification is possible with access to the mapping table.

• Preserves referential integrity across records while obscuring identity
• Often used alongside differential privacy for defense-in-depth
• Requires strict separation of pseudonymized data from the mapping key

The creation of high-fidelity, artificially generated datasets that preserve the statistical properties of the original data without containing real individual records. When combined with differential privacy, differentially private synthetic data provides formal privacy guarantees while enabling safe sharing of realistic datasets for model training and testing.

• Generative models (GANs, VAEs) learn the distribution of the original data
• Differentially private training ensures the generator cannot memorize individual records
• Useful for software testing, academic research, and vendor collaboration

A cryptographic protocol where one party (the prover) can prove to another party (the verifier) that a statement is true without revealing any information beyond the validity of the statement itself. ZKPs complement differential privacy by enabling verifiable computation on private data without exposing the underlying inputs.

• zk-SNARKs: Succinct, non-interactive proofs with a trusted setup
• zk-STARKs: Scalable, transparent proofs without trusted setup
• Applications include private identity verification and confidential transactions