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.

Private join and compute (PJC) is a paradigm where two parties owing their private database securely join their databases and compute a function over the combined database. Inner product PJC, introduced by Lepoint et al. (Asiacrypt’21), is a class of PJC that has a wide range of applications such as secure analysis of advertising campaigns. In this computation, two parties, each of which has a set of identifier-value pairs, compute the inner product of the values after the (inner) join of their databases with respect to the identifiers. They proposed inner product PJC protocols that are specialized for the unbalanced setting where the input sizes of both parties are significantly different and not suitable for the balanced setting where the sizes of two inputs are relatively close.

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.

We propose a secure multi-party computation (MPC) protocol that constructs a secret-shared decision tree for a given secret-shared dataset. The previous MPC-based decision tree training protocol (Abspoel et al. 2021) requires $O(2^hmn log n)$ comparisons, being exponential in the tree height $h$ and with $n$ and $m$ being the number of rows and that of attributes in the dataset, respectively. The cause of the exponential number of comparisons in $h$ is that the decision tree training algorithm is based on the divide-and-conquer paradigm, where rows are padded after each split in order to hide the number of rows in the dataset. We resolve this issue via secure data structure that enables us to compute an aggregate value for every group while hiding the grouping information. By using this data structure, we can train a decision tree without padding to rows while hiding the size of the intermediate data. We specifically describes a decision tree training protocol that requires only $O(hmn log n)$ comparisons when the input attributes are continuous and the output attribute is binary. Note that the order is now linear in the tree height $h$. To demonstrate the practicality of our protocol, we implement it in an MPC framework based on a three-party secret sharing scheme. Our implementation results show that our protocol trains a decision tree with a height of 4 in 404 seconds for a dataset of $2^{20}$ rows and 11 attributes.

Secret sharing (SS) has been extensively studied as both a means of secure data storage and a fundamental building block for multiparty computation (MPC). For these purposes, code‐efficiency and MPC‐suitability are required for SS but they are incomparable. Recently, a computational SS and a conversion protocol were proposed. The computational SS is code‐efficient and the conversion protocol converts shares of the computational (code‐efficient) SS into those of an MPC‐suitable SS, and it can be applied to reduce the amount of data storage while maintaining extendibility to MPC. However, this protocol is one‐way: one cannot convert the share of MPC output value. In addition, it is only passively secure. The authors propose three protocols and a new computational SS. The first protocol is the inverse of the existing protocol, that is, it converts an MPC‐suitable SS to the existing SS. The other two protocols are actively secure conversion protocols that convert shares between the new SS and an MPC‐suitable SS. The new computational SS is code‐efficient when the number of parties is small, so these two protocols are for converting between the code‐efficient SS and an MPC‐suitable SS. These two conversion protocols are actively secure in the honest majority.

We propose a multiparty protocol for various computations using comparator networks such as sorting and searching. By repeating the execution of a comparator, the proposed protocol can efficiently detect outlier values, without revealing them. In our scenario, all input values to a comparator network and the intermediate output from each comparator are kept secret assuming the presence of an honest majority. Possible application areas for the proposed protocol include statistical analysis while preserving the privacy of respondents.