Anonymous Authentication Scheme with Decentralized Multi-Authorities

We propose an anonymous authentication scheme with a feature that more than one authorities such as license issuers or product providers can admit a single entity by issuing secret keys, and then the entity is able to prove that is has those secret keys associated to its identity, without a central authority. First, we provide the syntax and the security definition of an anonymous authentication scheme with such decentralized multi-authorities. Next, we give a construction of an anonymous authentication scheme in the discrete logarithm setting by using the Okamoto identification scheme and the Pedersen commitment scheme as building blocks. Then we prove that, under the discrete logarithm assumption, our scheme possesses the proving ability of knowing secret keys associated to the single identity, the anonymity, and the security against concurrent attacks of causing misauthentication. The algorithm of our scheme does not need costly pairing computation, and hence our scheme is suitable for devices with less computational resource.