Improving the utility of locally differentially private protocols for longitudinal and multidimensional frequency estimates

Abstract

This paper investigates the problem of collecting multidimensional data throughout time (i.e., longitudinal studies) for the fundamental task of frequency estimation under Local Differential Privacy (LDP) guarantees. Contrary to frequency estimation of a single attribute, the multidimensional aspect demands particular attention to the privacy budget. Besides, when collecting user statistics longitudinally, privacy progressively degrades. Indeed, the "multiple" settings in combination (i.e., many attributes and several collections throughout time) impose several challenges, for which this paper proposes the first solution for frequency estimates under LDP. To tackle these issues, we extend the analysis of three state-of-the-art LDP protocols (Generalized Randomized Response -- GRR, Optimized Unary Encoding -- OUE, and Symmetric Unary Encoding -- SUE) for both longitudinal and multidimensional data collections. While the known literature uses OUE and SUE for two rounds of sanitization (a.k.a. memoization), i.e., L-OUE and L-SUE, respectively, we analytically and experimentally show that starting with OUE and then with SUE provides higher data utility (i.e., L-OSUE). Also, for attributes with small domain sizes, we propose Longitudinal GRR (L-GRR), which provides higher utility than the other protocols based on unary encoding. Last, we also propose a new solution named Adaptive LDP for LOngitudinal and Multidimensional FREquency Estimates (ALLOMFREE), which randomly samples a single attribute to be sent with the whole privacy budget and adaptively selects the optimal protocol, i.e., either L-GRR or L-OSUE. As shown in the results, ALLOMFREE consistently and considerably outperforms the state-of-the-art L-SUE and L-OUE protocols in the quality of the frequency estimates.

arXiv commentFinal version accepted in the journal Digital Communications and Networks. Version of Record: https://doi.org/10.1016/j.dcan.2022.07.003

References in corpus (15)

• Deep Learning with Differential Privacy
• RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response
• LoPub: High-Dimensional Crowdsourced Data Publication with Local Differential Privacy
• Collecting Telemetry Data Privately
• Local Differential Privacy for Deep Learning
• Discrete Distribution Estimation under Local Privacy
• Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy
• Google COVID-19 Community Mobility Reports: Anonymization Process Description (version 1.1)
• Frequency Estimation under Local Differential Privacy [Experiments, Analysis and Benchmarks]
• What Can We Learn Privately?
• Collecting and Analyzing Multidimensional Data with Local Differential Privacy
• Practical Locally Private Heavy Hitters
• Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation
• LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale
• Random Sampling Plus Fake Data: Multidimensional Frequency Estimates With Local Differential Privacy

Cited by in corpus (4)

• On the Risks of Collecting Multidimensional Data Under Local Differential Privacy
• Multi-Freq-LDPy: Multiple Frequency Estimation Under Local Differential Privacy in Python
• Revealing the True Cost of Locally Differentially Private Protocols: An Auditing Perspective
• On the Utility Gain of Iterative Bayesian Update for Locally Differentially Private Mechanisms