Mathematical results on database privacy
Martin M. Merener · 2012
The central problem in Data Privacy is how to release valuable information pertaining to a group of individuals, while preserving their privacy. A key question is how far the data disclosure can go, without compromising the privacy of the individuals who contributed their data. Examples of this include databases containing health information about patients, customer electronic transactions, and web browsing history. In this work we focus on attacks to two types of mechanisms that are meant to protect privacy: output perturbation and de-identification. On output perturbation, we revisit two known attacks: the Dinur-Nissim adversary [14] and the Hadamard adversary [23]. We extend the know results on the success of the Dinur-Nissim adversary to a more general and abstract setting that includes, in particular, both real-valued and binary databases—the case studied in [14]—each case with natural and appropriate metrics. In this general setting we provide a better explanation of the relationships between all the relevant parameters of the problem, and consequently obtain more efficient and versatile results on the performance of the adversary. We study the Hadamard adversary in the context of differential privacy [18], and prove several new results showing the amount of error that is necessarily caused by a randomized output perturbation sanitizer providing differential privacy. We show that the required amount of noise is excessively large, rendering the sanitized responses with little or no utility. We conclude that differential privacy against the Hadamard adversary comes with an extremely large cost on the utility of the sanitized responses. Regarding the mechanisms that anonymize databases via de-identification, we perform several experiments with linkage attacks on real data contained in the microdata file of the Joint Canada/United States Survey of Health 2004 [47]. We show that with a large (or at least significant) probability, an adversary knowing a rather small amount of auxiliary information about the less sensitive attributes of the database, can successfully link such an auxiliary information (which could be associated with an identity) to the whole and anonymous record of the corresponding individual. Then we review the theoretical result of Narayanan and Shmatikov [38] on database de-anonymization. We start by exhibiting counterexamples to their main theoretical proof, and develop new theorems of de-anonymization that fix these problems. We also contribute more and new theoretical results that incorporate hypotheses on the sparseness of the database, and contemplate the realistic situation in which the auxiliary information of the adversary contains rare attributes, which in turn improves the de-anonymization by requiring less auxiliary information.