Random Sampling Plus Fake Data: Multidimensional Frequency Estimates With Local Differential Privacy
This addresses the challenge of preserving privacy in multidimensional data analysis for applications like population studies, offering an incremental improvement over prior methods by enhancing utility while maintaining privacy guarantees.
The paper tackles the problem of multidimensional frequency estimation under local differential privacy, where existing methods either split the privacy budget or sample a single attribute, and proposes a new solution called Random Sampling plus Fake Data (RS+FD) that creates uncertainty over the sampled attribute by generating fake data for non-sampled ones, achieving nearly the same or better utility than the state-of-the-art method in experiments.
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 \geq 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ε{d}$-LDP (Spl), and 2) random sampling a single attribute and spend all the privacy budget to send it with $ε$-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^ε$ probability bound (rather than $e^{ε/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.