Privacy-preserving publishing microdata with full functional dependencies

Data publishing has generated much concern on individual privacy. Recent work has shown that different background knowledge can bring various threats to the privacy of published data. In this paper, we study the privacy threat from the full functional dependency (FFD) that is used as part of adversary knowledge. We show that the cross-attribute correlations by FFDs (e.g., Phone → Zipcode  ) can bring potential vulnerability. Unfortunately, none of the existing anonymization principles (e.g., k-anonymity, ℓℓ-diversity, etc.) can effectively prevent against an FFD-based privacy attack. We formalize the FFD-based privacy attack and define the privacy model, (d,ℓ)(d,ℓ)-inference, to combat the FD-based attack. We distinguish the safe FFDs that will not jeopardize privacy from the unsafe ones. We design robust algorithms that can efficiently anonymize the microdata with low information loss when the unsafe FFDs are present. The efficiency and effectiveness of our approach are demonstrated by the empirical study.