Differentially private anonymized histograms
This work addresses privacy concerns for sensitive data like password frequencies and social network degree distributions, offering a novel solution for secure histogram release.
The authors tackled the problem of releasing anonymized histograms under differential privacy, achieving near-optimal privacy-utility trade-offs in terms of item count and privacy parameters, with sub-linear runtime for compact inputs.
For a dataset of label-count pairs, an anonymized histogram is the multiset of counts. Anonymized histograms appear in various potentially sensitive contexts such as password-frequency lists, degree distribution in social networks, and estimation of symmetric properties of discrete distributions. Motivated by these applications, we propose the first differentially private mechanism to release anonymized histograms that achieves near-optimal privacy utility trade-off both in terms of number of items and the privacy parameter. Further, if the underlying histogram is given in a compact format, the proposed algorithm runs in time sub-linear in the number of items. For anonymized histograms generated from unknown discrete distributions, we show that the released histogram can be directly used for estimating symmetric properties of the underlying distribution.