Privacy Budget (Epsilon Budget)

The privacy budget is represented by the parameter epsilon (ε), a non-negative real number. It provides a provable upper bound on privacy loss, moving privacy from a qualitative promise to a mathematical guarantee. A smaller ε (e.g., 0.1) indicates stronger privacy but more noise, while a larger ε (e.g., 10) indicates weaker privacy but higher utility. This finite resource must be carefully allocated across all queries to a dataset.

• ε = 0: Perfect, absolute privacy (output is independent of any single record).
• ε ≤ 1: Typically considered a strong privacy guarantee.
• ε > 10: Weak privacy guarantee; significant information leakage is possible.

The total privacy loss accumulates additively across multiple computations on the same dataset. If you run a query with privacy loss ε₁, followed by another with ε₂, the total privacy loss is ε₁ + ε₂. This is the fundamental accounting rule of a privacy budget.

• Analogy: Think of it as a bank account with a fixed balance. Each query "withdraws" a specific ε amount.
• Implication: Data scientists must track cumulative ε to ensure the total does not exceed the pre-defined global budget, preventing gradual privacy erosion through repeated queries.

When queries operate on disjoint, non-overlapping subsets of the data, the total privacy cost is the maximum of the individual costs, not the sum. This property is critical for scaling differential privacy to large, partitioned datasets.

• Example: If a hospital's patient data is partitioned by department, and a query on cardiology data costs ε=0.5 and a query on oncology data costs ε=0.7, the total cost is ε=0.7, not 1.2.
• Key Requirement: The subsets must be strictly disjoint. If any record appears in both partitions, sequential composition rules apply.

Once a result is computed under a differential privacy guarantee, any subsequent computation on that result cannot degrade the privacy guarantee. An adversary cannot increase privacy loss by performing arbitrary post-hoc analysis on a differentially private output.

• Practical Meaning: A differentially private statistic can be safely published, visualized, or used as input to another model without any additional privacy cost.
• Contrast: This property does not protect against re-identification if the original output was not sufficiently private; it only guarantees that post-processing does not make it worse.

Differential privacy's standard guarantee protects the presence or absence of a single record. Group privacy extends this to a group of size k. If a mechanism provides ε-differential privacy for one record, it provides k·ε differential privacy for a group of k records.

• Intuition: Protecting a family of 4 from inference requires a budget 4 times larger than protecting an individual.
• Risk: This linear degradation means that while DP protects against singling out an individual, it offers weaker protection against inferring attributes of a correlated group, such as all members of a household.

The privacy budget directly governs the fundamental tension between accuracy and privacy. Injecting noise to achieve a lower ε inevitably reduces the statistical utility of the output. This is not a bug but an inherent, mathematically proven constraint.

• Mechanism: The Laplace or Gaussian mechanisms add noise scaled by sensitivity/ε. As ε decreases, noise variance increases.
• Strategy: The goal is to find the optimal ε that satisfies regulatory requirements (e.g., HIPAA expert determination) while preserving sufficient signal for the federated model to converge effectively.

A privacy breach where an attacker reconstructs sensitive training data or statistical features from a model's parameters or confidence scores. This attack directly exploits an exhausted or absent privacy budget.

• Gradient inversion: Reconstructs input images from shared gradients in federated learning
• Confidence score exploitation: Uses model outputs to infer class representatives
• A properly calibrated epsilon budget bounds the success rate of such reconstruction
• Demonstrates why tracking cumulative privacy loss across training rounds is critical

An adversarial technique to determine whether a specific data record was part of a model's training dataset. This attack is the canonical metric for evaluating the effectiveness of a privacy budget.

• Attacker trains shadow models to recognize differences in model confidence on members vs. non-members
• Overfitting dramatically increases vulnerability to this attack
• Differential privacy's ε parameter directly bounds the attacker's advantage
• A privacy budget exhausted too quickly leaves later training rounds vulnerable

An attack that reconstructs private local training data from the shared model gradients during collaborative learning. In federated settings, this is the primary threat that the privacy budget is designed to mitigate.

• Deep Leakage from Gradients (DLG) : Iteratively optimizes dummy inputs to match observed gradients
• Can reconstruct pixel-level images and token-level text from language model gradients
• Adding DP noise to gradients before sharing directly consumes the privacy budget to defeat this attack
• The ε value determines the reconstruction error floor

A cryptographic scheme that permits direct computation on encrypted data, producing an encrypted result that decrypts to the correct output. Unlike differential privacy, HE provides cryptographic security rather than statistical privacy, and does not consume a privacy budget.

• Additive HE: Supports addition on ciphertexts (e.g., Paillier)
• Fully Homomorphic Encryption (FHE) : Supports arbitrary computation but is computationally expensive
• Often combined with DP: HE protects data in transit, DP protects the final model release
• No epsilon tracking required, but introduces significant computational overhead