Privacy Budget

Epsilon (ε) is the privacy loss parameter that quantifies the strength of the privacy guarantee. A lower epsilon value indicates stronger privacy protection but introduces more noise, reducing data utility.

• ε = 0: Absolute privacy—output is completely independent of any individual's data, rendering results useless.
• ε < 1: Strong privacy protection, suitable for highly sensitive datasets like medical records.
• ε = 1–10: Moderate privacy, balancing utility for aggregate analytics.
• ε > 10: Weak privacy guarantee, where individual influence on outputs becomes detectable.

The epsilon value represents the maximum divergence between outputs on neighboring datasets differing by a single record.

Sequential composition is the fundamental theorem stating that privacy loss accumulates additively across multiple queries on the same dataset.

If you execute query A with privacy budget ε₁ and query B with privacy budget ε₂, the total privacy cost is ε₁ + ε₂. This linear accumulation is why the budget is a finite resource that must be carefully managed.

• A data scientist running 100 queries at ε = 0.1 each consumes a total budget of ε = 10.
• This property forces query planning—you cannot simply run unlimited analyses.
• Once the total budget cap is reached, the dataset must be locked to prevent further privacy leakage.

Parallel composition provides a critical optimization: when queries operate on disjoint, non-overlapping subsets of data, the total privacy cost equals the maximum of the individual epsilons, not their sum.

• If you partition a dataset by user ID and run a query on each partition at ε = 0.5, the total cost is ε = 0.5, not ε = 0.5 × n.
• This property enables scalable private analytics by partitioning data into independent shards.
• It relies on strict data isolation—any overlap between partitions invalidates the guarantee and reverts to sequential composition.

Post-processing immunity guarantees that once a result is computed under differential privacy, no further computation on that result can weaken the privacy guarantee.

• An adversary cannot "reverse-engineer" privacy by applying arbitrary functions to the noisy output.
• This property is resilience to auxiliary information—even if an attacker possesses external datasets, the privacy bound holds.
• It enables safe sharing of differentially private outputs: analysts can visualize, aggregate, or transform results without consuming additional budget.
• This is a one-way property: it protects outputs, not the original data.

When the cumulative privacy loss reaches the predefined global epsilon cap, the system must enforce a hard lockout—no further queries are permitted on that dataset.

• This is not a soft guideline; it is a mathematical necessity to uphold the privacy guarantee.
• Administrators must define a budget refresh policy: whether the budget resets periodically (e.g., annually), never resets, or requires re-consent.
• Exceeding the budget constitutes a privacy violation equivalent to exceeding a consented processing purpose.
• Systems typically implement budget accounting modules that track consumption in real-time and reject queries that would exceed the cap.

While basic composition is linear, advanced composition theorems provide tighter bounds for multiple adaptive queries, accounting for the probability of privacy failure (delta, δ).

• For k queries, the total privacy cost is bounded by approximately ε_total ≈ ε√(2k ln(1/δ)) + kε(e^ε - 1) rather than kε.
• This sub-linear scaling allows significantly more queries under the same total budget when a small failure probability δ is acceptable.
• (ε, δ)-differential privacy relaxes pure ε-differential privacy by allowing a δ probability of catastrophic privacy failure.
• Typical values: δ < 1/n² where n is the dataset size, ensuring the failure probability is cryptographically negligible.

The core unit of the privacy budget, representing the privacy loss parameter. A smaller ε (e.g., 0.1) provides stronger privacy guarantees but requires more noise, reducing utility. A larger ε (e.g., 10) yields higher accuracy but weaker privacy. Key thresholds:

• ε < 1: Strong privacy for high-sensitivity data
• 1 < ε < 10: Moderate, practical for many enterprise applications
• ε > 10: Weak guarantees, approaching non-private analysis Composability theorems dictate that ε accumulates additively across sequential queries.

The foundational privacy principle that directly constrains the privacy budget. By collecting only the minimum necessary attributes and records required for a specified purpose, the attack surface and total sensitivity of the dataset are reduced. This enables a tighter ε allocation per query. Techniques include:

• Attribute suppression: Dropping unnecessary columns before training
• Record sampling: Using a statistically valid subset rather than the full population
• Aggregation: Pre-computing summary statistics to avoid raw data exposure

The architectural enforcement of purpose limitation through logical or physical segregation of datasets. Each model or business function receives its own isolated data partition with an independent privacy budget. This prevents cross-context budget depletion, where a high-ε query on one project consumes the shared budget needed by another. Implementation patterns include:

• Database-level tenancy: Separate schemas or instances per purpose
• Row-level security: Policy-based filtering enforced at query time
• Air-gapped environments: Physically disconnected infrastructure for high-sensitivity workloads

A cryptographic scheme enabling computation directly on ciphertext, producing encrypted results that decrypt to the correct plaintext output. When combined with a privacy budget, it allows training on encrypted data without ever exposing raw records to the compute environment. The privacy budget governs the information leakage through the model outputs, while homomorphic encryption protects the data in use. Schemes include:

• Partially Homomorphic Encryption (PHE): Supports only addition or multiplication
• Fully Homomorphic Encryption (FHE): Supports arbitrary computation, though with significant computational overhead