document: Composition attacks and auxiliary information in data privacy 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 . 1 . We investigate composition attacks , in which an adversary uses independent anonymized releases to breach privacy . We explain why recently proposed models of limited auxiliary information fail to capture composition attacks . Our experiments demonstrate that even a simple instance of a composition attack can breach privacy in practice , for a large class of currently proposed techniques . The class includes k-anonymity and several recent variants . 2 . On a more positive note , certain randomization-based notions of privacy ( such as differential privacy ) provably resist composition attacks and , in fact , the use of arbitrary side information . This resistance enables `` stand-alone '' design of anonymization schemes , without the need for explicitly keeping track of other releases . We provide a precise formulation of this property , and prove that an important class of relaxations of differential privacy also satisfy the property . This significantly enlarges the class of protocols known to enable modular design .
doc_bio_tags: O O O O O O O B B O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O B O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O