Differential Privacy (DP)

When multiple differentially private computations are performed on the same dataset, the total privacy loss accumulates linearly. If mechanism M1 satisfies ε1-DP and M2 satisfies ε2-DP, the combined release satisfies (ε1 + ε2)-DP. This property forces engineers to track a cumulative privacy budget across all queries, preventing death by a thousand cuts where an adversary reconstructs data by combining many slightly noisy outputs.

When differentially private mechanisms operate on disjoint subsets of the data, the total privacy cost equals the maximum epsilon among the mechanisms, not the sum. If user A's data appears only in partition 1, and user B's data only in partition 2, the overall guarantee is max(ε1, ε2). This property enables efficient scaling of private analytics across sharded databases without exhausting the privacy budget.

Any computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. An adversary with arbitrary auxiliary information cannot reverse-engineer the private input by transforming the noisy output. This closure property is critical: it means data scientists can safely perform arbitrary downstream analysis, visualization, or model training on DP-protected outputs without additional privacy risk.

Differential privacy naturally extends to protect groups of correlated individuals. If a mechanism provides ε-DP for a single record, it provides kε-DP for a group of size k. This property is essential for protecting families, households, or any cluster of records where individual data points are not statistically independent. The degradation is linear, making large-group protection computationally expensive.

The DP guarantee holds regardless of what external knowledge an adversary possesses. Even if an attacker knows every other record in the database, they cannot confidently infer whether a specific target individual was included. This property distinguishes DP from syntactic anonymization techniques like k-anonymity, which catastrophically fail when linked with external datasets.

While basic composition sums epsilons linearly, advanced composition provides tighter bounds for k-fold adaptive queries. For a target δ, the total privacy cost grows proportionally to √(k ln(1/δ)) rather than k, enabling significantly more queries under the same budget. This is the theoretical foundation for practical DP-SGD training, where thousands of gradient steps must remain within a reasonable privacy budget.