  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{\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.
