Anonymized Histograms in Intermediate Privacy Models. (arXiv:2210.15178v1 [cs.DS])

We study the problem of privately computing the anonymized histogram (a.k.a.
unattributed histogram), which is defined as the histogram without item labels.
Previous works have provided algorithms with $\ell_1$- and $\ell_2^2$-errors of
$O_\varepsilon(\sqrt{n})$ in the central model of differential privacy (DP).

In this work, we provide an algorithm with a nearly matching error guarantee
of $\tilde{O}_\varepsilon(\sqrt{n})$ in the shuffle DP and pan-private models.
Our algorithm is very simple: it just post-processes the discrete
Laplace-noised histogram! Using this algorithm as a …

arxiv histograms privacy