PrivKV: Key-value data collection with local differential privacy

Qingqing Ye, Haibo Hu, Xiaofeng Meng, Huadi Zheng

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

32 Citations (Scopus)

Abstract

Local differential privacy (LDP), where each user perturbs her data locally before sending to an untrusted data collector, is a new and promising technique for privacy-preserving distributed data collection. The advantage of LDP is to enable the collector to obtain accurate statistical estimation on sensitive user data (e.g., location and app usage) without accessing them. However, existing work on LDP is limited to simple data types, such as categorical, numerical, and set-valued data. To the best of our knowledge, there is no existing LDP work on key-value data, which is an extremely popular NoSQL data model and the generalized form of set-valued and numerical data. In this paper, we study this problem of frequency and mean estimation on key-value data by first designing a baseline approach PrivKV within the same 'perturbation-calibration' paradigm as existing LDP techniques. To address the poor estimation accuracy due to the clueless perturbation of users, we then propose two iterative solutions PrivKVM and PrivKVM+ that can gradually improve the estimation results through a series of iterations. An optimization strategy is also presented to reduce network latency and increase estimation accuracy by introducing virtual iterations in the collector side without user involvement. We verify the correctness and effectiveness of these solutions through theoretical analysis and extensive experimental results.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE Symposium on Security and Privacy, SP 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages317-331
Number of pages15
ISBN (Electronic)9781538666609
DOIs
Publication statusPublished - 19 May 2019
Event40th IEEE Symposium on Security and Privacy, SP 2019 - San Francisco, United States
Duration: 19 May 201923 May 2019

Publication series

NameProceedings - IEEE Symposium on Security and Privacy
Volume2019-May
ISSN (Print)1081-6011

Conference

Conference40th IEEE Symposium on Security and Privacy, SP 2019
Country/TerritoryUnited States
CitySan Francisco
Period19/05/1923/05/19

Keywords

  • Data-perturbation
  • Key-value-data
  • Local-differential-privacy

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Software
  • Computer Networks and Communications

Cite this