Publishing Set-Valued Data Against Realistic Adversaries

Privacy protection in publishing set-valued data is an important problem. However, privacy notions proposed in prior works either assume that the adversary has unbounded knowledge and hence provide over-protection that causes excessive distortion, or ignore the knowledge about the absence of certain items and do not prevent attacks based on such knowledge. To address these issues, we propose a new privacy notion, (k,l)^(m,n)-privacy, which prevents both the identity disclosure and the sensitive item disclosure to a realistic privacy adversary who has bounded knowledge about the presence of items and the bounded knowledge about the absence of items. In addition to the new notion, our contribution is an efficient algorithm that finds a near-optimal solution and is applicable for anonymizing real world databases. Extensive experiments on real world databases showed that our algorithm outperforms the state of the art algorithms.