Differential Privacy (DP)

The privacy budget, denoted by the parameter epsilon (ε), is the central metric controlling the strength of the privacy guarantee. A smaller ε provides a stronger guarantee, as it makes the output of a computation statistically more similar whether or not any single individual's data is included.

• ε = 0: Perfect, absolute privacy. The output is completely independent of any individual's data, but it also provides zero utility.
• ε < 1: A strong, meaningful privacy guarantee suitable for highly sensitive data.
• ε > 10: A weak guarantee where substantial information leakage about individuals is possible.

Selecting ε is a critical socio-technical decision, balancing the risk of information leakage against the utility of the resulting analysis or model.

The composition theorem quantifies how the privacy budget is consumed when multiple differentially private computations are performed on the same dataset. The total privacy loss accumulates linearly.

If Mechanism M₁ is ε₁-DP and Mechanism M₂ is ε₂-DP, then releasing the outputs of both mechanisms on the same data satisfies (ε₁ + ε₂)-DP.

• This is the fundamental reason for tracking a cumulative privacy budget.
• It forces system designers to account for the total privacy cost of all queries, not just individual ones.
• Advanced composition theorems provide tighter, sub-linear bounds for many queries, enabling more complex iterative algorithms like DP-SGD.

When differentially private mechanisms operate on disjoint subsets of the data, the total privacy cost is not the sum of their individual budgets. Instead, the overall guarantee is bounded by the maximum ε among the mechanisms.

If the dataset is partitioned into independent shards, and a query with budget ε is run on each shard, the total privacy cost is ε, not n × ε.

• This property is essential for scalable privacy-preserving analytics.
• It enables the PATE (Private Aggregation of Teacher Ensembles) framework, where teacher models are trained on disjoint data partitions.
• It allows organizations to run many queries in parallel without exhausting the privacy budget, provided they operate on distinct user groups.

A uniquely powerful property: any computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. The output remains ε-DP regardless of subsequent processing.

• An adversary with access to the DP output can apply any arbitrary function—machine learning, statistical analysis, or even adversarial manipulation—and gains no additional advantage in inferring individual records.
• This guarantee holds without any assumptions about the post-processing function's complexity or intent.
• It provides a composable safety net: once data is privatized, it can be freely used for visualization, model training, or sharing without further privacy risk assessment.

The standard definition protects the privacy of a single individual's record. Group privacy extends this guarantee to groups of correlated individuals, such as a family or a shared device.

If a mechanism is ε-DP for a single record, it provides (k × ε)-DP for a group of size k.

• The privacy guarantee degrades linearly with group size.
• This is a known limitation: protecting a family of four requires a budget four times larger than protecting an individual.
• It highlights the challenge of protecting against adversaries with auxiliary information about correlations between records.

At its core, differential privacy is defined by a bound on the privacy loss random variable. For any output y, the privacy loss is the log-ratio of the probability of observing y from mechanism M on dataset D versus its neighbor D′.

A mechanism is ε-DP if this loss is bounded by ε for all possible outputs and all neighboring datasets.

• This formulation is the foundation for Privacy Loss Distribution (PLD) accounting.
• PLD methods track the full distribution of loss values, enabling much tighter composition bounds than simple linear summation.
• This is the mathematical engine behind modern privacy accountants used in DP-SGD training.

The first large-scale production deployment of differential privacy for a national census. The Bureau injected calibrated noise into population statistics to prevent reconstruction attacks that could re-identify individuals from published tables.

• Epsilon budget: Allocated a total privacy loss parameter across all published tables
• TopDown Algorithm: A hierarchical mechanism that ensures noisy counts are consistent across geographic levels
• Scale: Protected 331 million residents across 8 billion statistical cells
• Controversy: Sparked debate over accuracy vs. privacy trade-offs, with some states challenging the methodology for potentially skewing redistricting data

Apple deploys a local differential privacy implementation across iOS and macOS to collect usage analytics, emoji suggestions, and Safari browsing patterns without accessing raw user data.

• Mechanism: Randomized response with ε per day of data contribution
• Use cases: QuickType keyboard suggestions, Health app usage trends, Safari crash and energy drain reports
• Architecture: Data is randomized on-device before transmission; no raw logs leave the device
• Scale: Deployed across over 1 billion active devices globally

During the pandemic, Google published anonymized mobility trends using differential privacy to help public health officials assess the impact of lockdown policies without exposing individual location histories.

• Mechanism: Applied the Laplace mechanism to aggregate location category visit counts
• Privacy guarantee: Ensured no individual's presence at a specific location could be inferred
• Granularity: Reports covered 131 countries at the regional level
• Legacy: Demonstrated DP's utility for urgent public health analytics while maintaining user trust

LinkedIn uses differential privacy to power its "Audience Engagement API," allowing advertisers to access aggregated demographic insights about content viewers without exposing individual member profiles.

• Mechanism: Gaussian noise addition to aggregate query results
• Privacy model: Protects against differencing attacks that compare overlapping audience segments
• Business impact: Enables advertisers to measure campaign reach while LinkedIn maintains its enterprise trust posture
• Implementation: Integrated directly into the ad analytics pipeline with automated privacy budget tracking

Microsoft applies differential privacy to Windows diagnostic data, collecting crash reports, application usage statistics, and system reliability metrics while mathematically limiting what can be learned about any individual user.

• Mechanism: Local DP with randomized response for categorical telemetry fields
• Scope: Covers Windows 10 and 11 diagnostic data across consumer and enterprise editions
• Enterprise controls: IT administrators can configure telemetry levels and verify privacy guarantees
• Compliance alignment: Supports GDPR and CCPA requirements for data minimization in system diagnostics