Group signatures with controllable linkability for dynamic membership

In this paper we present a novel group signature scheme for dynamic membership which enables fine-grained control over the release of user information. This scheme could be widely used for various anonymity-based applications such as privacy-preserving data mining and customized anonymous authentication owing to a useful property called controllable linkability. A valid signer is able to create signatures that hide his or her identity as normal group signatures but can be anonymously linked regardless of changes to the membership status of the signer and without exposure of the history of the joining and revocation. From signatures, only linkage information can be disclosed, with a special linking key. Using this controllable linkability and the controllable anonymity of a group signature, anonymity may be flexibly or elaborately controlled according to a desired level. To begin construction of our scheme, we first introduce the Decision Linear Combination (DLC) assumption in a so-called gap Diffie-Hellman group where the DDH problem is tractable but the CDH problem is hard, and we prove that this assumption can be guaranteed in generic bilinear groups. To identify security requirements more precisely, we formally present definitions of anonymity, traceability, non-frameabilty, and linkability. We then prove that our scheme achieves all these security properties in the random oracle model. Our scheme supporting controllable linkability yields a short signature that is only 33.3% longer than the best-known normal group signature. Furthermore, we show that our scheme is comparable to the group signature scheme in terms of the amount of computation for basic operations such as signing, verification, and the key update caused by revocation. Finally, using the linkability for dynamic. membership, computation overhead in opening signer's identity can be significantly reduced or minimized. (C) 2012 Elsevier Inc. All rights reserved.