Private Heavy Hitters and Range Queries in the Shuffled Model
By Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker. 2019
6 citations recorded by the source corpus.
An exciting new development in differential privacy is the shuffled model, which makes it possible to circumvent the large error lower bounds that are typically incurred in the local model, while relying on much weaker trust assumptions than in the central model. In this work, we study two basic statistical problems, namely, heavy hitters and $d$-dimensional range counting queries, in the shuffled model of privacy. For both problems we devise algorithms with polylogarithmic communication per user and polylogarithmic error; a consequence is an algorithm for approximating the median with similar communication and error. These bounds significantly improve on what is possible in the local model of differential privacy, where the error must provably grow polynomially with the number of users.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Badih Ghazi
- Pasin Manurangsi
- Albert Cheu
- Abhradeep Thakurta
- Rasmus Pagh
- Vitaly Feldman
- Kunal Talwar
- Peter Kairouz
Citations in the corpus
- Private Aggregation from Fewer Anonymous Messages (2019, methodology): “Indeed, the power of the shuffled model has been illustrated by a number of recent works that have designed algorithms in this model for a wide range of problems such as privacy amplification, histograms, heavy hitters, and range queries [7,10,4,11].”
- Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, background): “This lack of clarity is especially concerning because of recent formal results—known colloquially as “privacy amplification by shuffling” [3], [13], [14], [19]—which have fundamentally changed privacy/utility tradeoffs and forced a reconsideration of previous approaches, like those described above.”
- Separating Local & Shuffled Differential Privacy via Histograms (2019, background): “O ( log d n + 1 εn · √ log d · log 1 εδ ) O ( 1 ε(2) log 1 εδ ) [9]”
- Practical and Robust Privacy Amplification with Multi-Party Differential Privacy (2019, methodology): “Parallel to our work, [8], [30] propose mechanisms other than GRR to improve utility in this model.”