Toward Evaluating Re-identification Risks in the Local Privacy Model

LDP (Local Differential Privacy) has recently attracted much attention as a metric of data privacy that prevents the inference of personal data from obfuscated data in the local model. However, there are scenarios in which the adversary needs to perform re-identification attacks to link the obfuscated data to users in this model. LDP can cause excessive obfuscation and destroy the utility in these scenarios, because it is not designed to directly prevent re-identification. In this paper, we propose a privacy metric which we call the PIE (Personal Information Entropy). The PIE is designed so that it directly prevents re-identification attacks in the local model. It lower-bounds the lowest possible re-identification error probability (i.e., Bayes error probability) of the adversary. We analyze the relation between LDP and the PIE, and analyze the PIE and utility in distribution estimation for two obfuscation mechanisms providing LDP. Through experiments, we show that LDP fails to guarantee meaningful privacy and utility in distribution estimation. Then we show that the PIE can be used to guarantee low reidentification risks for the local obfuscation mechanisms while keeping high utility.