Differential Privacy

The core guarantee: the output of a differentially private mechanism is statistically indistinguishable whether or not any single individual's data was included. This is achieved by injecting calibrated noise proportional to the query's sensitivity. An adversary observing the output cannot confidently infer any individual's presence, as the same output is nearly as likely to have come from a dataset without that individual. This provides a formal, mathematical definition of privacy rather than a heuristic one.

When multiple differentially private computations are performed on the same dataset, the total privacy loss accumulates linearly. If mechanism M1 satisfies ε1-differential privacy and M2 satisfies ε2-differential privacy, their sequential application satisfies (ε1 + ε2)-differential privacy. This property is fundamental to privacy accounting, allowing engineers to track and bound the total privacy expenditure of a complex ML training pipeline within a predefined privacy budget.

When differentially private mechanisms are applied to disjoint subsets of a dataset, the total privacy cost is bounded by the maximum ε of any single mechanism, not their sum. For example, computing a private statistic on user data partitioned by state: the overall privacy guarantee is the worst-case ε applied to any single state's data. This property is crucial for federated learning and distributed analytics, where computations occur on siloed data partitions.

Any computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. An adversary with arbitrary auxiliary information cannot perform any transformation, analysis, or machine learning on the noisy output to reverse-engineer the presence of an individual. This property ensures that once data is privatized, it remains safe for any downstream use, including visualization, statistical analysis, or sharing with untrusted third parties.

Differential privacy naturally extends to protect groups of correlated individuals. A mechanism that provides ε-differential privacy for a single individual provides kε-differential privacy for a group of size k. This means the privacy guarantee degrades gracefully and predictably with group size. Protecting against adversaries who may have access to multiple correlated records from family members or linked accounts requires accounting for this linear scaling factor.

The guarantee holds against adversaries with arbitrary external knowledge. Unlike anonymization techniques like k-anonymity, which catastrophically fail when linked with public datasets, differential privacy makes no assumptions about what the adversary already knows. Even if an attacker knows every other record in the dataset except the target's, they still cannot determine whether the target's record was included. This property makes it the gold standard for provable privacy.

The privacy budget is a quantifiable limit on total privacy loss, parameterized by epsilon (ε) . A lower epsilon (e.g., 0.1) provides stronger privacy by forcing more noise into the computation, while a higher epsilon (e.g., 10) allows for higher utility but weaker guarantees.

• Composition: Privacy loss accumulates additively across multiple queries or training steps.
• Exhaustion: Once the budget is spent, no further analysis can be performed on the data without violating the guarantee.
• Delta (δ) : Often paired with epsilon as (ε, δ)-differential privacy, allowing a small probability of catastrophic failure.

A fundamental building block of differential privacy that achieves (ε, δ)-DP by adding noise drawn from a Gaussian (normal) distribution to the output of a query.

• Calibration: The noise scale (σ) is calibrated to the L2 sensitivity of the function—the maximum change in output caused by adding or removing a single record.
• Comparison to Laplace: The Gaussian mechanism is preferred for high-dimensional data and composition, as it provides tighter privacy accounting under advanced composition theorems.
• Use Case: The primary noise mechanism used in DP-SGD for perturbing gradients.

Privacy accounting is the rigorous process of tracking cumulative privacy loss over a sequence of differentially private operations. It ensures the total loss remains within a predefined budget.

• Moments Accountant: A specific technique that tracks the moment-generating function of the privacy loss random variable, providing tight bounds on overall cost.
• Rényi Differential Privacy (RDP) : A relaxation based on Rényi divergence that simplifies composition analysis and is widely used in modern DP libraries like Opacus and TF Privacy.
• Subsampling Amplification: Randomly sampling a subset of data before applying a DP mechanism provides a stronger overall guarantee than processing the full dataset.

Sensitivity is the maximum change in a function's output caused by adding or removing a single record. It is the critical parameter for calibrating noise in any differential privacy mechanism.

• L1 Sensitivity: Used for the Laplace mechanism; the maximum absolute difference in output measured by the L1 norm.
• L2 Sensitivity: Used for the Gaussian mechanism; the maximum Euclidean distance between outputs on adjacent datasets.
• Global vs. Local: Global sensitivity considers all possible adjacent datasets, while local sensitivity is dataset-specific but can leak information if used directly.