Preventing Equivalence Attacks in Updated, Anonymized Data

In comparison to the extensive body of existing
work considering publish-once, static anonymization, dynamic
anonymization is less well studied. Previous work, most notably
m-invariance, has made considerable progress in devising a
scheme that attempts to prevent individual records from being
associated with too few sensitive values. We show, however, that
in the presence of updates, even an m-invariant table can be
exploited by a new type of attack we call the “equivalenceattack.”
To deal with the equivalence attack, we propose a
graph-based anonymization algorithm that leverages solutions
to the classic “min-cut/max-flow” problem, and demonstrate
with experiments that our algorithm is efficient and effective
in preventing equivalence attacks.