Differential Privacy

The privacy budget (ε) is the central parameter controlling the privacy-utility trade-off. A lower epsilon provides stronger privacy but adds more noise.

• ε = 0: Absolute privacy, but zero utility (pure noise).
• ε = 0.1 to 1: Strong privacy, suitable for high-sensitivity data like medical records.
• ε = 1 to 10: Moderate privacy, common in industry deployments.
• ε > 10: Weak privacy guarantees; effectively no meaningful protection.

The budget is consumed with each query. Once exhausted, no further queries are permitted on that dataset without risking privacy violation.

When multiple differentially private mechanisms are applied to the same dataset, their privacy budgets sum linearly.

If you run a query with budget ε₁ and another with budget ε₂, the total privacy cost is ε₁ + ε₂.

• This forces careful accounting across an entire analysis session.
• A privacy accountant tracks cumulative spend to enforce a global epsilon ceiling.
• Prevents the "death by a thousand queries" attack where an adversary combines many low-sensitivity queries to reconstruct private data.

When queries operate on disjoint subsets of the data, the privacy cost does not accumulate. The total cost equals the maximum of the individual budgets, not their sum.

• If you partition a dataset by user ID and query each partition with budget ε, the total cost remains ε.
• This property enables efficient, scalable private analytics on sharded data.
• Critical for federated learning, where each client's data is a disjoint partition.
• Contrasts with sequential composition to form the foundation of privacy accounting in complex systems.

Any computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. Privacy is not degraded by post-processing.

• An adversary cannot "un-noise" the result through arbitrary computation.
• Enables safe sharing of private outputs: visualizations, ML model weights, or summary statistics remain protected.
• This property holds without any additional assumptions about the post-processing function.
• Formally: If M(x) satisfies ε-differential privacy, then f(M(x)) also satisfies ε-differential privacy for any function f.

The standard definition protects against adversaries distinguishing datasets that differ in a single record. Group privacy extends this to groups of size k.

• Protecting a group of k individuals requires scaling the privacy budget: ε_group = k × ε.
• A mechanism that is ε-differentially private for individuals is kε-differentially private for groups of size k.
• This reveals a fundamental limitation: protecting correlated records (e.g., family members) is exponentially harder.
• Important for scenarios where multiple records per individual exist or when protecting household-level statistics.

The amount of noise required is determined by the sensitivity of the query function—the maximum change in output when a single record is added or removed.

• L1 Sensitivity (Global): The maximum absolute difference in query output across all possible neighboring datasets.
• L2 Sensitivity: The Euclidean distance version, used for Gaussian noise mechanisms.
• Local Sensitivity: The maximum change for a specific dataset, which can leak information if used directly.
• Smooth Sensitivity: A smoothed upper bound on local sensitivity that prevents leakage while enabling less noise for "well-behaved" queries like the median.

Apple uses a system called Private Count Mean Sketch to collect emoji usage, health data, and web domain preferences from billions of devices. The system applies local differential privacy by hashing data and injecting noise on-device before transmission. This ensures that even Apple's servers cannot reconstruct an individual user's typing habits or browsing history, while still allowing aggregate trend analysis for product improvement.

During the pandemic, Google published Community Mobility Reports to help public health officials track movement trends. The underlying technology was differential privacy with a temporal smoothing mechanism. By adding carefully calibrated Laplace noise to location history aggregates, Google provided statistically valid insights into retail footfall and workplace occupancy without revealing any single user's trajectory or home location.

The 2020 Census implemented TopDown Algorithm, a formal differential privacy framework, to protect respondent identities. Instead of traditional swapping methods, the Bureau injected noise into the microdata detail tables. This marked the first time a national statistical office used a provable mathematical guarantee to balance redistricting accuracy with the legal mandate to prevent reconstruction of individual household data from published statistics.

LinkedIn employs differential privacy to protect member data when providing audience engagement metrics to advertisers and content creators. The system adds noise to aggregate counts of profile views, post impressions, and search appearances. This prevents advertisers from inferring the specific identity of a viewer through repeated micro-targeted queries, a technique known as differentially private reporting.

Differentially Private Stochastic Gradient Descent (DP-SGD) is the standard algorithm for training neural networks with privacy guarantees. It works by:

• Clipping gradients: Bounding the influence of any single training example.
• Adding noise: Injecting Gaussian noise to the clipped gradients. This allows hospitals to collaboratively train diagnostic models or keyboard apps to learn new words without centralizing raw sensitive data.