Differential Privacy

The privacy budget (ε) is the core metric defining the strength of the privacy guarantee. A lower epsilon value indicates stronger privacy but more noise. It quantifies the maximum divergence in output probability when a single record is added or removed. Key considerations:

• ε < 1 provides strong plausible deniability
• ε > 10 offers weak statistical protection
• The budget is consumed cumulatively across queries
• Once the budget is exhausted, no further queries are allowed

Privacy is achieved by adding carefully calibrated random noise drawn from specific probability distributions, such as the Laplace or Gaussian mechanisms. This noise masks the contribution of any single individual. Mechanism selection depends on:

• Laplace Mechanism: Optimal for L1 sensitivity and pure ε-differential privacy
• Gaussian Mechanism: Used for L2 sensitivity and relaxed (ε, δ)-differential privacy
• The scale of noise is proportional to the query's sensitivity divided by epsilon

Sensitivity measures the maximum possible impact a single record can have on a query's output. It is the key parameter that determines how much noise must be added. Two primary types exist:

• Global Sensitivity: The worst-case change across all possible datasets
• Local Sensitivity: The change specific to a given dataset instance Accurate sensitivity analysis prevents both under-protection and excessive data degradation.

When multiple differentially private analyses are performed on the same dataset, the total privacy loss accumulates. Composition theorems provide formal bounds on this degradation. Fundamental rules include:

• Sequential Composition: The epsilons of independent queries sum linearly
• Parallel Composition: Queries on disjoint data partitions do not accumulate
• Advanced Composition: Provides tighter bounds for Gaussian mechanisms over many queries These theorems prevent privacy budget exhaustion attacks.

A critical property of differential privacy is its immunity to post-processing. Any arbitrary computation applied to the output of a differentially private mechanism does not degrade the privacy guarantee. This means:

• An adversary cannot reverse-engineer the noise by applying transformations
• Results can be safely visualized, rounded, or fed into other algorithms
• No additional privacy budget is consumed by downstream analysis This property ensures that privacy is not a link in a chain that can be broken.

The architecture of trust dictates where noise is injected. Two primary models exist:

• Central DP (Curator Model): A trusted server collects raw data and adds noise to query responses. Provides higher accuracy.
• Local DP (LDP): Noise is added on the individual's device before data is ever transmitted. Eliminates the need for a trusted curator. The choice involves a trade-off between data accuracy and the removal of trusted third parties.

The privacy loss parameter that quantifies the maximum information leakage allowed by a differential privacy mechanism. A lower epsilon (e.g., ε=0.1) provides stronger privacy guarantees but introduces more noise, reducing data utility. An epsilon budget is consumed with each query; once exhausted, the dataset can no longer be queried without risking re-identification. This is the central tuning knob for balancing privacy vs. accuracy in audit log analysis.

The foundational algorithm for achieving ε-differential privacy on numerical queries. It works by adding random noise drawn from a Laplace distribution calibrated to the query's sensitivity—the maximum impact a single record can have on the result. For a query function f and privacy parameter ε, the mechanism returns f(D) + Lap(Δf/ε). This ensures that the output distribution is nearly identical whether or not any individual's data is included.

An alternative to the Laplace mechanism that adds noise from a Gaussian (normal) distribution to achieve (ε, δ)-approximate differential privacy. The δ parameter allows a small probability of violating pure ε-privacy, which enables tighter utility bounds for complex queries. This mechanism is the workhorse behind the DP-SGD (Differentially Private Stochastic Gradient Descent) algorithm used to train deep learning models on sensitive audit data without memorizing individual records.

Two distinct trust models for deploying differential privacy. In Global DP (or Central DP), a trusted curator collects raw data and applies noise to query outputs. This yields high accuracy but requires trusting the central server. In Local DP, noise is applied by each individual before data leaves their device, ensuring the curator never sees raw data. Local DP is used by Apple and Google for telemetry collection but requires significantly larger datasets to achieve comparable utility.

The process of determining the maximum influence a single record can exert on a query's output, denoted as L1 sensitivity (Δf) for the Laplace mechanism or L2 sensitivity (Δ₂f) for the Gaussian mechanism. For a simple counting query, Δf=1. For an averaging query, Δf = (max - min)/n. Accurate sensitivity calibration is critical: overestimation adds unnecessary noise, while underestimation breaks the privacy guarantee.

A cryptographic technique that allows computation directly on encrypted data without decryption. When combined with differential privacy, it enables secure multi-party computation of audit statistics: data remains encrypted during processing, and differential privacy noise is applied to the encrypted result before decryption. This eliminates the trusted curator requirement in the global DP model, providing cryptographic enforcement of the privacy guarantee.