Abstract
Local Differential Privacy protocols are stochastic protocols used in data aggregation when individual users do not trust the data aggregator with their private data. In such protocols there is a fundamental tradeoff between user privacy and aggregator utility. In the setting of frequency estimation, established bounds on this tradeoff are either nonquantitative, or far from what is known to be attainable. In this paper, we use information-theoretical methods to significantly improve established bounds. We also show that the new bounds are attainable for binary inputs. Furthermore, our methods lead to improved frequency estimators, which we experimentally show to outperform state-of-the-art methods.
| Original language | English |
|---|---|
| Title of host publication | WPES 2020 - Proceedings of the 19th Workshop on Privacy in the Electronic Society |
| Publisher | Association for Computing Machinery, Inc |
| Pages | 123-135 |
| Number of pages | 13 |
| ISBN (Electronic) | 9781450380867 |
| DOIs | |
| Publication status | Published - 9 Nov 2020 |
| Event | 19th ACM Workshop on Privacy in the Electronic Society, WPES 2020, held in conjunction with the 27th ACM Conference on Computer and Communication Security, CCS 2020 - Virtual, Online, United States Duration: 9 Nov 2020 → 9 Nov 2020 |
Conference
| Conference | 19th ACM Workshop on Privacy in the Electronic Society, WPES 2020, held in conjunction with the 27th ACM Conference on Computer and Communication Security, CCS 2020 |
|---|---|
| Country/Territory | United States |
| City | Virtual, Online |
| Period | 9/11/20 → 9/11/20 |
Funding
This project is supported by NSF grant 1640374, NWO grant 628.001.026, and NSF grant 1931443. We thank the anonymous reviewers for their helpful suggestions.
Keywords
- frequency estimation
- information theory
- local differential privacy
- privacy-utility tradeoff