Various models for evaluating anonymity have been proposed so far. Among them,$k$-anonymity is widely known as a typical anonymity measure, guaranteeing that at least$k$individuals in a database have the same values. Unfortunately, it is difficult to create highly useful anonymized data satisfying$k$-anonymity for high-dimensional data because of the curse of dimensionality. Several approaches relaxing$k$-anonymity have been proposed, such as$k^{m}$-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$k^{m}$-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$k^{m}$-anonymity and differential privacy under sampling. These experiments also show relationships between$k$-anonymity and$k^{m}$-anonymity as$k$-anonymity is a special case of$k^{m}$-anonymity in some sense.

This paper explores the relationships between two privacy protection measures:$P$k-anonymity and$\varepsilon$-differential privacy.$P$k-anonymity and$\varepsilon$-differential privacy are proposed by Ikarashi et al. and Dwork et al., respectively, and they are independent privacy measures. The previous research has indicated the relationships between k-anonymity and$(\beta,\ \epsilon,\ \delta)$-differential privacy under sampling, and precisely, have shown that a k-anonymization algorithm can satisfy$(\beta,\ \epsilon,\ \delta)$-differential privacy under sampling within a range of parameters. Although k-anonymity is a stronger notion than Pk-anonymity,$(\beta,\ \epsilon,\ \delta)$-differential privacy under sampling is a weaker one than$\varepsilon$-differential privacy. We introduce a property of anonymization, named record-independence where the processing of one record is not af-fected by the values of other records, and show that a P k- anonymization algorithm can satisfy$\varepsilon$-differential privacy within a range of parameters under the condition where the an-onymization algorithm is record-independent. With the fact that k-anonymity implies Pk-anonymity, k-anonymity meets$\varepsilon{-}$differential privacy. Then, it implies that an algorithm with a strong privacy notion can satisfy a strong one in another privacy measure. Numerical experiments are then performed to give relations among the parameters of$P$k-anonymity and$\varepsilon$-differential privacy.

Various models for evaluating anonymity have been proposed so far. Among them, k-anonymity is widely known as a typical anonymity measure, which guarantees that at least k individuals in a database have the same values. However, it is difficult to create highly useful anonymized data satisfying k-anonymity for high-dimensional data because of the curse of dimensionality. To overcome the problem, several approaches relaxing k-anonymity have been proposed, such as km-anonymity and σ-km-anonymity. Unfortunately, they can only evaluate deterministic anonymization methods.We propose Pkm-anonymity, a variant of km-anonymity, and prove that km-anonymity and Pkm-anonymity are equivalent in a deterministic privacy mechanism. This suggests that our Pkm-anonymity is an extension of kmanonymity. Also, we propose a km-anonymization method for binary data, unlike the previous approaches for non-binary data. The success probability and utility of the proposed method are examined with the number of attributes as a parameter. Our experiments show that the "curse of dimensionality" does not occur up to a dimensionality of 45 and that usefulness does not deteriorate in the range of dimensionality from 10 to 40.