Skip to yearly menu bar Skip to main content


Poster

Anonymized Histograms in Intermediate Privacy Models

Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi

Hall J (level 1) #829

Keywords: [ pan privacy ] [ shuffle DP ] [ anonymized histograms ] [ differential privacy ]


Abstract: We study the problem of privately computing the \it anonymized histogram\it anonymized histogram (a.k.a. \it unattributed histogram), which is defined as the histogram without item labels. Previous works have provided algorithms with 1- and 22-errors of Oε(n) in the central model of differential privacy (DP).In this work, we provide an algorithm with a nearly matching error guarantee of ˜Oε(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 subroutine, we show applications in privately estimating symmetric properties of distributions such as entropy, support coverage, and support size.

Chat is not available.