Real hidden identity-based signatures

Group signature allows members to issue signatures on behalf of the group anonymously in normal circumstances. When the need arises, an opening authority (OA) can open a signature and reveal its true signer. Yet, many constructions require not only the secret key of the OA but also a member database (cf. a public-key repository) for this opening. This “secret members list” put the anonymity of members at risk as each of them is a potential signer. To resolve this “anonymity catch-22” issue, Kiayias and Zhou proposed hidden identity-based signatures (Financial Crypt. 2007 and IET Information Security 2009), where the opening just takes in the secret key of the OA and directly outputs the signer identity. The membership list can be hidden from the OA since there is no membership list whatsoever. However, their constructions suffer from efficiency problem. This paper aims to realize the vision of Kiayias and Zhou for real, that is, an efficient construction which achieves the distinctive feature of hidden identity-based signatures. Moreover, our construction is secure against concurrent attack, and easily extensible with linkability such that any double authentication can be publicly detected. Both features are especially desirable in Internet-based services which allow anonymous authentication with revocation to block any misbehaving user. We believe our work will improve the usability of group signature and its variant.