In 2020, the U.S. Census Bureau adopted differential privacy by injecting integer-valued Gaussian noise into published census tabulations. Accurately evaluating the privacy guarantees of these data releases allows the Bureau to determine the minimum noise required to satisfy a given privacy budget, thus avoiding unnecessary excess noise and significantly enhancing data utility for downstream applications like federal funding allocation and political redistricting.
This paper introduces a computationally efficient and mathematically rigorous quadrature method to evaluate the exact privacy profile of practical, large-scale census releases under the composition of heterogeneous discrete Gaussian mechanisms. Mathematically, this problem reduces to evaluating the tail probabilities of high-dimensional convolutions of integer-valued random variables sampled from heterogeneous discrete Gaussian distributions under exceptionally stringent numerical error tolerances (e.g., $10^{-35}$). By recasting the exact privacy accounting as a numerical integration problem via the discrete Fourier transform, we explicitly exploit the exponential convergence of the trapezoidal rule for complex analytic, periodic characteristic functions.
Furthermore, to overcome the computational bottleneck of evaluating highly oscillatory integrands in high dimensions, we develop a sieve algorithm that identifies and prunes negligible quadrature nodes, accelerating the computation by three orders of magnitude. Together, these numerical innovations enable the first exact, assumption-free privacy accounting for the 2020 Census Demographic and Housing Characteristics File, achieving a 1,824-fold speedup over prior methods while maintaining census-mandated error tolerances.
Blogger's Review: This research not only optimizes privacy protection mechanisms but also greatly enhances data utility, showcasing the powerful potential of mathematical and computational methods in practical applications.