Local, Private, Efficient Protocols for Succinct Histograms
Local, Private, Efficient Protocols for Succinct Histograms
We give efficient protocols and matching accuracy lower bounds for frequency estimation in the local model for differential privacy. In this model, individual users randomize their data themselves, sending differentially private reports to an untrusted server that aggregates them. We study protocols that produce a succinct histogram representation of the …