  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.
