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.

This paper shows by a mathematical model that, for image classification/recognition purposes, high resolution pictures have lower recognition rate than relatively low resolution pictures. The analysis is based on the matching approach by a simple neural network, but we believe that the conclusion remains valid even when the classification process involves complicated matching schemes such as principal component analysis and Gabor transforms.