PCKV: Locally differentially private correlated key-value data collection with optimized utility

Xiaolan Gu, Ming Li, Yueqiang Cheng, Li Xiong, Yang Cao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Scopus citations

Abstract

Data collection under local differential privacy (LDP) has been mostly studied for homogeneous data. Real-world applications often involve a mixture of different data types such as key-value pairs, where the frequency of keys and mean of values under each key must be estimated simultaneously. For key-value data collection with LDP, it is challenging to achieve a good utility-privacy tradeoff since the data contains two dimensions and a user may possess multiple key-value pairs. There is also an inherent correlation between key and values which if not harnessed, will lead to poor utility. In this paper, we propose a locally differentially private key-value data collection framework that utilizes correlated perturbations to enhance utility. We instantiate our framework by two protocols PCKV-UE (based on Unary Encoding) and PCKV-GRR (based on Generalized Randomized Response), where we design an advanced Padding-and-Sampling mechanism and an improved mean estimator which is non-interactive. Due to our correlated key and value perturbation mechanisms, the composed privacy budget is shown to be less than that of independent perturbation of key and value, which enables us to further optimize the perturbation parameters via budget allocation. Experimental results on both synthetic and real-world datasets show that our proposed protocols achieve better utility for both frequency and mean estimations under the same LDP guarantees than state-of-the-art mechanisms.

Original languageEnglish (US)
Title of host publicationProceedings of the 29th USENIX Security Symposium
PublisherUSENIX Association
Pages967-984
Number of pages18
ISBN (Electronic)9781939133175
StatePublished - 2020
Event29th USENIX Security Symposium - Virtual, Online
Duration: Aug 12 2020Aug 14 2020

Publication series

NameProceedings of the 29th USENIX Security Symposium

Conference

Conference29th USENIX Security Symposium
CityVirtual, Online
Period8/12/208/14/20

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'PCKV: Locally differentially private correlated key-value data collection with optimized utility'. Together they form a unique fingerprint.

Cite this