Mr X vs. Mr Y: The emergence of externalities in differential privacy

The application of differential privacy requires the addition of Laplace noise, whose level must be measured out to achieve the desired level of privacy. However, the protection of the data concerning a Mr. X, i.e., its privacy level, also depends on the other data contained in the database: a negative externality is recognized. In this paper we show that an attack on Mr. X can be conducted by an oracle, by computing the likelihood ratio under two scenarios, where the database population is made of either independent or correlated entries. We show that the target Mr. X can be spotted, notwithstanding the addition of noise, when its position happens to be eccentric with respect to the bulk of the database population.