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.

We study the security of triple encryption in the multi-user setting with its application to Triple DES (TDES) in mind. Although depreciation of TDES is a global trend, the migration will take the next decade, considering the billions of TDES hardware the industry has invested so far. The multi-user security captures the reality of practical systems with multiple users, substantially impacts security, and is already considered in practical protocols such as TLS 1.3. The best multi-user lower bound of TDES is 43-(3/2) \cdot łog_2 u bits with u users, which is tractable with a standard PC and is unacceptably low. We devise a new proof to improve the multi-user security and show its tightness by giving a concrete attack. The new bound with the TDES parameters is 79-(1/2) \cdot łog_2 u bits. We also propose TEFX that strengthens triple encryption with the FX construction while preserving the compatibility with legacy hardware. TDES with TEFX achieves the multi-user security of 114-(1/2) \cdot łog_2 q bits with q TEFX calls: it achieves 84.5 bits with 2^40 users and 2^21 TEFX calls for each user, which is comparable to that of AES (128-40=88 bits).

The Sponge function is known to achieve $$2^{c/2}$$ security, where c is its capacity. This bound was carried over to its keyed variants, such as SpongeWrap, to achieve a $$\min \{2^{c/2},2^\kappa \}$$ security bound, with $$\kappa $$ the key length. Similarly, many CAESAR competition submissions were designed to comply with the classical $$2^{c/2}$$ security bound. We show that Sponge-based constructions for authenticated encryption can achieve the significantly higher bound of $$\min \{2^{b/2},2^c,2^\kappa \}$$ , with $$b>c$$ the permutation size, by proving that the CAESAR submission NORX achieves this bound. The proof relies on rigorous computation of multi-collision probabilities, which may be of independent interest. We additionally derive a generic attack based on multi-collisions that matches the bound. We show how to apply the proof to five other Sponge-based CAESAR submissions: Ascon, CBEAM/STRIBOB, ICEPOLE, Keyak, and two out of the three PRIMATEs. A direct application of the result shows that the parameter choices of some of these submissions are overly conservative. Simple tweaks render the schemes considerably more efficient without sacrificing security. We finally consider the remaining one of the three PRIMATEs, APE, and derive a blockwise adaptive attack in the nonce-respecting setting with complexity $$2^{c/2}$$ , therewith demonstrating that the techniques cannot be applied to APE.