Fully Dynamic Group Signature Scheme with Member Registration and Verifier-Local Revocation

Abstract

Since Bellare et al. (EUROCRYPT 2003) proposed a security model for group signature schemes, almost all the securities of group signature schemes have been discussed in their model (the BMW03 model). While the BMW03 model is for static groups, Bellare et al. in 2005 considered the case of dynamic group signature schemes and provided a solution to cope with dynamic groups. However, their scheme does not serve member revocation, serves only member registration. In this paper, we incorporate a member revocation mechanism into a group signature scheme with member registration and construct a fully dynamic group signature, which supports verifier-local revocation (VLR) to manipulate member revocation. Moreover, we achieve the security of the proposed scheme with a restricted version of full anonymity to overcome the security complications that may arise due to member revocation.

1 Introduction

The notion of group signature was first introduced by Chaum and van Heyst [12] in 1991. Each member has a private signing key and a corresponding public key. The private signing key is used to generate signatures on messages while the public key is used as a public verification key by verifiers to authenticate the signatures. Group signatures allow group members to sign anonymously on behalf of the group (anonymity). Only the authorized person can reveal the identity of the member who signs (traceability).

Besides the naive security notions (anonymity and traceability) for group signatures, more security requirements like un-frameability, collusion resistance, and unforgeability are proposed. In 2003, Bellare et al. [2] suggested a formal security notion with full anonymity and full traceability to provide a stronger security for group signature schemes (the BMW03 model). This BMW03 model supports only for static groups, not for dynamic groups. Hence, it does not guarantee the security when group members can be flexibly reorganized.

In the setting of dynamic group signatures, neither the number of group members nor their keys should be fixed in the setup phase. Thus, a scheme should be able to register or revoke members anytime. In 2005, Bellare et al. [3] suggested a scheme by providing foundations for dynamic group signatures. The scheme in [3] helps to bridge the gap between the results in [2], and the previous works are done to deliver a dynamic group signature scheme. The dynamic groups are more complex than the static groups since they require many security concerns and deliver more issues to be focused. Schemes in [3] and [14] provide formal security definitions for dynamic group signatures to overcome those issues. Another scheme was suggested by Libert et. al. [15]. However, none of them are fully dynamic group signature schemes since they do not support member revocation. Recently, Bootle et. al. [7] suggested a security definition for fully dynamic group signature schemes and they have also provided some fixes for existing schemes. Hereafter, if a scheme supports both member registration and member revocation, we refer to it as fully dynamic, and if a scheme supports either member registration or revocation, we refer to it as dynamic.

The member revocation is an essential requirement in practice, and many researchers presented various approaches to manage member revocation in groups. One approach is replacing the group public key and the private signing keys with new keys for all existing members when a member is revoked. Since this requires to update all the existing members and the verifiers, it is not the best solution, especially not suitable for large groups. In 2001, Bresson et al. [8] provided a solution that requires signers to prove, at the time of signing, that their member certificates are not in the public revocation list. In 2002, Camenisch et al. [11] proposed a different approach, which is based on dynamic accumulators. It maps a set of values into a fixed-length string and permits efficient proofs of memberships. However, this approach requires existing members to keep track of the revoked users. Thus, it increases the workload of existing members. Moreover, schemes in [5, 10, 18] have taken some other revocation approache.

A different and simple revocation mechanism was suggested by Brickell [9], which was subsequently formalized by Boneh and Shacham [6]. This revocation mechanism is known as Verifier-Local Revocation (VLR). VLR allows the members to convince the verifiers that they are valid members, who are not revoked and eligible to sign on behalf of the group. Every member has a unique token, and when he is revoked, this token is added to a list called Revocation List (RL). Then, the group manager passes the latest RL to the verifiers. When a verifier needs to authenticate a signature, he checks the validity of the signer with the help of RL. Since the verifiers are smaller in number than the members, this mechanism is more convenient than any others, especially for large groups. Moreover, this is advantageous to the previous approaches since it does not affect on existing members.

Our Contribution

This paper presents a fully dynamic group signature scheme that allows to both add and revoke members and a new security notion to overcome some security barriers.

First, we take the scheme in [3], which includes an interactive protocol, that allows new users to join the group at any time, and we incorporate with member revocation mechanism by adapting the methods in the scheme in [3] and suggesting new methods to manage member revocation with VLR.

Then, we suggest a method to generate member revocation tokens in our scheme. In general, any VLR scheme consists of a token system and those tokens are generated as a part of the secret signing key. Since our intention is to apply full anonymity which requires to provide all the secret signing keys to an adversary at the anonymity game, this method is not suitable for our scheme. If we generate revocation tokens using the signing keys of the members, the adversary can obtain the tokens of the challenged indices and win the anonymity game. Thus, to present a member’s token, we use his personal secret key (usk[i]) and his verification key ($\textit{pk}_i$). Nevertheless, $\textit{pk}_i$ is a public attribute, revealing $\textit{pk}_i$ does not show any other information about the member. Even though usk[i] is a secret key, no one can generate any secret signing key by usk[i]. Besides, no one can create a group member token using the secret signing key, since the token is not a part of the secret signing key. Thus, it ensures the security of the scheme.

Moreover, we present a new security notion that is somewhat weaker than the full anonymity. VLR relies on a weaker security notion called selfless-anonymity. Even our intention is to apply full anonymity for our scheme, achieving full anonymity suggested in the BMW03 model for VLR is quite difficult. In case of the anonymity game (for the definition) between a challenger and a adversary, the BMW03 model passes all the secret keys to the adversary. But, we cannot allow the adversary to reveal all the secret keys since he can corrupt the anonymity of the scheme. If we allow the adversary to reveal all the users’ personal private keys (usk), which we use to create tokens he can create any token, including the challenged users’ tokens. Then, he can verify the challenging signature and return the correct user index of the challenged signature. Thus, we suggest a new restricted version of full anonymity (almost-full anonymity), which will not provide all the secret keys to the adversary to ensure the security of our scheme. It will allow the adversary to reveal any member’s secret signing keys not the member’s personal private keys.

2 Preliminaries

In this section, we describe notations used in the paper and the primitives with which we use to construct our scheme. Construction of dynamic group signature schemes use three building blocks: public-key encryption schemes secure against chosen-ciphertext attack [13], digital signature schemes secure against chosen-message attack [1], and simulation-sound adaptive non-interactive zero-knowledge (NIZK) proofs for NP [17]. All the three primitives are based on trapdoor permutation.

2.1 Notation

We denote by $\lambda$ the security parameter of the scheme and let $\mathbb {N} = \{1, 2, 3, \ldots \}$ be the set of positive integers. For any $\textit{k} \ge {1} \in \mathbb {N}$, we denote by [k] the set of integers {1, ..., k}. An empty string is denoted by $\varepsilon$. If s is a string, then $|s|$ denotes the length of the string and if $\mathcal {S}$ is a set then $|\mathcal {S}|$ denotes the size of the set. If $\mathcal {S}$ is a finite set, b $\overset{\$}{\leftarrow }$ $\mathcal {S}$ denotes that b is chosen uniformly at random from $\mathcal {S}$. We denote experiments by Exp.

2.2 Digital Signature Schemes

A digital signature scheme DS = ($\textsf {K}_s, \textsf {Sig}, \textsf {Vf}$) consists of three algorithms: key generation $\textsf {K}_s$, signing Sig, and verification Vf. The scheme DS should satisfy the standard notion of unforgeability under chosen-message attack.

For an adversary $\mathcal {A}$, consider an experiment $\mathbf{Exp }_{DS ,\mathcal {A}}^{\textit{unforg-cma}}(\lambda )$. First, a pair of a public key and the corresponding secret key for the scheme DS is obtained by executing $\textsf {K}_s$ with the security parameter $\lambda$ as (pk, sk) $\overset{\$}{\leftarrow }$ $\textsf {K}_s(1^{\lambda })$. Then, the public key pk is given to the adversary, and the adversary can access the signing oracle $\textsf {Sig}(\mathbf{sk },\cdot )$ for any number of messages. Finally, the forging adversary $\mathcal {A}$ outputs (m, $\sigma$). He wins if $\sigma$ is a valid signature on the message m and m is not queried so far. We let $\mathbf{Adv }^{\textit{unforg-cma}}_{DS ,\mathcal {A}}(\lambda ) = \Pr [\mathbf{Exp }^{\textit{unforg-cma}}_{DS ,\mathcal {A}}(\lambda )=1]$.

A digital signature scheme DS is secure against forgeries under chose message attack if $\mathbf{Adv }^{\textit{unforg-cma}}_{DS ,\mathcal {A}}(\lambda )$ is negligible in $\lambda$ for any polynomial-time adversary $\mathcal {A}$.

2.3 Encryption Scheme

An encryption scheme E = ($\textsf {K}_e, \textsf {Enc}, \textsf {Dec}$) consists of three algorithms: key generation $\textsf {K}_e$, encryption Enc, and decryption Dec. The scheme E should satisfy the standard notion of indistinguishability under adaptive chosen-ciphertext attack.

For an adversary $\mathcal {A}$, consider an experiment $\mathbf{Exp }_{E , \mathcal {A}}^{\textit{ind-cca-b}}(\lambda )$. First, a pair of a public key and the corresponding secret key for the encryption scheme E is obtained by executing $\textsf {K}_e$ with the security parameter $\lambda$ and a randomness string $r_e$ (where the length of $r_e$ is bounded by some fixed polynomial $r(\lambda )$) as (pk, sk) $\overset{\$}{\leftarrow }$ $\textsf {K}_e(1^{\lambda }, r_e)$. Let LR($m_0, m_1, b$) a function which returns $m_b$ for a bit $b$ and messages $m_0, m_1$. We assume the adversary $\mathcal {A}$ never queries $\textsf {Dec}(\mathbf{sk }, \cdot )$ on a ciphertext previously returned by $\textsf {Enc}(\mathbf{pk }, \textsf {LR}(\cdot , \cdot , b))$. We let $\mathbf{Adv }^{\textit{ind-cca}}_{E , A}(\lambda ) = |\Pr [\mathbf{Exp }^{\textit{ind-cca-1}}_{E ,\mathcal {A}}(\lambda )=1] - \Pr [\mathbf{Exp }^{\textit{ind-cca-0}}_{E ,\mathcal {A}}(\lambda )=1]|$.

An encryption scheme E is IND-CCA secure if $\mathbf{Adv }^{\textit{ind-cca}}_{E, \mathcal {A}}(\lambda )$ is negligible in $\lambda$ for any polynomial-time adversary $\mathcal {A}$.

2.4 Simulation-Sound Non-interactive Zero-Knowledge Proof System

A two-party game between a prover and a verifier which needs to determine whether a given string belongs to a language or not is called an interactive system. The interactive system allows to exchange messages between the prover and the verifier. Besides, argument systems are like interactive proof systems, except they are required to be computationally infeasible for a prover to convince the verifier to accept inputs not in the language. Non-interactive proof systems are mono-directional [4]. The non-interactive proof systems allow a prover to convince a verifier about a truth statement while zero-knowledge ensures that the verifier learns nothing from the proof other than the truth of the statement. The non-interactive zero-knowledge proof system shows that without any interaction but using a common string computational zero-knowledge can be achieved. In a simulation-sound NIZK proof system, an adversary cannot prove any false statements even after seeing simulated proofs of arbitrary statements.

An NP-$relation~over~domain$ Dom $\subseteq \{0, 1\}^*$ is a subset $\rho$ of $\{0, 1\}^* \times \{0, 1\}^*$. We say that $x$ is a theorem and $w$ is a proof of $x$ if $(x, w) \in \rho$. The membership of $(x, w) \in \rho$ is decidable in time polynomial in the length of the first argument for all $x$ in Dom.

We fix an NP relation $\rho$ over Dom and take a pair of polynomial-time algorithms ($P, V$), where $P$ is randomized, and $V$ is deterministic. Both $P$ and $V$ have access to a common reference string R. The ($P,V$) is a non-interactive proof system for $\rho$ over Dom if the following two conditions are satisfied for polynomials $p$ and $l$.

• Completeness: $\forall \lambda \in \mathbb {N}, \forall (x, w) \in \rho$ with $|x| \le l(\lambda )$ and $x \in Dom$ :

  Pr [$R \overset{\$}{\leftarrow }\{0, 1\}^{p(\lambda )} ;~\pi \overset{\$}{\leftarrow }P(1^{\lambda }, x, w, R): V(1^{\lambda }, x, \pi , R)$ = 1] = 1.

• Soundness: $\forall \lambda \in \mathbb {N}, \forall \hat{P}$ and $x \in Dom$ such that $x \notin L_{\rho }$:

  $\Pr [R \overset{\$}{\leftarrow }\{0, 1\}^{p(\lambda )} ;~\pi \overset{\$}{\leftarrow }\hat{P}(1^{\lambda }, x, R): V(1^{\lambda }, x, \pi , R)$ = 1] $\le 2^{-\lambda }$.

3 Our Scheme

We construct our scheme based on the scheme in [3]. In the scheme in [3], they have taken a digital signature scheme DS = ($\textsf {K}_s, \textsf {Sig}, \textsf {Vf}$) and a public-key encryption scheme E = ($\textsf {K}_e, \textsf {Enc}, \textsf {Dec}$) as the building blocks to construct a group signature scheme GS. Moreover, they have used NIZK proof system to convince the verifier the validity of the signature. We also use above-mentioned primitives; DS, E, and NIZK to present a new scheme FDGS = (GKg, UKg, Join, Issue, Revoke, Sign, Verify, Open, Judge). GKg, UKg, and Judge are same as the scheme in [3]. We provide a new algorithm Revoke to revoke members, and we modify Join, Issue, Sign, Verify, and Open to be compatible with the revocation mechanism. We use DS for generating the group manager’s keys and E for generating the opener’s keys. Thus, our group public key gpk consists of the security parameter $\lambda$, public keys of group manager and opener, and two reference strings $R_1, R_2$ obtained for NIZK proof.

We describe our group-joining protocol which executes Join and Issue in Fig. 1, and we describe other algorithms of our scheme in Fig. 2.

Fig. 1

Group-joining protocol

Fig. 2

Algorithms of the new fully dynamic group signature scheme

3.1 Coping with VLR and Making the Scheme Secure

In general, VLR schemes satisfy a weaker security notion called selfless-anonymity, which does not provide any secret keys to the adversary. Even though our scheme supports VLR mechanism, we make our scheme more secure by using the techniques in [3] scheme and suggesting a new security notion called almost-full anonymity. Making VLR scheme fully anonymous is quite difficult since the full anonymity requires to provide all the secret keys to the adversary and providing tokens to the adversary makes the scheme insecure. The adversary can execute Verify with the tokens of the challenged indices and win the game easily. Thus, we consider a new security notion called almost-full anonymity which will not provide tokens to the adversary, which is a restricted version of the full anonymity.

Moreover, any VLR scheme has an associated tracing mechanism called implicit tracing algorithm to trace signers. The implicit tracing algorithm requires to run Verify linear times in the number of group members. Compare to the explicit tracing algorithm, which is used in schemes like [16], use of the implicit tracing algorithm increases the time consumption. Hence, instead of using the implicit tracing algorithm given in VLR, we use algorithms provided in [3] for our scheme’s tracing mechanism.

As well, VLR manages a token system. Thus, our scheme should consist user tokens and those tokens should be unique to the users. Furthermore, tokens should not reveal user’s identity in case of disclosing to the outsiders. We generate tokens for members, which will not expose identity of the members even though tokens are opened to the outsiders. We use the combination of each group member’s personal secret key and his verification key as his token, and we maintain the list RL with revoked members’ tokens.

3.2 Description of Our Scheme

There are two authorities, group manager and opener. The trusted setup is responsible for generating the group public key and keys for the authorities. The group manager manages member registration and member revocation while the opener traces signers.

When a new user wants to join the group, he interacts with the group manager via group-joining protocol (Fig. 1), which allows new users to generate their public key and secret keys. We assume this interaction between the new user, and the group manager is done through a secure channel. The new user produces a signature on his verification key and sends both the signature and the key to the group manager. If the signature is acceptable, then the group manager accepts him as a new member. In the registration table reg, we maintain a field called Status for each member to identify the active status of them. Thus, the group manager stores the index i, verification key $\textit{pk}_{\textit{i}}$, and the signature $\textit{sig}_{\textit{i}}$ of the new member in reg and makes the status of the new member as active. After that, the group manager issues member certification to the new member. Now the new member can generate signatures on messages using his secret key.

Each member has a unique token, which is the tracing key to identify the validity of signers, whether they are revoked or not. Here we use the member’s personal secret key $usk[i]$ and his verification key $\textit{pk}_{\textit{i}}$ as the token since $usk[i]$ or $\textit{pk}_{\textit{i}}$ does not help to reveal any other information. We check the existence of the new user keys against reg at the joining protocol. Thus, in a situation that a revoked member wants to join again, he cannot use his previous keys, and he has to follow the process as a new user. That is to secure the scheme against adversaries who steal tokens and try to join the group. During the member revocation, the group manager adds the revoking member’s token to RL and updates reg to inactive. When a member needs to sign a message, he generates the signature on a message with his secret key and passes to the verifier with his token for verification. The verifier authenticates the signature on the given message and checks the validity of the signer with the provided token against the latest RL. In the case of necessity to trace the signer, the opener can trace the signer using opener’s key, and he can check the status of the signer in reg.

Our scheme is a tuple FDGS = (GKg, UKg, Join, Issue, Revoke, Sign, Verify, Open, Judge), which consists of polynomial-time algorithms. Each algorithm is described in below. GKg, UKg, and Judge are same as in [3] and Join, Issue, Sign, Verify, and Open are different from the algorithms given in [3] since we have to generate and pass the member’s token as an additional attribute in our scheme. Revoke helps to revoke the misbehaved users.

• GKg($1^\lambda$): On input $1^\lambda$, the trusted party obtains a group public key gpk and authority keys, ik and ok. Then gives secret keys, ik to the group manager and ok to the opener.

• UKg($1^\lambda$): Every user who wants to be a member should run this algorithm before the group-joining protocol to obtain their personal public key and personal private key (upk[i], usk[i]). UKg takes as input $1^\lambda$. We assume upk is publicly available.

• Join, Issue: The group-joining protocol is an interactive protocol between the group manager and the user who wants to be a member. Join is implemented by the user while Issue is implemented by the group manager. Join allows new users to generate keys and a signature on the keys which are needed to join the group. Issue allows the group manager to validate the keys and the signatures sent by users and generate member certifications. Each algorithm takes an incoming message as input and returns an outgoing message. Join and Issue maintains their current status for both parties. The user i generates a public / secret key pair $\textit{pk}_i$ and $\textit{sk}_i$. Then, he produces a signature $\textit{sig}_i$ on $\textit{pk}_i$ using usk[i], which was obtained in UKg. Then, user sends $\textit{sig}_i$ and $\textit{pk}_i$ to the group manager to authenticate. The group manager authenticates the signature $\textit{sig}_i$ on $\textit{pk}_i$ and generates member certification by signing $\textit{pk}_i$ with his private key ik (gmsk). The group manager stores new member’s informations, i, $\textit{pk}_i$, and $\textit{sig}_i$ with the status as 1 (active) in reg. Then, he sends member certification $\textit{cert}_i$ to the user who is the new member of the group. After that new user can make his secret key gsk[i] = (i, $\textit{pk}_i$, $\textit{sk}_i$, $\textit{cert}_i$), and his token grt[i] = ($\mathbf{usk }[\textit{i}], \textit{pk}_i$).

• Revoke(i, grt[i], ik, RL, reg): This algorithm takes, index i of the member, who wants to be revoked and the group manager’s secret key ik as inputs. First, the group manager queries reg using the index i to obtain the information of the member stored. Then, he checks whether the queries are equal to the data obtained by parsing the grt[i]. If the data are equal and if the user is active, insert (usk[i], $\textit{pk}_i$) to RL and updates reg to 0 (inactive).

• Sign(gpk, gsk[i], grt[i], m): This randomized algorithm generates a signature $\sigma$ on a given message m. It takes the group public key gpk, the group member’s secret key gsk, and the message m as inputs. In addition, we pass the group member’s token as an input to prove that the member is an active person at the time of signing.

• Verify(gpk, m, $\sigma$, RL): This deterministic algorithm allows anyone in possession of group public key gpk to verify the given signature $\sigma$ on the message m and checks the validity of the signer against RL. This algorithm outputs 1 if both conditions are valid. Otherwise, it returns 0.

• Open(gpk, ok, reg, m, $\sigma$): This deterministic algorithm traces the signer by taking gpk, the opener’s secret key ok, reg, the message m, and the signature $\sigma$ as inputs. It returns the index of the signer, the proof of the claim $\tau$, and the status of the signer st at reg. If the algorithm failed to trace the signature to a particular group member, it returns (0, $\varepsilon$, 0).

• Judge(gpk, i, upk[i], m, $\sigma$, $\tau$): This deterministic algorithm outputs either 1 or 0 depending on the validity of the proof $\tau$ on $\sigma$. This takes, the group public key gpk, the member index i, the tracing proof $\tau$, the member verification key upk[i], the message m, and the signature $\sigma$ as inputs. The algorithm outputs 1 if $\tau$ can proof that i produced $\sigma$. Otherwise, it returns 0.

In addition, we use the following simple polynomial-time algorithm.

• IsActive(i,reg): This algorithm determines whether the member i is active by querying the registration table and outputs either 0 or 1.

4 Security Notions of the Scheme

Even though the BMW03 model has two key requirements, full anonymity and full traceability, the scheme in [3] has three key requirements; anonymity, traceability, and non-frameability. Since full traceability discussed in the BMW03 model covers both traceability and non-frameability, the BMW03 model has only two requirements. In the setting of [3], traceability and non-frameability are separated since non-frameability can be achieved with lower levels of trust in the authorities than traceability as discussed below. According to the scheme in [3], the opener’s secret key is provided to an adversary in traceability game but, the issuer’s secret key is not provided. The scheme in [3], they assume that the opener is partially corrupted in traceability. But in non-frameability, both the opener’s and the tracer’s secret keys are given to the adversary. Thus, the adversary is stronger in non-frameability than in traceability. Thus, non-frameability is separated from the traceability in [3]. Moreover, anonymity allows the adversary to corrupt the issuer in [3]. Thus, we provide the issuer’s secret key to the adversary but not the opener’s secret key.

However, the scheme in [3] does not support member revocation but our scheme supports. Thus, we adapt the security experiments and the oracles to be compatible with VLR. Before we discuss the security notions, we define the set of oracles that we use. We suggest a new oracle, revoke to maintain the member revocation queried by any adversary.

For the requirement of anonymity, we suggest a restricted version of full anonymity. In the full-anonymity game, we provide all the members’ secret keys to the adversary including challenged indexes’ keys to the adversary. In our scheme, this may help the adversary to create the challenged indexes’ tokens since he knows all the members’ personal secret keys (usk) and he can execute Verify to check which index is used to generate the challenged signature. Thus, we will not provide users’ personal secret keys to the adversary when he requests for user’s secret keys. However, he can request for any private signing key. Hence, we suggest a new security notion almost-full anonymity to show the security of our scheme. Since the almost-full anonymity does not allow members’ personal secret keys to the adversary, it is somewhat weaker than the full anonymity, and since, it provides members’ secret signing keys including challenged indices’ to the adversary, it is stronger than the selfless-anonymity.

Fig. 3

Oracles

4.1 The Oracles

All the oracles that we use are specified in Fig. 3. We maintain a set of global lists, which are manipulated by the oracles in the security experiments discussed later. HUL is the honest user list, which maintains the indexes of the users who are added to the group. When the adversary corrupts any user, that user’s index is added to CUL. SL carries the signatures that obtained from Sign oracle. When the adversary requests a signature, the generated signature, the index, and the message are added to SL. When the adversary accesses Challenge oracle, the generated signature is added to CL with the message sent. We use a set S to maintain a set of revoked users.

• AddU(i): The adversary can add a user $\textit{i} \in \mathbb {N}$ to the group as an honest user. The oracle adds i to HUL and selects keys for i. It then executes the group-joining protocol. If Issue accepts, then adds the state to reg and if Join accepts then generates gsk[i]. Finally, returns upk[i].

• CrptU(i, upk): The adversary can corrupt user i by setting its personal public key upk[i] to upk. The oracle adds i to CUL and initializes the issuer’s state in group-joining protocol.

• SendToIssuer(i, $\textit{M}_{in}$): The adversary acts as i and engages in group-joining protocol with Issue-executing issuer. The adversary provides i and $\textit{M}_{in}$ to the oracle. The oracle which maintains the Issue state returns the outgoing message and adds a record to reg.

• SendToUser(i, $\textit{M}_{in}$): The adversary corrupts the issuer and engages in group-joining protocol with Join-executing user. The adversary provides i and $\textit{M}_{in}$ to the oracle. The oracle which maintains the user i state, returns the outgoing message, and sets the private signing key of i to the final state of Join.

• RevealU(i): The adversary can reveal secret keys of the user i. We only provide user’s private signing key gsk[i] not his personal private key usk[i].

• ReadReg(i): The adversary can read the entry of i in reg.

• ModifyReg(i, val): The adversary can modify the contents of the record for i in reg by setting val.

• Sign(i, m): The adversary obtains a signature $\sigma$ for a given message m and user i who is an honest user and has private signing key.

• $\textsf {Chal}_b$($\textit{i}_0, \textit{i}_1, \textit{m}$): This oracle is for defining anonymity and provides a group signature for the given message m under the private signing key of $\textit{i}_b$, as long as both $\textit{i}_0, \textit{i}_1$ are active and honest users having private signing keys.

• Revoke(i): The adversary can revoke user i. The oracle updates the record for i in reg and adds revocation token of i to the set S.

• Open(m, $\sigma$): The adversary can access this opening oracle with a message m and a signature $\sigma$ to obtain the identity of the user, who generated the signature $\sigma$. If $\sigma$ is queried before for $\textsf {Chal}_b$, oracle will abort.

4.2 Correctness

The notion of correctness requires that any signature generated by any honest and active users should be valid and Open should correctly identify the signer for a given message and a signature. Moreover, the proof returned by Open should be accepted by Judge. Hence, any scheme is correct if the advantage of the correctness game is 0, for all $\lambda \in \mathbb {N}$ and for any adversary A.

We let, $\mathbf{Adv }^{corr}_{FDGS, A}(\lambda ) = \Pr [\mathbf{Exp }^{corr}_{FDGS, A}(\lambda )=1]$.

$\underline{{\mathbf{Exp }}_{FDGS, A }^{corr}(\lambda )}$

$(\mathbf{gpk }, \mathbf{ok }, \mathbf{ik }) \leftarrow \textsf {GKg}(1^{\lambda })$; $\mathbf{HUL }\leftarrow \emptyset$; $(i, m)\leftarrow A (\mathbf{gpk }; \textsf {AddU},\textsf {ReadReg},\textsf {Revoke})$;

If i $\notin \mathbf{HUL }$ or $\mathbf{gsk }[\textit{i}] = \varepsilon$ or $\textsf {IsActive}(\textit{i}, reg)$= 0, then return 0.

$\sigma \leftarrow \textsf {Sign}(\mathbf{gpk }, \mathbf{gsk }[\textit{i}], \textit{m})$;

If Verify(gpk, m, $\sigma$, S) = 0, then return 1.

$(\textit{i}', \tau )\leftarrow \textsf {Open}(\mathbf{gpk }, \mathbf{ok }, reg, \textit{m}, \sigma )$;

If $i\not = \textit{i}'$, then return 1.

If Judge(gpk, i, upk[i], m, $\sigma$, $\tau$) = 0, then return 1 else return 0.

4.3 Anonymity

The anonymity requires the signatures do not reveal the identity of the signer. In the anonymity game, the adversary’s goal is to identify the index that is used to create the signature. We allow the adversary A to corrupt any user and allow him to fully corrupt the group manager. Also, A can learn secret signing keys of any user. In full-anonymity game, adversary can access all the secret keys of any member. However, we suggest a new security notion almost-full anonymity, which does not allow to reveal the personal secret keys of the users since the adversary can create the tokens of the challenged ones and check with Verify. Hence, he can easily win the game. We say that FDGS scheme is almost-fully anonymous if the advantage of the adversary $\mathbf{Adv }^{anon}_{FDGS, A}(\lambda )$ is negligible for any polynomial-time adversary.

In the game, A selects two active group members and a message to challenge the game. He has to guess which member is used to generate the signature. He wins if he can guess the member correctly. We allow only one guess.

We let $\mathbf{Adv }^{anon}_{FDGS, A}(\lambda ) = \Pr [\mathbf{Exp }^{\textit{anon-0}}_{FDGS, A}(\lambda )=1] - \Pr [\mathbf{Exp }^{\textit{anon-1}}_{FDGS, A}(\lambda )=1]$.

$\underline{{\mathbf{Exp }}_{FDGS, A }^{\textit{anon-b}}(\lambda )}$

$(\mathbf{gpk }, \mathbf{ok }, \mathbf{ik }) \leftarrow \textsf {GKg}(1^{\lambda })$; $\mathbf{HUL }, \mathbf{CUL }, \mathbf{SL }, \mathbf{CL }\leftarrow \emptyset$;

$b^*\leftarrow A (\mathbf{gpk }, \mathbf{ik }; \textsf {CrptU}, \textsf {SendToUser}, \textsf {RevealU}, \textsf {Open}, \textsf {ModifyReg}, \textsf {Revoke}, \textsf {Chal}_b)$;

Return $b^*$;

4.4 Non-Frameability

The non-frameability ensures that any adversary unable to produce a signature can be attributed to an honest member, who did not produce it.

We let $\mathbf{Adv }^{\textit{non-fram}}_{FDGS, A}(\lambda ) = \Pr [\mathbf{Exp }^{\textit{non-fram}}_{FDGS, A}(\lambda )=1]$.

In this game, we only require that the framed member is honest. Thus, the adversary A can fully corrupt the group manager and the opener.

Formally, the FDGS scheme is non-frameable for all $\lambda \in \mathbb {N}$ and for any adversary A.

$\underline{{\mathbf{Exp }}_{FDGS, A }^{\textit{non-fram}}(\lambda )}$

$(\mathbf{gpk }, \mathbf{ok }, \mathbf{ik }) \leftarrow \textsf {GKg}(1^{\lambda })$; $\mathbf{HUL }, \mathbf{CUL }, \mathbf{SL }\leftarrow \emptyset$;

$(\textit{m}, \sigma , \textit{i}, \tau )\leftarrow A (\mathbf{gpk }, \mathbf{ik }, \mathbf{ok };\textsf {CrptU}, \textsf {SendToUser}, \textsf {RevealU}, \textsf {Sign}, \textsf {ModifyReg})$;

If Verify(gpk, m, $\sigma$, S) = 0, then return 0.

If Judge(gpk, i, upk[i], m, $\sigma$, $\tau$) = 0, then return 0.

If $\textit{i} \notin \mathbf{HUL }$ or $(\textit{i}, \textit{m}, \sigma , \tau ) \in \mathbf{SL }$, then return 0 else 1.

4.5 Traceability

The traceability requires any adversary cannot produce a signature that unable to identify the origin of the signature. That means the adversary’s challenge is to generate a signature that cannot be traced to an active member of the group. In this game, A is allowed to corrupt any user and he has the opener’s key, but he is not allowed to corrupt the group manager since he can produce dummy users. He wins if he can create a signature, whose signer cannot be identified or signer is an inactive member when creating the signature, or Judge algorithm does not accept the Open algorithm’s decision.

We let $\mathbf{Adv }^{trace}_{FDGS, A}(\lambda ) = \Pr [\mathbf{Exp }^{trace}_{FDGS, A}(\lambda )=1]$.

$\underline{{\mathbf{Exp }}_{FDGS, A }^{trace}(\lambda )}$

$(\mathbf{gpk }, \mathbf{ok }, \mathbf{ik }) \leftarrow \textsf {GKg}(1^{\lambda })$; $\mathbf{HUL }, \mathbf{CUL }, \mathbf{SL }\leftarrow \emptyset$;

$(\textit{m}, \sigma )\leftarrow A (\mathbf{gpk }, \mathbf{ok };\textsf {AddU}, \textsf {CrptU}, \textsf {SendToIssuer}, \textsf {RevealU}, \textsf {Sign}, \textsf {ModifyReg}, \textsf {Revoke})$;

If Verify(gpk, m, $\sigma$, S) = 0, then return 0.

$(\textit{i}, \tau )\leftarrow \textsf {Open}(\mathbf{gpk }, \mathbf{ok }, reg, \textit{m}, \sigma )$;

If $i=0$ or $\textsf {Judge}(gpk, i, upk[i], m, \sigma , \tau ) = 0$, then return 1 else return 0.

5 Security Proof of Our Scheme

We can prove that our scheme is anonymous, non-frameable and traceable according to the experiments described above and which are discussed in [3] and [7]. Even though our scheme has used a token system as an additional attribute than the scheme in [3], since we are not providing the tokens to the adversary and since we have used the member’s personal secret key usk[i] and his verification key $\mathbf{pk }_{\textit{i}}$ as his revocation token, which cannot be used to learn about the member, there is no impact on the security of the scheme from the token system. Since our scheme requires a reasonable and sufficient security notion for the problem of considering full anonymity, we use almost-full anonymity and we use security experiments provided above instead of experiments given in [3]. However, due to the page limitation, we provide only a summary of security proof and we will give a detailed proof of security in a full version of this paper.

5.1 Anonymity

On the assumption that $P_1$ is computational zero knowledge for $\rho _1$ over $Dom_1$ and $P_2$ is computational zero knowledge for $\rho _2$ over $Dom_2$, two simulations $Sim_1$ and $Sim_2$ can be fixed as $\Pi _1$ = $P_1, V_1, Sim_1$;    $\Pi _2$ = $P_2, V_2, Sim_2$; $\Pi _1$ and $\Pi _2$ are the simulation-sound zero-knowledge non-interactive proof systems of them for $L_{\rho 1}$ and $L_{\rho 2}$, respectively.

For any polynomial-time adversary $B$, who will challenge the anonymity of our scheme and who can construct polynomial-time IND-CCA adversaries $A_0, A_1$ against encryption scheme E, an adversary $A_s$ against the simulation soundness of $\Pi$ and distinguishers $D_1, D_2$ that distinguish real proofs of $\Pi _1$ and $\Pi _2$, respectively, for all $\lambda \in \mathbb {N}$, we say

$$\begin{aligned} \mathbf{Adv }_{FDGS, B}^{anon}(k)&\le \mathbf{Adv }_{{E}, A_0}^{{ind-cca}}(k) + \mathbf{Adv }_{{E},A_1}^{{ind-cca}}(k) + \mathbf{Adv }_{\Pi , A_s}^{ss}(k)\\&\qquad \qquad + 2 \cdot (\mathbf{Adv }_{P_1, Sim_1, D_1}^{zk}(k) + \mathbf{Adv }_{P_2, Sim_2, D_2}^{zk}(k)). \end{aligned}$$

According to the Lemma 5.1 described and proved in [3], we can say the left side function is negligible since all the functions on the right side are negligible under the assumptions on the security of building blocks described. This proves the anonymity of our scheme.

5.2 Non-Frameability

If there is a non-frameability adversary $B$, who creates at most $n(k)$ honest users, where $n$ is a polynomial and who constructs two adversaries $A_2, A_3$ against the digital signature scheme, on the assumption that $(P_1, V_1), (P_2, V_2)$ are sound proof systems for $\rho _1, \rho _2$, respectively, we say

$$\begin{aligned} \mathbf{Adv }_{FDGS, B}^{{non-fram}}(k) \le 2^{-k+1} + n(k) \cdot (\mathbf{Adv }_{DS,A_2}^{unforg-cma}(k) + \mathbf{Adv }_{DS,A_{3}}^{unforg-cma}(k)). \end{aligned}$$

On the assumption that the scheme DS is secure, all the functions on the right side are negligible, so the left side function. Thus, our scheme is non-frameable according to the definition of DS.

5.3 Traceability

If there is a traceability adversary $B$, who constructs an adversary $A_1$ against the scheme DS, on the assumption that ($P_1, V_1$) is a sound proof system for $\rho _1$, we say

$$\begin{aligned} \mathbf{Adv }_{FDGS, B}^{trace}(k) \,\le \, 2^{-k+1} \, + \,\mathbf{Adv }_{DS,A_1}^{{unforg-cma}}(k). \end{aligned}$$

On the assumption that DS is secure against traceability, all the functions on the right side are negligible. Because of this, the advantage of $B$ is negligible. Thus, it proves that our scheme is traceable.

6 Conclusion

In this paper, we have presented a simple fully dynamic group signature scheme that can be used as a basic scheme to develop with different approaches. We have constructed our scheme based on the scheme in [3] and proposed Verifier-Local revocation mechanism, which ease member revocation and convenient for large groups. Thus, our scheme is more flexible and suitable for dynamically changing groups, even they are large. We have shown how to achieve the security with almost-fully anonymity, which is a limited version of fully anonymity.