Preserving Target Distributions With Differentially Private Count Mechanisms
Authors: Nitin Kohli (UC Berkeley Center for Effective Global Action), Paul Laskowski (UC Berkeley School of Information)
Volume: 2026
Issue: 2
Pages: 615–641
DOI: https://doi.org/10.56553/popets-2026-0063
Abstract: Differentially private mechanisms are increasingly used to publish tables of counts, where each entry represents the number of individuals belonging to a particular category. A distribution of counts summarizes the information in the count column, unlinking counts from categories. This object is useful for answering a class of research questions, but it is subject to statistical biases when counts are privatized with standard mechanisms. This motivates a novel design criterion we term accuracy of distribution.
This study formalizes a two-stage framework for privatizing tables of counts that balances accuracy of distribution with two standard criteria of accuracy of counts and runtime. In the first stage, a distribution privatizer generates an estimate for the true distribution of counts. We introduce a new mechanism, called the cyclic Laplace, specifically tailored to distributions of counts, that outperforms existing general-purpose differentially private histogram mechanisms. In the second stage, a constructor algorithm generates a count mechanism, represented as a transition matrix, whose fixed-point is the privatized distribution of counts. We develop a mathematical theory that describes such transition matrices in terms of simple building blocks we call epsilon-scales. This theory informs the design of a new constructor algorithm that generates transition matrices with favorable properties more efficiently than standard optimization algorithms. We explore the practicality of our framework with a set of experiments, highlighting situations in which a fixed-point method provides a favorable tradeoff among performance criteria.
Keywords: Differential Privacy, Distribution Preservation, Optimal Count Mechanisms, Convex Polytopes, Fixed-Point Analysis
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
