Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918262471655424 |
|---|---|
| author | Kerschbaum, Florian Lee, Steven Wu, Hao |
| author_facet | Kerschbaum, Florian Lee, Steven Wu, Hao |
| contents | 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 \gg n$. Our method achieves the optimal $\ell_\infty$-estimation error and runs in strictly $O(n)$ time in the Word-RAM model, improving upon the previous best deterministic-time bound of $\tilde{O}(n^2)$ 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 $\ell_\infty$-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_17017 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time Kerschbaum, Florian Lee, Steven Wu, Hao Data Structures and Algorithms Cryptography and Security 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 \gg n$. Our method achieves the optimal $\ell_\infty$-estimation error and runs in strictly $O(n)$ time in the Word-RAM model, improving upon the previous best deterministic-time bound of $\tilde{O}(n^2)$ 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 $\ell_\infty$-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. |
| title | Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time |
| topic | Data Structures and Algorithms Cryptography and Security |
| url | https://arxiv.org/abs/2507.17017 |