Central Differential Privacy

The trusted curator (or server) is a central entity that holds the complete, raw dataset. This model assumes the curator will faithfully apply the differentially private mechanism before releasing any query results, statistics, or trained models. The trust is placed in the curator's execution of the algorithm, not in its discretion over the raw data.

• Key Implication: Data contributors must trust the curator with their sensitive information, as privacy is applied post-collection.
• Contrast with LDP: In local differential privacy, no entity ever sees the raw data, as perturbation happens on the client device.

Privacy mechanisms are applied after data has been collected and centralized. The curator computes the true answer to a query (e.g., an average, sum, or model gradient) and then injects calibrated noise to the result before release.

• Mechanism Workflow: 1) Receive raw data → 2) Compute exact aggregate → 3) Calculate sensitivity → 4) Add noise (e.g., Laplace, Gaussian) → 5) Release noised result.
• Advantage: This allows for much higher utility (accuracy) for the same privacy budget (ε) compared to local models, as noise is added only once to the aggregate, not to each individual data point.

The model provides a rigorous, mathematical guarantee. For any two adjacent datasets (differing by one individual's data), the probability distribution of the mechanism's output is nearly identical.

• Pure DP (ε-DP): Uses the Laplace Mechanism. Guarantees that the log-likelihood ratio of any output is bounded by ε.
• Approximate DP ((ε, δ)-DP): Uses the Gaussian Mechanism. Allows a small probability δ (e.g., 1e-5) of the ε guarantee failing, which enables adding less noise for complex functions like gradient descent.
• Interpretation: A smaller ε means stronger privacy; δ should be cryptographically small (<< 1/n).

The amount of noise added is proportional to the global sensitivity of the query function. Sensitivity measures the maximum possible change in the query's output when a single individual's data is added or removed.

• L1 Sensitivity (Δf): Used for the Laplace Mechanism. Δf = max ||f(D) - f(D')||₁.
• L2 Sensitivity (Δ₂f): Used for the Gaussian Mechanism. Δ₂f = max ||f(D) - f(D')||₂.
• Example: For a counting query ("how many patients have condition X?"), the sensitivity is 1. For an average, sensitivity depends on the data's bounded range.

Multiple queries consume a cumulative privacy budget. The curator must track total privacy loss using composition theorems.

• Basic Composition: Sequential queries have additive ε (ε_total = ε₁ + ε₂ + ...).
• Advanced Composition: Provides tighter bounds, allowing for more queries. Rényi DP (RDP) and zCDP are modern accounting methods used for iterative algorithms like DP-SGD.
• Privacy Accounting: A critical subsystem that tracks consumed (ε, δ) to ensure the total never exceeds a pre-defined budget, after which the data cannot be queried further.

A foundational property: any analysis performed on the output of a differentially private mechanism cannot weaken its privacy guarantee. If M(D) is (ε, δ)-DP, then for any function g (deterministic or randomized), g(M(D)) is also (ε, δ)-DP.

• Practical Consequence: Allows safe downstream use of private outputs. A private aggregate can be further analyzed, transformed, or used as input to another process without requiring new privacy calculations.
• Limitation: Immunity only holds if no additional information about the raw dataset is used. Combining a private output with external non-private data is allowed but doesn't retroactively privatize the external data.

Local Differential Privacy is a distributed privacy model where each data owner perturbs their own data with a differentially private mechanism before sending it to an untrusted data curator. This provides a strong, client-side guarantee, contrasting with Central DP's trusted curator model.

• Key Difference: In LDP, privacy is enforced at the source; the curator never sees raw data. In Central DP, the curator sees raw data but privatizes outputs.
• Use Case: LDP is foundational for privacy in scenarios like Google's RAPPOR for crowd-sourced statistics and Apple's emoji suggestion, where the server cannot be fully trusted.

Differential Privacy is the overarching, rigorous mathematical framework that defines privacy loss. It provides a quantifiable guarantee that the inclusion or exclusion of any single individual's data has a negligible effect on the output of an analysis.

• Formal Guarantee: An algorithm is (ε, δ)-differentially private if for any two adjacent datasets differing by one record, the probability of any output changes by at most a factor of e^ε, plus a small δ.
• Foundation: Central DP is a specific model (trusted curator) that implements the general DP framework. All DP guarantees, including composition and post-processing, apply.

The Laplace Mechanism and Gaussian Mechanism are the core algorithmic tools for achieving Central DP. They work by adding calibrated random noise to the true output of a function (e.g., a query count or an average).

• Laplace Mechanism: Achieves pure ε-DP. Adds noise drawn from a Laplace distribution, where the scale (λ) is set by the function's L1 sensitivity divided by ε.
• Gaussian Mechanism: Achieves the relaxed (ε, δ)-DP. Adds noise from a Gaussian distribution, where the scale (σ) is set by the function's L2 sensitivity and the chosen (ε, δ) values. It often allows for less noise than Laplace for the same utility when δ > 0.

A Privacy Budget is a finite allocation of the privacy parameter ε (and δ) that is consumed over multiple queries or analysis steps. Privacy Accounting is the rigorous process of tracking this cumulative consumption.

• Composition: Sequential queries consume the budget. Basic composition adds ε values; advanced composition (e.g., Moment Accountant, Rényi DP) allows for tighter tracking.
• Critical for Central DP: The trusted curator must use accounting to ensure the total privacy loss across all released statistics never exceeds the pre-defined, global budget, preventing privacy degradation over time.

Sensitivity is the maximum possible change in the output of a function when a single individual's data is added or removed from the dataset. It is the fundamental determinant of how much noise must be added for a DP guarantee.

• L1 Sensitivity (Δf): Used for the Laplace Mechanism. The maximum absolute change in the function's output: Δf = max ||f(D) - f(D')||₁.
• L2 Sensitivity (Δ₂f): Used for the Gaussian Mechanism. The maximum Euclidean norm change: Δ₂f = max ||f(D) - f(D')||₂.
• Example: For a simple count query, the sensitivity is 1. For an average, sensitivity depends on the bounded range of the data.

The Trusted Curator Model is the architectural assumption underlying Central DP. It posits the existence of a single, secure entity that has direct access to the raw, sensitive dataset and is responsible for applying differentially private mechanisms before releasing any information.

• Contrast with Local Model: This model assumes the curator is trusted not to misuse the raw data, whereas the local model assumes no such trust.
• Implications: Enables higher data utility for a given privacy guarantee compared to LDP, as noise is added only once to aggregated results rather than to each individual datum. It is the model assumed by the U.S. Census Bureau for programs like OnTheMap.