Differentially Private Data Publishing

The defining constraint of non-interactive publishing is the one-time expenditure of a total privacy budget (ε). The curator must decide a priori how to allocate this budget across all statistics or synthetic records in the release. Once the budget is exhausted, no further queries are permitted on the original data. This contrasts sharply with interactive mechanisms, where the budget is consumed incrementally per query. The composition theorem guarantees that the total privacy loss of the published output is bounded by the allocated ε, regardless of how many analyses the downstream consumer performs on the sanitized release.

Noise calibration in non-interactive publishing relies on the global sensitivity of the entire output function, not individual queries. The curator must compute the maximum possible change in the complete published dataset or set of statistics when a single record is added or removed. For high-dimensional data releases, this often requires bounding the L1 sensitivity (for the Laplace mechanism) or L2 sensitivity (for the Gaussian mechanism) of complex transformations. Techniques like histogram binning and grid partitioning are used to control sensitivity before noise injection.

A critical property of differentially private non-interactive publishing is post-processing immunity. Once a dataset or statistical summary is released with a valid ε-differential privacy guarantee, any arbitrary computation performed by the end-user on that output cannot degrade the privacy guarantee. This means data analysts can run unlimited regressions, visualizations, and machine learning models on the published data without ever increasing the privacy loss for the original individuals. The privacy protection is future-proof against any analysis technique.

A dominant paradigm in non-interactive publishing is the release of differentially private synthetic data. Instead of releasing noisy answers to pre-specified queries, the curator trains a generative model (e.g., a DP-GAN or Bayesian network) under differential privacy and then releases samples from that model. The goal is to preserve the joint distribution of the sensitive source data, enabling downstream analysts to perform exploratory analysis as if they had the real data. Key challenges include maintaining fidelity for high-dimensional categorical variables and rare combinations.

Because the curator cannot anticipate every future analysis, non-interactive publishing often employs workload-aware strategies. The curator selects a representative set of queries (a workload) that captures the expected analytical needs of downstream consumers and optimizes the noise injection to minimize total error on that workload. Techniques include:

• Matrix mechanism: Optimizes noise for linear queries by selecting a strategy matrix.
• Multiplicative weights: Iteratively refines a synthetic distribution to match noisy query answers.
• Column-wise privacy: Applies separate privacy budgets to different attributes based on their sensitivity.

The fundamental tension in non-interactive publishing is the utility-privacy trade-off. A small ε (strong privacy) requires large noise, which can destroy the statistical signal, especially for sparse or high-dimensional data. Conversely, a large ε (weak privacy) preserves utility but risks reconstruction attacks. The curator must select ε based on the sensitivity of the data and the intended use case. For census data, ε values between 0.1 and 10 are common. For highly sensitive medical data, ε < 1 is often mandated. The Rényi differential privacy (RDP) framework provides tighter composition bounds, allowing more utility for the same privacy guarantee.

The finite, quantifiable limit on total privacy loss allocated for a data release. Every query consumes a portion of the budget. Once exhausted, further access must be denied to prevent reconstruction attacks. A smaller epsilon (e.g., ε=0.1) provides stronger privacy than a larger one (e.g., ε=10).

• Sequential Composition: Total privacy loss sums linearly across queries.
• Parallel Composition: Querying disjoint data subsets only consumes the maximum single-query budget.
• Budget Depletion: The point at which the cumulative privacy loss exceeds the acceptable threshold, halting analysis.

The maximum change in a query's output caused by adding or removing a single record. Sensitivity directly determines the scale of noise required to achieve differential privacy.

• L1 Sensitivity: Used for the Laplace mechanism; measures absolute difference.
• L2 Sensitivity: Used for the Gaussian mechanism; measures Euclidean distance.
• High Sensitivity: Queries like 'count' have low sensitivity (1); 'sum' of unbounded values has high sensitivity, requiring more noise and reducing utility.

The foundational mechanism for achieving pure ε-differential privacy. It adds noise drawn from a Laplace distribution centered at zero, with a scale parameter calibrated to L1 sensitivity / ε.

• Optimality: Optimal for a single count query under pure ε-DP.
• Tail Behavior: Has heavier tails than the Gaussian distribution, providing stronger privacy for outliers.
• Use Case: Ideal for releasing numeric aggregates like counts and sums where pure differential privacy is required.

A mechanism that adds noise from a Gaussian (normal) distribution calibrated to the L2 sensitivity. It achieves (ε, δ)-approximate differential privacy, where δ represents a small failure probability.

• Tighter Composition: Enables more efficient cumulative privacy accounting than the Laplace mechanism over many iterations.
• DP-SGD Foundation: The core noise mechanism used in Differentially Private Stochastic Gradient Descent for training deep learning models.
• Trade-off: Allows for higher utility than the Laplace mechanism at the cost of a small δ probability of catastrophic privacy failure.

A resilience property guaranteeing that any arbitrary computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. An adversary with unlimited auxiliary information cannot reverse-engineer the noise.

• Arbitrary Computation: Mapping, rounding, or feeding the output into another algorithm does not degrade privacy.
• Safe Release: Once a statistic is published with DP, it can be freely visualized, shared, and analyzed without additional privacy risk.
• Contrast: This property does not hold for anonymization techniques like k-anonymity, which are vulnerable to linkage attacks.

Formal rules quantifying how the total privacy budget degrades when multiple differentially private mechanisms are applied to the same dataset.

• Basic Sequential Composition: The total ε is the sum of individual ε values.
• Advanced Composition: Provides a tighter bound (sub-linear growth) for (ε, δ)-DP mechanisms, enabling more queries.
• Moments Accountant: A state-of-the-art technique tracking higher-order moments of the privacy loss random variable, used in DP-SGD to compute tight, non-trivial privacy guarantees over thousands of training iterations.