A Sieve-Accelerated Quadrature Method for Exact Privacy Accounting in the 2020 U.S. Decennial Census
2026-06-29 • Cryptography and Security
Cryptography and SecurityData Structures and Algorithms
AI summaryⓘ
The authors developed a new, fast method to measure how private the data released by the 2020 U.S. Census really is when noise is added to protect people's information. Their technique uses advanced math and computer tricks to accurately calculate privacy guarantees without extra noise, helping keep data useful. They applied this to the Census data and sped up privacy calculations by over 1,800 times compared to older methods, meeting strict accuracy rules exactly.
differential privacydiscrete Gaussian noiseprivacy budgetnumerical integrationFourier transformtrapezoidal rulecharacteristic functionprivacy profilecensus datacomposition theorem
Authors
Buxin Su, Weijie Su, Chendi Wang
Abstract
In 2020, the U.S. Census Bureau adopted differential privacy for the Decennial Census by injecting integer-valued Gaussian noise into published census tabulations. Exactly evaluating the privacy guarantees of these data releases would enable the Bureau to determine the absolute minimum noise required to satisfy a given privacy budget, preventing the injection of unnecessary excess noise and thereby substantially enhancing the statistical utility of the data for downstream applications such as federal funding allocation and political redistricting. In this paper, we introduce 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. Taken 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.