Random Sampling Plus Fake Data: Multidimensional Frequency Estimates With Local Differential Privacy

Abstract

With local differential privacy (LDP), users can privatize their data and thus guarantee privacy properties before transmitting it to the server (a.k.a. the aggregator). One primary objective of LDP is frequency (or histogram) estimation, in which the aggregator estimates the number of users for each possible value. In practice, when a study with rich content on a population is desired, the interest is in the multiple attributes of the population, that is to say, in multidimensional data ($d\ge 2$). However, contrary to the problem of frequency estimation of a single attribute (the majority of the works), the multidimensional aspect imposes to pay particular attention to the privacy budget. This one can indeed grow extremely quickly due to the composition theorem. To the authors' knowledge, two solutions seem to stand out for this task: 1) splitting the privacy budget for each attribute, i.e., send each value with $\frac{\epsilon }{d}$-LDP (Spl), and 2) random sampling a single attribute and spend all the privacy budget to send it with $\epsilon$-LDP (Smp). Although Smp adds additional sampling error, it has proven to provide higher data utility than the former Spl solution. However, we argue that aggregators (who are also seen as attackers) are aware of the sampled attribute and its LDP value, which is protected by a "less strict" $e^{\epsilon }$ probability bound (rather than $e^{\epsilon /d}$). This way, we propose a solution named Random Sampling plus Fake Data (RS+FD), which allows creating uncertainty over the sampled attribute by generating fake data for each non-sampled attribute; RS+FD further benefits from amplification by sampling. We theoretically and experimentally validate our proposed solution on both synthetic and real-world datasets to show that RS+FD achieves nearly the same or better utility than the state-of-the-art Smp solution.

References in corpus (13)

• Deep Learning with Differential Privacy
• RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response
• Local, Private, Efficient Protocols for Succinct Histograms
• LoPub: High-Dimensional Crowdsourced Data Publication with Local Differential Privacy
• Collecting Telemetry Data Privately
• Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy
• Google COVID-19 Community Mobility Reports: Anonymization Process Description (version 1.1)
• Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences
• Privacy Amplification by Iteration
• Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication
• 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

Cited by in corpus (7)

• LDP-IDS: Local Differential Privacy for Infinite Data Streams
• Improving the utility of locally differentially private protocols for longitudinal and multidimensional frequency estimates
• On the Risks of Collecting Multidimensional Data Under Local Differential Privacy
• Multi-Freq-LDPy: Multiple Frequency Estimation Under Local Differential Privacy in Python
• (Local) Differential Privacy has NO Disparate Impact on Fairness
• Revealing the True Cost of Locally Differentially Private Protocols: An Auditing Perspective
• Fine-grained Manipulation Attacks to Local Differential Privacy Protocols for Data Streams