Composition attacks and auxiliary information in data privacy

TLDR

Privacy is increasingly important, yet reasoning about it is fraught with pitfalls, especially due to auxiliary information that adversaries can obtain from external sources such as the web, public records, or domain knowledge. This paper investigates how to reason about privacy in the presence of rich, realistic auxiliary information. The study examines the effectiveness of existing anonymization schemes when multiple organizations independently release anonymized data on overlapping populations.

Abstract

Privacy is an increasingly important aspect of data publishing. Reasoning about privacy, however, is fraught with pitfalls. One of the most significant is the auxiliary information (also called external knowledge, background knowledge, or side information) that an adversary gleans from other channels such as the web, public records, or domain knowledge. This paper explores how one can reason about privacy in the face of rich, realistic sources of auxiliary information. Specifically, we investigate the effectiveness of current anonymization schemes in preserving privacy when multiple organizations independently release anonymized data about overlapping populations.