International Association
for Cryptologic Research

Group signature is a class of digital signatures with enhanced privacy. By using this type of signature, a user can prove membership of a specific group without revealing his identity, but in the case of a dispute, for a given signature, an authority can expose the identity of its signer. However, in some situations wherein it is necessary to only know whether a specified user is the signer of the given signature, the naive use of a group signature may be problematic since if the specified user is NOT the actual signer, then the identity of the actual signer will be exposed.

In this paper, inspired by this problem, we propose the notion of a deniable group signature, where with respect to a signature and a user, the opener can issue a proof that the opening result of the signature is NOT the specified user without revealing the actual signer. We also describe a fairly practical construction by extending the Groth group signature scheme (ASIACRYPT 2007). In particular, a denial proof in our scheme consists of 96 group elements, which is about twice the size of a signature in the Groth scheme. The proposed scheme is provably secure under the same assumptions as those of the Groth scheme.