$k^{m}$-Anonymization Meets Differential Privacy Under Sampling

Various models for evaluating anonymity have been proposed so far. Among them, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>-anonymity is widely known as a typical anonymity measure, guaranteeing that at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> individuals in a database have the same values. Unfortunately, it is difficult to create highly useful anonymized data satisfying <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>-anonymity for high-dimensional data because of the curse of dimensionality. Several approaches relaxing <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>-anonymity have been proposed, such as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k^{m}$</tex>-anonymity, to overcome the problem. On the other hand, we have another privacy protection metric, developed by Dwork et al., and it is differential privacy. However, the full protection index for differential privacy, i.e., the level of noise that can satisfy the desired privacy, has not been clarified. This paper shows relationships between <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k^{m}$</tex>-anonymity and differential privacy under sampling, proposed by Li et al., that is, a weak notion of differential privacy. Numerical experiments are then performed to give relations among the parameters of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k^{m}$</tex>-anonymity and differential privacy under sampling. These experiments also show relationships between <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>-anonymity and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k^{m}$</tex>-anonymity as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>-anonymity is a special case of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k^{m}$</tex>-anonymity in some sense.