Preserving Target Distributions With Differentially Private Count Mechanisms

Nitin Kohli (Paper author · UC Berkeley), Paul Laskowski (Paper author · UC Berkeley)

Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 3 · Beaver

Overview

In this insightful talk from PETS, Paul Laskowski, co-authored with Nitin Kohli, both from UC Berkeley, introduced a critical re-evaluation of how differentially private count mechanisms are designed and assessed. The presentation, titled "Preserving Target Distributions With Differentially Private Count Mechanisms," addresses a fundamental limitation in existing privacy-preserving data publication techniques, specifically concerning tables of counts. While current approaches primarily focus on maintaining the accuracy of individual counts, they often inadvertently distort the overall statistical distribution of these counts, leading to skewed or misleading analytical results for certain types of queries.

Watch on YouTube · Slides

Visual summary for Preserving Target Distributions With Differentially Private Count Mechanisms by Nitin Kohli, Paul Laskowski
Visual summary for Preserving Target Distributions With Differentially Private Count Mechanisms by Nitin Kohli, Paul Laskowski

Key moments

  1. 0:43 Introduction to tables of counts and standard privatization
  2. 2:00 Two types of questions: category-based vs. distribution
  3. 3:42 New criterion: preserving count distribution accuracy
  4. 6:17 The two-stage differentially private framework
  5. 8:00 Optimization challenge: mechanisms as convex polytopes
  6. 9:07 Epsilon scales enable faster constructor algorithms
  7. 10:14 Summary of contributions and positive experimental results

Preserving Target Distributions With Differentially Private Count Mechanisms

Speakers: Nitin Kohli (Paper author, UC Berkeley); Paul Laskowski (Paper author, UC Berkeley)

Conference: PETS

YouTube: https://www.youtube.com/watch?v=bCePtgJeHLk

Overview

In this insightful talk from PETS, Paul Laskowski, co-authored with Nitin Kohli, both from UC Berkeley, introduced a critical re-evaluation of how differentially private count mechanisms are designed and assessed. The presentation, titled "Preserving Target Distributions With Differentially Private Count Mechanisms," addresses a fundamental limitation in existing privacy-preserving data publication techniques, specifically concerning tables of counts. While current approaches primarily focus on maintaining the accuracy of individual counts, they often inadvertently distort the overall statistical distribution of these counts, leading to skewed or misleading analytical results for certain types of queries.

The core contribution of this work lies in identifying and addressing the need for accuracy of distribution as a distinct and equally important performance criterion alongside the traditional accuracy of counts. Laskowski and Kohli propose a novel two-stage framework that aims to balance these two objectives, ensuring that privatized data remains useful for a broader range of analytical tasks. Their research introduces a sophisticated mathematical theory, leveraging the concept of "epsilon scales" to construct differentially private mechanisms that can preserve a target distribution without compromising privacy guarantees.

This talk is particularly significant for data publishers, privacy engineers, and researchers who rely on releasing aggregated count data while upholding strong privacy standards. By demonstrating that existing mechanisms can subtly undermine the utility of privatized data for distribution-based analyses, the authors highlight a crucial gap in current differential privacy practices. Their proposed framework offers a pathway to publishing more versatile and statistically faithful private datasets, ultimately enhancing the value of differentially private information for a diverse set of data consumers without sacrificing the robust privacy assurances of differential privacy.

Background

▶ Watch: Introduction to tables of counts and standard privatization (0:43)

Tables of counts are a ubiquitous data format across various domains, from demographic statistics to network traffic logs, where categories (e.g., states, countries, user sessions) are associated with numerical counts (e.g., number of residents, connections, participants). The imperative to privatize such data, especially when it contains sensitive individual information, has led to the widespread adoption of differential privacy (DP). The standard approach to privatizing tables of counts, as widely documented in privacy literature, typically involves adding independent random noise to each individual count. This noisy data is then often post-processed, for instance, by truncating negative values to zero, to ensure a plausible output.

Historically, the evaluation of these differentially private count mechanisms has predominantly centered on accuracy of counts. This metric assesses how close the published noisy count is to the true count, often quantified using measures like mean squared error. The underlying assumption is that if individual counts are accurate enough, the overall utility of the dataset is preserved.

However, Laskowski and Kohli challenge this singular focus by pointing out that real-world data consumers ask different types of questions. While some queries are category-based (e.g., "How many people live in Alberta?"), requiring a direct lookup of a specific category's count, many others are count distribution questions. These include queries like "What fraction of US flights have zero air marshals on board?", "What fraction of company boards have more than two women?", or "What is the average number of students overseen by each guidance counselor in the US?". Crucially, these latter types of questions do not require the names of the categories; they are concerned with the statistical properties of the counts themselves—their frequency, distribution, and overall shape. Such questions fundamentally rely on the distribution of counts, which can be visualized as a histogram where each bin I represents the number of categories that have exactly I individuals.

The critical problem identified by the authors is that all available differentially private algorithms, while aiming for count accuracy, inadvertently distort this underlying distribution of counts. A prominent example cited is the truncated geometric mechanism, which tends to inflate the number of zeros in the output dataset. This distortion means that analyses dependent on the shape or characteristics of the count distribution—such as identifying common count values, calculating percentiles, or understanding the overall spread of activity—can yield inaccurate or misleading results, even if individual counts appear reasonably accurate. This discrepancy highlights a fundamental trade-off: optimizing solely for individual count accuracy can come at the expense of preserving the aggregate statistical properties vital for broader analytical utility. The motivation for this work thus became to design privatization methods that explicitly preserve this distribution of counts, aiming for a balance across accuracy of distribution, accuracy of counts, and practical runtime efficiency.

Key Findings

▶ Watch: New criterion: preserving count distribution accuracy (3:42)

The research presented by Paul Laskowski and Nitin Kohli introduces several pivotal findings that address the limitations of existing differentially private count mechanisms:

  1. Identification of Accuracy of Distribution as a Key Metric: The talk highlights that accuracy of distribution is a distinct and often overlooked performance criterion crucial for many real-world analytical tasks. Unlike traditional accuracy of counts, which focuses on individual count fidelity, distribution accuracy assesses how well the overall statistical shape and properties of the counts are preserved after privatization.
  2. Inherent Distortion by Existing DP Mechanisms: A significant finding is that current differentially private algorithms, while designed to protect individual privacy, invariably distort the underlying distribution of counts. This distortion, exemplified by the inflated number of zeros produced by mechanisms like the truncated geometric mechanism, can lead to inaccurate conclusions for analyses that rely on the aggregate statistical properties of the data.
  3. A Novel Two-Stage Framework: To overcome this distortion, the authors propose a two-stage framework for privatizing tables of counts. This framework separates the process of privatizing the distribution itself from the subsequent application of a count mechanism, allowing for a more deliberate balance between accuracy of distribution and accuracy of counts.
  4. Mathematical Theory of Count Mechanism Fixed Points: The work introduces a sophisticated mathematical theory representing count mechanisms as transition matrices (T). A key insight is the concept of a fixed point (Z), where applying the mechanism to a distribution Z results in Z itself (Z = Z * T). This theoretical construct defines mechanisms that inherently preserve a specific target distribution.
  5. Decomposition into Epsilon Scales: A major mathematical breakthrough is the discovery that the set of all differentially private mechanisms that preserve a given distribution (a convex polytope) can be expressed as a conic combination of simpler building blocks called epsilon scales. This decomposition provides a foundation for designing more efficient algorithms.
  6. Development of Faster Constructor Algorithms: Building on the epsilon scales theory, the authors designed new constructor algorithms that can efficiently select and build transition matrices one scale at a time. These algorithms significantly outperform standard optimization methods, which are too slow for the high-dimensional spaces involved.
  7. Empirical Validation of Balanced Performance: Through experiments with real data, the research demonstrates that the proposed two-stage framework can achieve significant improvements in accuracy of distribution while simultaneously maintaining accuracy of counts close to optimal levels and exhibiting reasonable runtime. This validates the practical utility and effectiveness of their approach in balancing these critical performance criteria.

Technical Deep Dive

▶ Watch: The two-stage differentially private framework (6:17)

The core of this research revolves around a sophisticated mathematical and algorithmic framework designed to address the inherent tension between preserving individual count accuracy and the overall distribution of counts under differential privacy.

The journey begins by conceptualizing any count mechanism that applies independent noise to each row as a transition matrix T. This matrix is fundamental to understanding how true counts are mapped to privatized outputs. Specifically, if the true count for a category is I, and the mechanism outputs J, the entry T[I, J] represents the conditional probability of obtaining J given I. This matrix encapsulates the probabilistic behavior of the privacy mechanism.

Next, the true distribution of counts across all categories—i.e., how many categories have a count of 0, how many have 1, how many have 2, and so on—is represented as a row vector Z. If this distribution Z is fed through the count mechanism T, the expected distribution of the outputs will be the product Z T. A crucial concept then emerges: Z is considered a fixed point of the mechanism T if Z = Z T. This condition signifies that the mechanism, on average, preserves the distribution Z. The authors define F(Z) as the set of all differentially private count mechanisms T that have Z as a fixed point. This set F(Z) is mathematically characterized as a convex polytope, an intersection of linear half-spaces. While this sounds promising for selecting a mechanism that preserves a desired distribution, a significant challenge arises: the true distribution Z itself contains private information. Directly using it as a fixed point would compromise differential privacy.

To navigate this, the authors propose a two-stage framework:

  1. Stage 1: Distribution Privatizer (D): The first step involves taking the true, private distribution of counts and privatizing it using a distribution privatizer, denoted D. This yields a differentially private approximation of the true distribution, which the authors label Z'. This Z' now serves as the target distribution that the subsequent count mechanism will attempt to preserve.
  2. Stage 2: Constructor Algorithm (C): The privatized distribution Z' is then passed to a constructor algorithm, C. The constructor's critical role is to choose the actual transition probabilities for the count mechanism T. Its objective is to select a T from the set F(Z') (mechanisms that preserve Z') that also optimizes accuracy of counts. The rationale is that by ensuring T preserves Z', the goal of accuracy of distribution is addressed, and by optimizing for count accuracy, a balanced performance is achieved.
  3. Final Application: Once T is constructed, each row (individual count) of the original table is processed independently through this mechanism T, yielding the final privatized table of counts.

The challenge in Stage 2 lies in the computational complexity. Optimizing over F(Z'), a high-dimensional convex polytope, using standard optimization algorithms (e.g., linear programming solvers) is prohibitively slow. Furthermore, there was no existing theory to guide the design of faster, specialized algorithms for this specific problem.

To overcome this, the authors undertook extensive linear algebra, leading to a profound discovery: any mechanism within F(Z) (the set of mechanisms preserving a distribution Z) can be rewritten in terms of simpler building blocks called epsilon scales. An epsilon scale is a specific type of probability vector where the probabilities in a column either step up or down by a factor of e^ε (where ε is the privacy parameter). Conceptually, one can think of these as "walking up and down stairs" in the probability space. The key mathematical result is that any mechanism T in F(Z) can be expressed as a conic combination of these epsilon scales. This decomposition simplifies the complex optimization problem.

This theoretical breakthrough allowed the design of new constructor algorithms that build the transition matrices T iteratively, one epsilon scale at a time. This approach bypasses the computational bottlenecks of standard optimization methods, enabling much faster construction of privacy mechanisms that effectively preserve target count distributions while maintaining differential privacy and optimizing for count accuracy. The combination of a privatized target distribution and an efficient, distribution-preserving constructor algorithm forms the robust technical backbone of this innovative approach to differentially private count data publication.

Demo / Proof of Concept

▶ Watch: Epsilon scales enable faster constructor algorithms (9:07)

While the talk did not feature a live, interactive demonstration of the proposed system, the speakers presented strong empirical evidence from a set of experiments designed to validate their two-stage framework. These experiments involved applying their newly developed methods to real data and comparing the results against existing privatization techniques. The empirical evaluation focused on the three key performance criteria: accuracy of distribution, accuracy of counts, and runtime. The authors reported positive outcomes, indicating that in several scenarios and with various datasets, their framework yielded significant improvements. Specifically, they observed substantial gains in accuracy of distribution while simultaneously ensuring that accuracy of counts remained close to optimal levels and the runtime was reasonable. These experimental results serve as the proof of concept, demonstrating the practical viability and superior performance of their approach in balancing the critical aspects of privacy-preserving data publication.

Defensive Implications

▶ Watch: Summary of contributions and positive experimental results (10:14)

The work presented by Laskowski and Kohli has profound implications for data publishers, privacy engineers, and organizations tasked with releasing sensitive count data while adhering to differential privacy principles. Rather than focusing on defending against specific attacks, the "defensive" aspect here lies in proactively choosing and implementing privacy mechanisms that offer superior utility and fidelity for a wider range of data analyses.

Firstly, this research urges data publishers to rethink their evaluation criteria for differentially private mechanisms. Exclusive reliance on accuracy of counts is insufficient if the downstream analyses depend on the statistical shape or distribution of the counts. Defenders must consider what types of questions their data consumers will ask. If queries involve identifying common values, understanding frequencies (e.g., "how many entities have zero occurrences"), calculating averages across categories, or performing other distribution-sensitive statistics, then preserving the accuracy of distribution becomes paramount. Failing to do so, as shown by the inherent distortions of existing mechanisms, can lead to misleading or biased insights, undermining the very purpose of data release.

Secondly, organizations should consider adopting or developing differentially private count mechanisms that explicitly address distribution preservation. The two-stage framework proposed in this talk offers a robust theoretical and practical foundation for achieving this balance. This means moving beyond generic noise addition and towards more sophisticated mechanisms that leverage a privatized target distribution to guide the construction of the final privacy mechanism.

Thirdly, privacy engineers should be aware of the trade-offs inherent in differential privacy. While the proposed framework aims to balance accuracy of distribution, accuracy of counts, and runtime, the optimal balance may vary depending on the specific application and the privacy budget (epsilon) allocated. Understanding these trade-offs is crucial for making informed decisions about mechanism selection and parameter tuning.

Finally, this research contributes to a more mature understanding of data utility in the context of differential privacy. By highlighting a previously overlooked dimension of utility, it empowers defenders to publish data that is not only private but also genuinely useful and statistically representative for a broader spectrum of analytical tasks. This proactive approach to mechanism design strengthens the overall "defense" against privacy breaches while maximizing the value derived from sensitive datasets.

Key Takeaways

  • Beyond Count Accuracy: Accuracy of distribution is a critical, often overlooked, performance metric for differentially private count data, essential for analyses focused on the statistical properties of counts rather than just individual values.
  • Inherent Distortion: Existing differentially private count mechanisms inherently distort the underlying distribution of counts (e.g., inflating zeros), leading to potentially misleading analytical results for distribution-based queries.
  • Novel Two-Stage Framework: A new two-stage framework (comprising a distribution privatizer and a constructor algorithm) is proposed to effectively balance accuracy of distribution with traditional accuracy of counts while maintaining differential privacy.
  • Mathematical Breakthrough with Epsilon Scales: The research introduces a novel mathematical theory demonstrating that distribution-preserving mechanisms can be represented as a conic combination of "epsilon scales", enabling the design of significantly faster constructor algorithms.
  • Improved Utility and Efficiency: Empirical results show that the proposed methods offer substantial improvements in preserving count distributions, maintain near-optimal count accuracy, and achieve reasonable runtime, enhancing the overall utility of privatized data.
  • Informed Mechanism Selection: Data publishers and privacy engineers should carefully consider the types of analyses performed on their privatized data and prioritize mechanisms that explicitly address distribution preservation when statistical properties of counts are important.

About the Speaker(s)

The talk was delivered by Paul Laskowski, a paper author associated with UC Berkeley, who presented the research findings. His co-author for this work is Nitin Kohli, also affiliated with UC Berkeley. Their collaboration has focused on advancing the theoretical and practical aspects of differential privacy, specifically in the context of preserving data utility for complex analytical tasks.

Reviews

Dr. Zero (Offensive Security Researcher) — STRONG ACCEPT

Laskowski and Kohli did the actual math to fix a massive, quietly ignored problem in Differential Privacy: standard noise injection destroys aggregate distribution utility. They bypass slow linear programming bottlenecks using a novel 'epsilon scale' decomposition to build transition matrices that don't wreck your dataset's statistical shape. It's rigorous, hype-free privacy engineering that builders desperately need.

Heather Calloway (CISO) — SOLID

Solid privacy engineering research on a fundamental flaw in how we anonymize dataset counts. It proves that standard differential privacy mechanisms destroy the macro-statistical distribution of the data. Worth passing to your privacy engineering lead if your business monetizes or shares aggregated customer data.

→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026

All talks from Privacy Enhancing Technologies Symposium (PETS) 2026