Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time

2025/07/22 by Kerschbaum, Florian, Lee, Steven, Wu, Hao
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2507.17017

Abstract

We present an algorithm that releases a pure differentially private (under the replacement neighboring relation) sparse histogram for n participants over a domain of size d ≫ n. Our method achieves the optimal ℓ_∞-estimation error and runs in strictly O(n) time in the Word-RAM model, improving upon the previous best deterministic-time bound of O(n²) and resolving the open problem of breaking this quadratic barrier (Balcer and Vadhan, 2019). Moreover, the algorithm admits an efficient circuit implementation, enabling the first near-linear communication and computation cost pure DP histogram MPC protocol with optimal ℓ_∞-estimation error. Central to our algorithm is a novel **private item blanket** technique with target-length padding, which hides differences in the supports of neighboring histograms while remaining efficiently implementable.

Citations

• Approximate DBSCAN under Differential Privacy
• A Framework for Differential Privacy Against Timing Attacks
• Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch
• CrypTen: Secure Multi-Party Computation Meets Machine Learning
• Asymptotically Optimal Locally Private Heavy Hitters via Parameterized Sketches
• Array programming with NumPy
• The Privacy Blanket of the Shuffle Model
• Heavy Hitters and the Structure of Local Privacy
• Differential Privacy on Finite Computers
• Prio: Private, Robust, and Scalable Computation of Aggregate Statistics
• Building a RAPPOR with the Unknown: Privacy-Preserving Learning of\n Associations and Data Dictionaries
• Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation
• On the Geometry of Differential Privacy
• Universally Utility-Maximizing Privacy Mechanisms
• Shannon meets Gray: Noise-robust, Low-sensitivity Codes with Applications in Differential Privacy

Related

• Tight Bounds for Differentially Private Anonymized Histograms
• Locally Private Histograms in All Privacy Regimes
• Anonymized Histograms in Intermediate Privacy Models
• DPCube: Differentially Private Histogram Release through Multidimensional Partitioning
• Differentially Private Sparse Vectors with Low Error, Optimal Space, and\n Fast Access