VLR Group Signatures with Indisputable Exculpability and Efficient Revocation

Group signatures have been studied for nearly two decades and have wide applications, such as anonymous authentication and trusted computing. In 2004 Boneh and Shacham first formalized the concept of a group signature scheme with Verifier-Local Revocation (VLR) in which the revocation list is distributed only to the verifiers. This is an interesting revocation model as the signers are not involved in the revocation check and are transparent to the revocation process. Most of the existing VLR group signature schemes including the Boneh and Shacham´s original one do not satisfy exculpability without fully trusted issuer or largely increasing cost. In this paper, we propose a modification to the Boneh and Shacham VLR group signature definition by adding a dispute process to achieve exculpability. We propose a concrete VLR group signature scheme under this new definition. Our scheme is more efficient than previous VLR group signatures schemes, and only takes one exponentiation per revocation check whereas the existing VLR group signature schemes require at least one bilinear map operation per revocation check. Security of our scheme is based on the strong Diffie-Hellman assumption and the decisional Diffie-Hellman assumption in the random oracle model.