$(\ell,δ)$-Diversity: Linkage-Robustness via a Composition Theorem

In this paper, we consider the problem of degradation of anonymity upon linkages of anonymized datasets. We work in the setting where an adversary links together $t\geq 2$ anonymized datasets in which a user of interest participates, based on the user's known quasi-identifiers, which motivates the use of $\ell$-diversity as the notion of dataset anonymity. We first argue that in the worst case, such linkage attacks can reveal the exact sensitive attribute of the user, even when each dataset respects $\ell$-diversity, for moderately large values of $\ell$. This issue motivates our definition of (approximate) $(\ell,δ)$-diversity -- a parallel of (approximate) $(ε,δ)$-differential privacy (DP) -- which simply requires that a dataset respect $\ell$-diversity, with high probability. We then present a mechanism for achieving $(\ell,δ)$-diversity, in the setting of independent and identically distributed samples. Next, we establish bounds on the degradation of $(\ell,δ)$-diversity, via a simple ``composition theorem,'' similar in spirit to those in the DP literature, thereby showing that approximate diversity, unlike standard diversity, is roughly preserved upon linkage. Finally, we describe simple algorithms for maximizing utility, measured in terms of the number of anonymized ``equivalence classes,'' and derive explicit lower bounds on the utility, for special sample distributions.