Local, private, efficient protocols for succinct histograms

DOI10.1145/2746539.2746632zbMATH Open1321.94037arXiv1504.04686OpenAlexW3102859907MaRDI QIDQ2941496FDOQ2941496

Authors:

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Abstract: 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 data. A succinct histogram is a list of the most frequent items in the data (often called "heavy hitters") along with estimates of their frequencies; the frequency of all other items is implicitly estimated as 0. If there are $n$ users whose items come from a universe of size $d$, our protocols run in time polynomial in $n$ and $log(d)$. With high probability, they estimate the accuracy of every item up to error $Oleft(sqrtlog(d)/(epsilo{n}^{2}n)ight)$ where $epsilon$ is the privacy parameter. Moreover, we show that this much error is necessary, regardless of computational efficiency, and even for the simple setting where only one item appears with significant frequency in the data set. Previous protocols (Mishra and Sandler, 2006; Hsu, Khanna and Roth, 2012) for this task either ran in time $Omega(d)$ or had much worse error (about $sqrt[6]log(d)/(epsilo{n}^{2}n)$), and the only known lower bound on error was $Omega(1/sqrtn)$. We also adapt a result of McGregor et al (2010) to the local setting. In a model with public coins, we show that each user need only send 1 bit to the server. For all known local protocols (including ours), the transformation preserves computational efficiency.

Full work available at URL: https://arxiv.org/abs/1504.04686

Recommendations

• Practical locally private heavy hitters
• Distributed private heavy hitters
• Heavy Hitters and the Structure of Local Privacy
• On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
• Fast Private Norm Estimation and Heavy Hitters

zbMATH Keywords

algorithmscomplexitydifferential privacyheavy hitterslocal protocolssuccinct histograms

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Shortest-path queries in static networks
• Approximate distance oracles
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On approximate distance labels and routing schemes with affine stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Approximate distance oracles with constant query time
• Fast C-K-R partitions of sparse graphs
• Automata, Languages and Programming
• Ramsey partitions and proximity data structures

Cited In (16)

• Scalable and Jointly Differentially Private Packing
• Empirical risk minimization in the non-interactive local model of differential privacy
• Optimal locally private estimation under \(\ell_p\) loss for \(1\le p\le 2\)
• Locally differentially private item-based collaborative filtering
• Fast Private Norm Estimation and Heavy Hitters
• Separating Local & Shuffled Differential Privacy via Histograms
• Title not available (Why is that?)
• Distributed private heavy hitters
• Forty years of frequent items
• Comment
• Practical locally private heavy hitters
• The complexity of differential privacy
• On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
• Local differentially private frequency estimation based on learned sketches
• Buying data from privacy-aware individuals: the effect of negative payments
• Key-value data collection and statistical analysis with local differential privacy

Uses Software

• Graphs

This page was built for publication: Local, private, efficient protocols for succinct histograms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941496)