  Local Differential Privacy (LDP) protocols enable an untrusted server to
perform privacy-preserving, federated data analytics. Various LDP protocols
have been developed for different types of data such as categorical data,
numerical data, and key-value data. Due to their distributed settings, LDP
protocols are fundamentally vulnerable to poisoning attacks, in which fake
users manipulate the server's analytics results via sending carefully crafted
data to the server. However, existing poisoning attacks focused on LDP
protocols for simple data types such as categorical and numerical data, leaving
the security of LDP protocols for more advanced data types such as key-value
data unexplored.
  In this work, we aim to bridge the gap by introducing novel poisoning attacks
to LDP protocols for key-value data. In such a LDP protocol, a server aims to
simultaneously estimate the frequency and mean value of each key among some
users, each of whom possesses a set of key-value pairs. Our poisoning attacks
aim to simultaneously maximize the frequencies and mean values of some
attacker-chosen target keys via sending carefully crafted data from some fake
users to the sever. Specifically, since our attacks have two objectives, we
formulate them as a two-objective optimization problem. Moreover, we propose a
method to approximately solve the two-objective optimization problem, from
which we obtain the optimal crafted data the fake users should send to the
server. We demonstrate the effectiveness of our attacks to three LDP protocols
for key-value data both theoretically and empirically. We also explore two
defenses against our attacks, which are effective in some scenarios but have
limited effectiveness in other scenarios. Our results highlight the needs for
new defenses against our poisoning attacks.
