We propose an authentication scheme in which users can be authenticated anonymously so long as times that they are authenticated is within an allowable number. The proposed scheme has two features: 1) no one, not even an authority, can identify users who have been authenticated within the allowable number, 2) anyone can trace, without help from the authority, dishonest users who have been authenticated beyond the allowable number by using the records of these authentications. Our scheme can be applied to e-voting, e-cash, electronic coupons, and trial browsing of content. In these applications, our scheme, unlike the previous one, conceals users' participation from protocols and guarantees that they will remain anonymous to everyone.

We say that a signature scheme is strongly existentially unforgeable (SEU) if no adversary, given message/signature pairs adaptively, can generate a signature on a new message or a new signature on a previously signed message. We propose a general and efficient conversion in the standard model that transforms a secure signature scheme to SEU signature scheme. In order to construct that conversion, we use a chameleon commitment scheme. Here a chameleon commitment scheme is a variant of commitment scheme such that one can change the committed value after publishing the commitment if one knows the secret key. We define the chosen message security notion for the chameleon commitment scheme, and show that the signature scheme transformed by our proposed conversion satisfies the SEU property if the chameleon commitment scheme is chosen message secure. By modifying the proposed conversion, we also give a general and efficient conversion in the random oracle model, that transforms a secure signature scheme into a SEU signature scheme. This second conversion also uses a chameleon commitment scheme but only requires the key only attack security for it.

An anonymous credential system enables individuals to selectively prove their attributes while all other knowledge remains hidden. We considered the applicability of such a system to large scale infrastructure systems and perceived that revocations are still a problem. Then we contrived a scenario to lessen the number of revocations by using more attributes. In this scenario, each individual needs to handle a huge number of attributes, which is not practical with conventional systems. In particular, each individual needs to prove small amounts of attributes among a huge number of attributes and the manager of the system needs to certify a huge number of attributes of individuals periodically. These processes consume extremely large resources. This paper proposes an anonymous credential system in which both a user's proving attributes set, which is included in a huge attribute set, and manager's certifying attributes are very efficient. Conclusion Our proposal enables an anonymous credential system to be deployed as a large scale infrastructure system.

Recently, Bellare and Palacio defined the plaintext awareness (PA-ness) in the standard model. In this paper, we study the relationship between the standard model PA-ness and the property about message hiding, that is, IND-CPA. Although these two notions seem to be independent at first glance, we show that PA-ness in the standard model implies the IND-CPA security if the encryption function is oneway. By using this result, we also showed that "PA + Oneway ⇒ IND-CCA2." We also show that the computational PA-ness notion is strictly stronger than the statistical one.