Local, private, efficient protocols for succinct histograms

DOI10.1145/2746539.2746632MaRDI QIDQ2941496zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

algorithmscomplexitydifferential privacyheavy hitterslocal protocolssuccinct histograms

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(22)

• On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
• Locally differentially private item-based collaborative filtering
• Optimal locally private estimation under \(\ell_p\) loss for \(1\le p\le 2\)
• Distributed private heavy hitters
• Buying data from privacy-aware individuals: the effect of negative payments
• Comment
• Practical locally private heavy hitters
• The complexity of differential privacy
• Scalable and Jointly Differentially Private Packing
• Empirical risk minimization in the non-interactive local model of differential privacy
• Locally private \(k\)-means clustering
• Fast Private Norm Estimation and Heavy Hitters
• Separating Local & Shuffled Differential Privacy via Histograms
• Key-value data collection and statistical analysis with local differential privacy
• Forty years of frequent items
• Local differentially private frequency estimation based on learned sketches
• Fine-filter: an effective defense against poisoning attacks on frequency estimation under LDP
• LDP-PPA: local differential privacy protection for principal component analysis
• Differentially private hypothesis testing with the subsampled and aggregated randomized response mechanism
• Estimating sparse discrete distributions under privacy and communication constraints
• Channel simulation: theory and applications to lossy compression and differential privacy
• On the privacy of sublinear-communication Jaccard index estimation via min-hash

Describes a project that uses

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)