This paper extends the concept of the specific verification function (SVF), introduced by Cui et al. in formally describing the Naor transformation, from hierarchical identity-based encryption (HIBE) to hierarchical identity-based cryptog-raphy (HIBC), including hierarchical identity-based signature (HIBS), where the Naor transformation can convert a secure (H)IBE scheme to a secure (H)IBS one. We formulate this extended concept, checkable key generation (CKG), give its syntax, and classify it into two types: fully and partially ones. We also define security notions of CKG, named unextractability (UE) against several attacks. Next, we show that an$\boldsymbol{\ell}$-level CKG component can be constructed from an$\boldsymbol{\ell}$-level HIBS scheme, and an$\boldsymbol{\ell}$-level HIBS scheme can be constructed from an$(\ell+1)$-level CKG component. Both give security enhancement of HIBS from a weakly secure scheme to a strongly secure one. In addition, we mention that an HIBS scheme with constant-size signatures can be constructed from a partially CKG component.

This paper examines a security enhancement technique from a passively secure hierarchical identity-based identification (HIBI) protocol to a concurrently secure one. Two types of security enhancement techniques for the identification protocols have been proposed: one based on the OR-proof technique and the other using a chameleon hash function. The former has been examined in detail, while the latter has not been formulated in the HIBI protocol, and its close evaluation of applicability, especially in identity-selecting settings, and reduction efficiency has not been made public. We describe a transformation using a chameleon hash function and compare it with the others based on the OR-proof technique in applicability and reduction efficiency.

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.

This paper discusses how to realize practical post-quantum authenticated key exchange (AKE) with strong security, i.e., CK+ security (Krawczyk, CRYPTO 2005). It is known that strongly secure post-quantum AKE protocols exist on a generic construction from IND-CCA secure key encapsulation mechanisms (KEMs) in the standard model.