Improving Frequency Estimation under Local Differential Privacy

Milan Lopuhaä-Zwakenberg, Zitao Li, Boris Skoric, Ninghui Li

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationWPES 2020 - Proceedings of the 19th Workshop on Privacy in the Electronic Society
PublisherAssociation for Computing Machinery, Inc
Pages123-135
Number of pages13
ISBN (Electronic)9781450380867
DOIs
Publication statusPublished - 9 Nov 2020
Event19th 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 → …

Publication series

NameWPES 2020 - Proceedings of the 19th Workshop on Privacy in the Electronic Society

Conference

Conference19th 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
CountryUnited States
CityVirtual, Online
Period9/11/20 → …

Keywords

  • frequency estimation
  • information theory
  • local differential privacy
  • privacy-utility tradeoff

Fingerprint Dive into the research topics of 'Improving Frequency Estimation under Local Differential Privacy'. Together they form a unique fingerprint.

Cite this