Structural composition attacks on anonymized data

Abstract

Anonymized releases of databases are increasingly available in public. The composition of two releases does not necessarily fulfil any anonymity notion, even if the individual releases do fulfil that anonymity notion on their own. In this paper, we study composition scenarios and provide formalizations. We introduce a formal framework to study the composition of databases on a structural level and show the equivalence of the composition scenarios used in the literature. We show that known attacks on anonymity notions can be reduced to two simple properties and only need limited side information.