Revocable Group Signatures with Compact Revocation List Using Accumulators

Abstract

Group signatures allow a group member to anonymously sign a message on behalf of the group. One of the important issues is the revocation, and lots of revocable schemes have been proposed so far. The scheme recently proposed by Libert et al. achieves that $O(1)$ or $O(\log N)$ efficiency except for the revocation list size (also the revocation cost), for the total number of members $N$ and the number of revoked members $R$. However, since a signature is required for each subset in the used subset difference method, the size is about $900R$ Bytes in the 128-bit security. In the case of $R=100{,}000$, it amounts to about 80 MB. In this paper, we extend the scheme to reduce the revocation list (also the revocation cost). In the proposed scheme, an extended accumulator accumulates $T$ subsets, which is signed for the revocation list. The revocation list size is reduced by $1/T$, although the public key size, membership certificate size and the cost of a witness computation needed for signing increase related to $T$.

This work was supported by JSPS KAKENHI Grant Number 25330153.

1 Introduction

The group signature scheme [13] allows a group member to anonymously sign a message on behalf of the group. In the group signature scheme, two types of trusted parties participate: A group manager ($GM$) has the authority to add a user to the own group. An opener can identify the signer from a signature. One of important issues in the group signature schemes is a revocation that the signing capability of a user is revoked. The revocation may happen, when the user leaves the group voluntarily or the account is banned due to the illegal usage, etc.

Lots of revocable group signature schemes have been proposed (e.g., [6–8, 10–12, 16, 17, 19, 20]). Hereafter, let $N$ be the total number of group members, and $R$ be the number of revoked members. In the early scheme [7], the signature size is $O(R)$ (also, the costs of signing and verification). Then, the accumulator-based scheme has been proposed in [12], which is followed in [11], to achieve the constant-size signature with the constant verification costs. However, each member has to update a secret key (a witness for the accumulator) using the revocation data, which implies that signing costs is $O(R)$ in the worst case.

In [19], revocable schemes with the costs of constant signing and verification have been proposed. The demerit of the schemes is the long public key size. The basic scheme needs $O(N)$ size, and the extended one needs $O(\sqrt{N})$ in exchange for the extra signing cost. Recently, in [17], Libert et al. proposed an elegant scalable scheme using Naor et al.’s broadcast encryption framework [21]. This scheme achieves the constant verification cost, and the polylogarithmic public and secret key sizes. Finally, the same authors proposed the extended version with $O(1)$ secret key size [16], as achieving $O(1)$ signature size, $O(1)$ signing/verification costs and $O(\log N)$ public key size.

In this paper, we consider reducing the revocation list size. In [16], to indicate the revoked members, $O(R)$ size is needed for the revocation list. Furthermore, in the list, a signature is required for each subset in the used subset difference (SD) method, and the number of the signatures is bounded by $2R-1$. The signature is an AHO signature [2], which needs 7 elements of a bilinear group. Assuming 128-bit security, the signature size is 448 Bytes. Thus, the revocation list size is about $900R$ Bytes or more. In an example of $R=10{,}000$, the size amounts to 8 MB or more, and in case of $R=100{,}000$, it becomes 80 MB or more. Note that the signer has to fetch all data of the latest revocation list every revocation epoch, as noted in [3]. This is because fetching a part of the list can reveal the information to trace the signer. Therefore, the large data may cause a delay in mobile environments.

In this paper, we propose a revocable group signature scheme with a compact revocation list as the extension of the state-of-the-art scheme [16]. In our scheme, using an extended accumulator based on [4], $GM$ accumulates $T$ subsets in the SD method, and signs the accumulated value. This is why the number of signatures is reduced by $1/T$. The revocation cost is similar. In case of $R=100{,}000$, the size of the signature data including the accumulated value is reduced to 1,000 KB if $T=100$. The compensation is increasing the public key size, the membership certificate size, and the cost of a witness computation needed for signing. Nevertheless, in case of $T=100$, the public key size is 2,500 KB and the membership certificate size is 13 KB. In real applications, the public key and the certificate are not often distributed. On the other hand, the revocation list has to be distributed every revocation epoch. Thus, we consider that it is sufficiently practical to decrease the revocation list size while increasing the public key and the membership certificate sizes. The witness computation cost is about 120 exponentiations in case of $T=100$. This cost is comparable to the computation cost of commitments in the original signing. This computation is needed only once every revocation epoch. As shown in Sect. 5, we can reduce the cost by computing only the modified parts from the previous epoch. Therefore, we consider that the extra costs are not a serious issue.

Due to the page limitation, the preliminary section reviewing the bilinear map and utilized primitives is in Appendix A.

2 Extended Accumulator

In [11], an efficient pairing-based accumulator is proposed. The accumulator is generated from a set of values, and we can verify that a single value is included in the set. In [22], the extended version is proposed, where we can verify that multiple values are included in the specified set, all at once. In [4], another extension is proposed, where we can verify that, for a set $U$, for all multiple sets $V_1,\ldots , V_T$, a value from $U$ is included in each $V_t$, i.e., $U\cap V_t \ne \emptyset$, all at once. This is applied to the verification for CNF formulas on attributes in the anonymous credential system of [4]. For a CNF formula $(\mathsf {a}_1\in U \vee \cdots \vee \mathsf {a}_{L'}\in U)\wedge (\mathsf {b}_1 \in U\vee \cdots \vee \mathsf {b}_L\in U)\cdots$, setting $V_1=\{\mathsf {a}_1,\ldots , \}, V_2=\{\mathsf {b}_1,\ldots \}$, $\ldots$, we can verify the formula by checking $U\cap V_t \ne \emptyset$ for all $t$.

This paper furthermore extends the accumulator in [4], since our group signature scheme also needs the CNF-type verification. The scheme requires the verification of the logical formula as $(\mathsf {a}_{t1}\in U \wedge \cdots \wedge \mathsf {a}_{tL_t}\in U)\wedge (\mathsf {b}_{t1} \in U\vee \cdots \vee \mathsf {b}_{tL}\in U)$ for some $t$, given $V_t=\{\mathsf {a}_{t1},\ldots , \mathsf {a}_{tL_t}\}, \tilde{V}_t=\{\mathsf {b}_{t1},\ldots , \mathsf {b}_{tL}\}$ for all $1\le t\le T$. The length of the AND relation is variable, but the length of the matched AND relation has to be hidden in the group signature scheme. Thus, we introduce a dummy parameter ${\mathsf {SP}}$. The other point of extension is to unbind the limitation of the number of given sets $(V_1,\tilde{V}_1), \ldots , (V_T, \tilde{V}_T)$, i.e., $2T$. In the previous accumulator, the number is bounded by the order $p$ of the bilinear groups. In our construction, for any $K,D$ s.t. $T=K\cdot D$, the target sets are divided to $((V_{1,1},\tilde{V}_{1,1}),\ldots , (V_{1,D},\tilde{V}_{1,D})),\ldots , ((V_{K,1}, \tilde{V}_{K,1}),\ldots , (V_{K,D}, \tilde{V}_{K,D}))$. Using randomized public parameters $(g_{k,1},\ldots )$ for each $1\le k\le K$, although $D$ is bounded by $p$, $T=K\cdot D$ becomes unbounded.

2.1 Proposed Construction

For all $1\le k\le K$ and all $1\le d \le D$, define $V_{k,d}$ and $\tilde{V}_{k,d}$ as subsets of $\{1,\ldots , n\}$. Define $\mathcal{V} = \{(V_{k,d},\tilde{V}_{k,d})\}_{k=1,\ldots , K, d=1,\ldots , D}$. Let $U$ be a subset of $\{1,\ldots , n\}$ satisfying $U\cap V_{\tilde{k},\tilde{d}} = V_{\tilde{k},\tilde{d}}$ and $U\cap \tilde{V}_{\tilde{k},\tilde{d}} \ne \emptyset$ for some $1\le \tilde{d} \le D$ and some $1\le \tilde{k} \le K$. In this construction, we assume that the maximum of $|V_{k,d}|$ and $|\tilde{V}_{k,d}|$ is $\zeta$ for all $1\le k \le K$ and all $1\le d \le D$. In addition, we assume $(U\cap V_{k,d}) = (U\cap \tilde{V}_{k,d}) = \emptyset$ for all $1\le k \le K$ and all $1\le d \le D$ except some $k'$ and $d'$. If $U\cap V_{\tilde{k},\tilde{d}} = V_{\tilde{k},\tilde{d}}$ and $U\cap \tilde{V}_{\tilde{k},\tilde{d}} \ne \emptyset$, then it implies $k'= \tilde{k}$ and $d'=\tilde{d}$. These assumptions hold in our application to the revocable group signatures. We introduce mutually different special elements ${\mathsf {SP}}_{k,d} \in \mathcal{N}$ for all $k,d$ such that ${\mathsf {SP}}_{k,d}\notin V_{k',d'}$ for all $k',d'$. We assume that ${\mathsf {SP}}_{\tilde{k},\tilde{d}}\in U$ but ${\mathsf {SP}}_{k,d}\notin U$ for any $k\ne \tilde{k}, d\ne \tilde{d}$.

• AccSetup: This is the algorithm to output the public parameters. The inputs are the security parameter ${\mathsf {l}}$ and $n, K, D, \{{\mathsf {SP}}_{k,d}\}_{1\le k\le K,1\le d\le K}, \zeta$. Select bilinear groups $\mathcal{G, T}$ with a prime order $p> 2^{\mathsf {l}}$ and a bilinear map $e$. Select $g\in _R \mathcal{G}$. Select $\gamma ,\eta _1,\ldots , \eta _K\in _R Z_p$, and compute $g_1=g^{\gamma ^1}, \ldots , g_n=g^{\gamma ^n}, g_{n+2}=g^{\gamma ^{n+2}}, \ldots , g_{2n}=g^{\gamma ^{2n}}$, and $g_{k,1} = g_1^{\eta _k},\ldots , g_{k,n}=g_n^{\eta _k}, g_{k,n+2}=g_{n+2}^{\eta _k}, \ldots , g_{k,2n}=g_{2n}^{\eta _k}$ $z_k = e(g,g)^{\eta _k\gamma ^{n+1}}$ for all $1\le k\le K$. For all $1\le d \le D$, compute $c_d = (\zeta +1)^{2d-2}$, $\tilde{c}_d = (\zeta +1)^{2d-1}$ and set $\mathcal{C} = ((c_1,\tilde{c}_1),\ldots , (c_{D},\tilde{c}_{D}))$. We assume that $(\zeta +1) c_{D} < p$. Publish $n, K, D, \{{\mathsf {SP}}_{k,d}\}_{1\le k\le K,1\le d\le K}, \zeta$, $\mathcal{C}, p$, $\mathcal{G, T}, e, g, (g_1,\ldots , g_n$, $g_{n+2}, \ldots , g_{2n}), \{g_{k,1}, \ldots , g_{k,n}$, $g_{k,n+2}$, $\ldots , g_{k,2n}, z_k\}_{k=1}^{K}$ as the public parameters.

• AccGen: This is the algorithm to compute the accumulator using the public parameters. The accumulator $acc_\mathcal{V}$ of $\mathcal{V}$ is computed as

  

• AccWitGen: This is the algorithm to compute the witness that $U\cap V_{\tilde{k},\tilde{d}} = V_{\tilde{k},\tilde{d}}$ and $U\cap \tilde{V}_{\tilde{k},\tilde{d}} \ne \emptyset$ for some $1\le \tilde{d} \le D$ and some $1\le \tilde{k} \le K$, using the public parameters. Given $U$, $\mathcal{V}$, and the accumulator $acc_\mathcal{V}$, the witness is computed as

  $$\begin{aligned} W&= \prod _{i\in U}\prod _{1\le k\le K}\prod _{1\le d \le D}((\prod _{j\in V_{k,d}}^{j\ne i}g_{k,n+1-j+i})^{c_{d}}\cdot (\prod _{j=1}^{\zeta - |V_{k,d}|,i\ne {\mathsf {SP}}_{k,d}} g_{k,n+1-{\mathsf {SP}}_{k,d}+i})^{c_{d}}\cdot \\&\quad (\prod _{j\in \tilde{V}_{k,d}}^{j\ne i}g_{k,n+1-j+i})^{\tilde{c}_{d}}). \end{aligned}$$

  Furthermore, the auxiliary parameters are set as $\tilde{k},\tilde{d}$, $\delta _{\tilde{k},\tilde{d}} = |U\cap \tilde{V}_{\tilde{k},\tilde{d}}|$.

• AccVerify: This is the algorithm to verify that $U\cap V_{\tilde{k},\tilde{d}} = V_{\tilde{k},\tilde{d}}$ and $U\cap \tilde{V}_{\tilde{k},\tilde{d}} \ne \emptyset$ for some $1\le \tilde{d} \le D$ and some $1\le \tilde{k} \le K$, using the witness, the auxiliary parameters, and the public parameters. Given $acc_\mathcal{V}, U$, $W$ $\tilde{k},\tilde{d}$ and $\delta _{\tilde{k},\tilde{d}}$, accept if

  $$\begin{aligned} \frac{e(\prod _{i\in U} g_i,acc_\mathcal{V})}{e(g,W)} = {z_{\tilde{k}}}^{\zeta c_{\tilde{d}}+ \delta _{\tilde{k},\tilde{d}} \tilde{c}_{\tilde{d}}}, \quad \quad 1\le \delta _{\tilde{k},\tilde{d}} \le \zeta . \end{aligned}$$

  (1)

2.2 Security

We can show the correctness and the security. The proofs are shown in the full paper.

Theorem 1

Assume that AccSetup, AccGen, AccWitGen correctly compute all parameters. Then, $\mathbf{AccVerify}$ accepts $U, acc_\mathcal{V}, W, \tilde{k},\tilde{d}$ and $\delta _{\tilde{k},\tilde{d}}$ that they outputs.

Theorem 2

Under the $n$-DHE assumption, any adversary cannot output $(U, \mathcal{V}$, $W$, $\tilde{k},\tilde{d},$ $\delta _{\tilde{k},\tilde{d}})$, on inputs $n, K, D, \{{\mathsf {SP}}_{k,d}\}_{1\le k\le K,1\le d\le K}, \zeta$, $\mathcal{C}, p$, $\mathcal{G, T}, e, g, (g_1,\ldots , g_n$, $g_{n+2}, \ldots , g_{2n}), \{g_{k,1}, \ldots , g_{k,n}$, $g_{k,n+2}$, $\ldots , g_{k,2n}, z_k\}_{k=1}^{K}$ s.t. $\mathbf{AccVerify}$ accepts $U, acc_\mathcal{V}, W, \tilde{k},\tilde{d},$ $\delta _{\tilde{k},\tilde{d}}$ but $U\cap V_{{k'},{d'}} \ne V_{{k'},{d'}}$ or $U\cap \tilde{V}_{{k'},{d'}} = \emptyset$ for some $k',d'$, assuming the following preconditions.

• 1. $(U\cap V_{k,d}) = (U\cap \tilde{V}_{k,d}) = \emptyset$ for all $1\le k \le K$ and all $1\le d \le D$ except $k=k'$ and $d=d'$,

• 2. only ${\mathsf {SP}}_{k',d'}$ is included in $U$ (other ${\mathsf {SP}}_{k,d}$ is not included).

3 Syntax and Security of Revocable Group Signatures

3.1 Syntax

• Setup( $\mathsf {l},N,K,D$ ): Given the security parameter $\mathsf {l}\in \mathbb {N}$, the maximum number of group members $N\in \mathbb {N}$, and the efficiency parameters $K,D\in \mathbb {N}$, this algorithm outputs a group public key $gpk$, a $GM$’s secret key $gsk$, and an opener’s secret key $osk$. This algorithm initializes a public state $St$ comprising a set data structure $St_{users}=\emptyset$ and a string data structure $St_{trans}=\epsilon$.

• Join: This is an interactive protocol between the group manager $GM$ and a joining user $\mathcal{U}_\mathsf {i}$. The interactive Turing machines are denoted as $\mathsf {J}_{GM}$ and $\mathsf {J}_{\mathcal{U}_\mathsf {i}}$, respectively. After the protocol $[\mathsf {J}_{GM}(\mathsf {l}, St, gpk, gsk), \mathsf {J}_{\mathcal{U}_\mathsf {i}}(\mathsf {l}, gpk)]$ is executed, $\mathsf {J}_{\mathcal{U}_\mathsf {i}}$ outputs a membership secret $sec_\mathsf {i}$ and a membership certificate $cert_\mathsf {i}$. The protocol is successful, $\mathsf {J}_{GM}$ updates $St$ by setting $St_{user} = St_{user}\cup \{\mathsf {i}\}$ and $St_{trans} = St_{trans}\Vert \langle \mathsf {i},{\mathsf {transcript}}_\mathsf {i}\rangle$.

• Revoke $(gpk, gsk, \tau , \mathcal{R}_{\tau })$ : Given $gpk, gsk$, epoch $\tau$ and $\mathcal{R}_{\tau }\subset \{1,\ldots , N\}$ that is the identities of revoked members at the epoch $\tau$, this algorithm outputs the revocation list $RL_{\tau }$.

• Sign $(gpk, \tau , RL_{\tau }, cert_\mathsf {i}, sec_\mathsf {i}, M)$ : Given $gpk, \tau , RL_{\tau }$, the signing member’s $cert_\mathsf {i}, sec_\mathsf {i}$, and the message $M$ to be signed, this algorithm outputs $\perp$ if $i\in \mathcal{R}_t$ or the signature $\sigma$ otherwise.

• Verify $(gpk, \tau , RL_{\tau }, \sigma , M)$ : Given $gpk, \tau , RL_{\tau }$, the signature $\sigma$ and message $M$, this algorithm outputs 1 if the signature is valid and not revoked for the revocation list $RL_{\tau }$, or 0 otherwise.

• Open $(gpk, \tau , RL_{\tau },\sigma , M, St, osk)$ : Given $gpk, \tau , RL_{\tau },\sigma , M$ as in Verify, the state $St$ in Join, and the opener’s secret key $osk$, this algorithm outputs $\mathsf {i}\in St_{users}\cup \{\perp \}$ which means the identity of the signer of $\sigma$ or a symbol of an opening failure.

3.2 Security Model

The security of the revocable group signature scheme consists of security against misidentification attacks, security against framing attacks, and anonymity. The security against misidentification attacks requires that the adversary cannot forge a signature that is identified to one outside the set of corrupted and non-revoked members. The security against framing attacks requires that a signature of an honest member cannot be computed by other members and even $GM$. The anonymity captures the anonymity and the unlinkability of signatures. The formal definitions are described in the full paper.

4 A Revocable Group Signature with Compact Revocation List and Constant Verification Time

4.1 Construction Idea

The proposed scheme is based on the previous scheme [16]. The approach of the previous scheme is as follows. The subset cover framework with the SD method is used. To each member, a leaf node $v$ in the binary tree with the height $L$ for $N=2^L$ is assigned. Every node in the tree is assigned to a unique number. In Join, to the member, a membership certificate is issued, which is an AHO signature on a public key and an accumulated data for the node numbers on the path from the root to $v$, ${\mathsf {ID}}_1, \ldots , {\mathsf {ID}}_L$. For the accumulation, they adopt a vector commitment [18] that is similar to the accumulators. In Revoke, $GM$ publishes the revocation list, where each entry consists of accumulated values for primary and secondary nodes in each $S_i$ in the SD method, and the AHO signature on them and the current time epoch $\tau$. In the group signature, to show that the signer is not a revoked member, she proves

• 1. an AHO signature binds between $\tau$ and the primary node with number $\tilde{{\mathsf {ID}}}_{i,\phi _i}$ of level $\phi _i$ and the secondary node $\tilde{{\mathsf {ID}}}_{i,\psi _i}$ of level $\psi _i$ in an $S_i$,

• 2. for ${\mathsf {ID}}_{\phi _i}$ with level $\phi _i$ and ${\mathsf {ID}}_{\psi _i}$ with level $\psi _i$ in the membership certificate, it holds that ${\mathsf {ID}}_{\phi _i}=\tilde{{\mathsf {ID}}}_{i,\phi _i}$ and ${\mathsf {ID}}_{\psi _i} \ne \tilde{{\mathsf {ID}}}_{i,\psi _i}$.

The second relation means that the primary node $\tilde{{\mathsf {ID}}}_{i,\phi _i}$ is an ancestor of $v$ and the secondary node $\tilde{{\mathsf {ID}}}_{i,\psi _i}$ is not, i.e., the subset $S_i$ includes $v$, which implies that the member is not revoked due to the subset cover framework. In this approach, an AHO signature is needed for each subset $S_i$. Each signature needs long data (448 Bytes in 128-bit security), and thus the revocation list becomes long as $R$ increases.

In our approach, to accumulate the revocation list, we adopt the extended accumulator in Sect. 2. Although the same tree structure in the subset cover framework is used, a different coding is used. In the tree, for the edge to the left (resp., right) child in the depth $j$, use index $(j, 0)$ (resp, $(j, 1)$). Then, for the leaf $v$ assigned to the member, let $(1,x_1), \ldots , (L, x_L)$ be the path from the root to the leaf $v$, where $x_\ell \in \{0,1\}$. Similarly, for the subset $S_i$, let $(1,s_{i,1}),\ldots , (\phi _i,s_{i,\phi _i})$ denote the path from the root to the primary root and let $(1,s_{i,1}),\ldots , (\psi _i,s_{i,\psi _i})$ denote the path to the secondary root, where $\phi _i, \psi _i \in \{1,\ldots , L\}$ and $s_{i,j}\in \{0,1\}$. To prove the non-revocation, the signer prove that $((1,x_1)=(1,s_{i_1})) \wedge \cdots \wedge ((\phi _i,x_{\phi _i})=(\phi _i,s_{\phi _i}))$ (i.e., the primary node is an ancestor $v$) and $((\phi _i+1,x_{\phi _i+1})\ne (\phi _i+1,s_{\phi _i+1})) \vee \cdots \vee ((\psi _i,x_{\psi _i})\ne (\psi _i,s_{\psi _i}))$ (i.e., the secondary node is not an ancestor of $v$). The latter relation can be rewritten as $((\phi _i+1,x_{\phi _i+1})= (\phi _i+1,\overline{s_{\phi _i+1}})) \vee \cdots \vee ((\psi _i,x_{\psi _i})=(\psi _i,\overline{s_{\psi _i}}))$.

Using the accumulator, we can prove the relations. Let $T$ be the number of accumulated $S_i$. For $T$, given $K,D$ such that $T =K\cdot D$. For all $1\le t \le T$, consider function $I_t$ mapping $\{(\ell , b)\}_{1\le \ell \le L, b\in \{0,1\}}$ to $\{T+1,\ldots , n\}$ such that $\{I_t(\ell ,b)\}_{1\le \ell \le L, b\in \{0,1\}} \cap \{I_{t'}(\ell ,b)\}_{1\le \ell \le L, b\in \{0,1\}} = \emptyset$ for any pair $1\le t,t'\le T$. Set ${\mathsf {SP}}_{k,d} = D\cdot (k-1) +d$ for all $1\le k \le K$ and $1\le d \le D$. Note that ${\mathsf {SP}}_{k,d}\in \{1,\ldots , T\}$. The relation is required to satisfy the precondition of the accumulator. Define $U_t = \{I_t(1,x_1),\ldots , I_t(L,x_L), {\mathsf {SP}}_{k,d}\}$ for all $1\le t\le T$, where $k = \lceil t/D \rceil$ and $d= t \;\mathrm{mod}\;D$. The accumulated $P_t = \prod _{i\in U_t}g_i$ is embedded into a membership certificate for all $t$. As for the revocation list, for $w = \lceil m/T \rceil$, divide $S_1,\ldots , S_m$ into $w$ sequences:

$$\mathcal{S}_1 = (S_1,\ldots , S_{T}), \mathcal{S}_2 = (S_{T+1},\ldots , S_{2T}),\ldots , \mathcal{S}_w = (S_{(w-1)T+1},\ldots , S_m),$$

where $\mathcal{S}_1,\ldots , \mathcal{S}_{w-1}$ contain $T$ elements and $\mathcal{S}_w$ contains $T$ or less elements. Here, we can connect any $S_{i}$ to the corresponding sequence $\mathcal{S}_{\omega }$ by the relation $\omega = \lceil i/T \rceil$. For each $\mathcal{S}_{\omega }$, do the following. Compute $t = i \;\mathrm{mod}\;T$ to determine the position of $S_i$ in $\mathcal{S}_\omega$. Transform $t$ to the corresponding $(k,d)$ in the accumulator, by $k = \lceil t/D \rceil$ and $d= t \;\mathrm{mod}\;D$. For all $(k,d)$ correspondent $1\le t \le T$ in $\mathcal{S}_\omega$ (i.e., $(\omega -1)T+1\le i\le \omega T$), set $V_{k,d} = \{I_t(1,s_{i,1}),\ldots , I_t(\phi _i, s_{i,\phi _i})\}$ and $\tilde{V}_{k,d} = \{I_t(\phi _i+1, \overline{s_{i,\phi _i+1}}),\ldots , I_t(\psi _i, \overline{s_{i,\psi _i})}\}$. As the revocation list, $GM$ publishes the accumulator $acc_\mathcal{{V}}$ for $\mathcal{V} = \{(V_{k,d},\tilde{V}_{k,d})\}_{k=1,\ldots , K, d=1,\ldots , D}$ together with the AHO signature. By accumulating $S_i$’s into $\mathcal{S}_{\omega }$, the number of published signatures is reduced by $1/T$.

In the group signature, for some $\tilde{t}$, the signer proves that $U_{\tilde{t}}\cap V_{\tilde{k},\tilde{d}} = V_{\tilde{k},\tilde{d}}$ and $U_{\tilde{t}}\cap \tilde{V}_{\tilde{k},\tilde{d}} \ne \emptyset$ for some $1\le \tilde{d} \le D$ and some $1\le \tilde{k} \le K$, using the accumulator verification. The former relation means the AND relation $((1,x_1)=(1,s_{i_1})) \wedge \cdots$ and the latter means that OR relation $((\phi _i+1,x_{\phi _i+1})= (\phi _i+1,\overline{s_{\phi _i+1}})) \vee \cdots$. In the verification relations (1) of the accumulator, the right hand reveals the indexes $\tilde{k}, \tilde{d}$ via $z_{\tilde{k}}, c_{\tilde{d}}, \tilde{c}_{\tilde{d}}$. To hide the indexes, we utilize the technique of membership proof using signatures [9]. Also, we utilize the technique to prove $1\le \delta _{\tilde{k},\tilde{d}} \le \zeta$ in the accumulator.

4.2 Proposed Construction

Setup. The inputs are the security parameter $\mathsf {l}$, the maximum number of group members $N$, and the efficiency parameters $K,D$.

• 1. Select bilinear groups $\mathcal{G}$, $\mathcal{T}$ with the same order $p> 2^{\mathsf {l}}$ and the bilinear map $e$, and $g \in _R \mathcal{G}$.

• 2. Set parameter $T=K\cdot D$.

• 3. Generate public parameters of the extended accumulator: Set $\zeta = L$. Set ${\mathsf {SP}}_{k,d} = D\cdot (k-1) +d$ for all $1\le k \le K$ and $1\le d \le D$. Note that ${\mathsf {SP}}_{k,d}\in \{1,\ldots , T\}$. Select $\gamma ,\eta _1,\ldots , \eta _K\in _R Z_p$, and compute $g_1=g^{\gamma ^1}, \ldots , g_n=g^{\gamma ^n}, g_{n+2}=g^{\gamma ^{n+2}}, \ldots , g_{2n}=g^{\gamma ^{2n}}$, and $g_{k,1} = g_1^{\eta _k},\ldots , g_{k,n}=g_n^{\eta _k}, g_{k,n+2}=g_{n+2}^{\eta _k}, \ldots , g_{k,2n}=g_{2n}^{\eta _k}$ $z_k = e(g,g)^{\eta _k\gamma ^{n+1}}$ for all $1\le k\le K$. For all $1\le d \le D$, compute $c_d = (\zeta +1)^{2d-2}$, $\tilde{c}_d = (\zeta +1)^{2d-1}$ and set $\mathcal{C} = ((c_1,\tilde{c}_1),\ldots , (c_{D},\tilde{c}_{D}))$. Set

  

• 4. Define $n_1=n_3=n_4=2, n_2=1$. Generate four key pairs for the AHO signature:

  $$\begin{aligned}&pk_\mathrm{AHO}^{(d)} = (G_r^{(d)}, H_r^{(d)}, G_z^{(d)}, H_z^{(d)}, \{G_i^{(d)}, H_i^{(d)}\}_{i=1}^{n_d}, A^{(d)}, B^{(d)}),\\&sk_\mathrm{AHO}^{(d)} = (\alpha _a^{(d)}, \alpha _b^{(d)},\mu _z^{(d)},\nu _z^{(d)}, \mu ,\nu ), \end{aligned}$$

  where $d\in \{1,2,3,4\}$.

• 5. Generate a CRS for the GS NIWI proof: select $\varvec{f} = (\varvec{f}_1, \varvec{f}_2, \varvec{f}_3)$, where $\varvec{f}_1 = (f_1,1,g)$, $\varvec{f}_2 = (1,f_2,g)$, $\varvec{f}_3 = \varvec{f}_1^{\xi _1}\cdot \varvec{f}_2^{\xi _2}$ for $\xi _1,\xi _2, y_1,y_2\in _R Z_p^*$ and $f_1 = g^{y_1},f_2 = g^{y_2}$. Set $\varvec{\tilde{f}} = \varvec{f}_3 \cdot (1,1,g)$.

• 6. Define set $\varPhi = \{(g_{k,1}^{c_d},g_{k,1}^{\tilde{c}_d})|1\le k \le K, 1\le d \le D\}$, where $|\varPhi | = K\cdot D =T$. For every $(g_{k,1}^{c_d},g_{k,1}^{\tilde{c}_d})\in \varPhi$, generate the AHO signature on two messages $(g_{k,1}^{c_d},g_{k,1}^{\tilde{c}_d})$, using $sk_\mathrm{AHO}^{(1)}$. The signature is denoted as $\tilde{\sigma }_t = (\tilde{\theta }_{t1},\ldots , \tilde{\theta }_{t7})$, where $t=D\cdot (k-1) +d$.

• 7. For every $1\le \delta \le \zeta$, generate the AHO signature on message $g_n^{\delta }$, using $sk_\mathrm{AHO}^{(2)}$. The signature is denoted as $\hat{\sigma }_{\delta } = (\hat{\theta }_{\delta 1},\ldots , \hat{\theta }_{\delta 7})$.

• 8. Select $\mathcal{U,V}\in _R \mathcal{G}$ for a pubic encryption.

• 9. Select a strongly unforgeable one-time signature $\varSigma _\mathrm{OTS} =(\mathbf{Setup}_\mathrm{OTS}, \mathbf{Sign}_\mathrm{OTS}$, $\mathbf{Verify}_\mathrm{OTS})$.

• 10. Output the group public key $gpk\!=\!(K, D, p,\mathcal{G},\mathcal{T},e, g, pk_\mathrm{acc}, \{pk_\mathrm{AHO}^{(i)}\}_{i=1,2,3,4}$, $\varvec{f}, \varvec{\tilde{f}}, \{\tilde{\sigma }_t\}_{t\in \varPhi }, \{\hat{\sigma }_\delta \}_{1\le \delta \le \zeta }$, $(\mathcal{U, V}), \varSigma _\mathrm{OTS}),$ the $GM$’s secret key $gsk=(\{sk_\mathrm{AHO}^{(i)}\}_{i=1,2,3,4})$ and the opener’s secret key $osk = (y_1,y_2)$.

Join. The common inputs of $\mathsf {J}_{GM}$ and $\mathsf {J}_{\mathcal{U}_\mathsf {i}}$ are $\mathsf {l}, gpk$. The additional inputs of $\mathsf {J}_{GM}$ are $St, gsk$.

• 1. $\mathsf {J}_{\mathcal{U}_\mathsf {i}}$ selects $x\in _R \mathcal{G}$, computes $X=g^x$ and send $X$ to $\mathsf {J}_{GM}$. If $X$ is already registered in database $St_{trans}$, $\mathsf {J}_{GM}$ halts and returns $\perp$ to $\mathsf {J}_{\mathcal{U}_\mathsf {i}}$.

• 2. $\mathsf {J}_{GM}$ assigns to the user a leaf $v$ in the tree. Let $(1,x_1), \ldots , (L, x_L)$ be the path from the root to the leaf $v$. Define $U_t = \{I_t(1,x_1),\ldots , I_t(L,x_L), {\mathsf {SP}}_{k,d}\}$ for all $1\le t\le T$, where $k = \lceil t/D \rceil$ and $d= t \;\mathrm{mod}\;D$. $\mathsf {J}_{GM}$ computes $P_t = \prod _{i\in U_t}g_i$ for all $1\le t\le T$.

• 3. $\mathsf {J}_{GM}$ generates an AHO signature $\sigma _{t}= (\theta _{t,1},\ldots , \theta _{t,7})$ on $(X,P_t)$ for all $1\le t\le T$, using $sk_\mathrm{AHO}^{(3)}$.

• 4. $\mathsf {J}_{GM}$ sends $v, \{P_t\}_{1\le t\le T}$ to $\mathsf {J}_{\mathcal{U}_\mathsf {i}}$. $\mathsf {J}_{\mathcal{U}_\mathsf {i}}$ checks the correctness of $P_t$’s. If these are incorrect, $\mathsf {J}_{\mathcal{U}_\mathsf {i}}$ aborts. Otherwise, $\mathsf {J}_{\mathcal{U}_\mathsf {i}}$ sends $\mathsf {J}_{GM}$ the ordinary digital signature $sig_\mathsf {i}$ on $(X,v)$.

• 5. $\mathsf {J}_{GM}$ verifies $sig$. If it is incorrect, $\mathsf {J}_{GM}$ aborts. Otherwise, $\mathsf {J}_{GM}$ sends the AHO signature $\sigma _t$ to $\mathsf {J}_{\mathcal{U}_\mathsf {i}}$, and stores $\langle \mathsf {i}, \mathsf {transcript}_\mathsf {i} = (v,X,\{P_t, \sigma _t\}_{1\le t\le T},sig_\mathsf {i})\rangle$ in the database $St_{trans}$.

• 6. $\mathsf {J}_{\mathcal{U}_\mathsf {i}}$ outputs the membership certificate $cert_\mathsf {i} = (v,X,\{U_t, P_t, \sigma _t\}_{1\le t\le T})$ and the membership secret $sec_\mathsf {i} =x$.

Revoke. The inputs are $gpk, gsk$, the epoch $\tau$ and the revocation members $\mathcal{R}_{\tau }$.

• 1. By the subset covering of the SD scheme, find a cover of the unrevoked users, $S_1,\ldots , S_m$. Set $w = \lceil m/T \rceil$. Divide $S_1,\ldots , S_m$ into $w$ sequences:

  $$\mathcal{S}_1 = (S_1,\ldots , S_{T}), \mathcal{S}_2 = (S_{T+1},\ldots , S_{2T}),\ldots , \mathcal{S}_w = (S_{(w-1)T+1},\ldots , S_m),$$

  where $\mathcal{S}_1,\ldots , \mathcal{S}_{w-1}$ contain $T$ elements and $\mathcal{S}_w$ contains $T$ or less elements. Here, we can connect any $S_{i}$ to the corresponding sequence $\mathcal{S}_{\omega }$ by the relation $\omega = \lceil i/T \rceil$. For the sub-tree $S_i$, let $(1,s_{i,1}),\ldots , (\phi _i,s_{i,\phi _i})$ denote the path from the root to the primary root and let $(1,s_{i,1}),\ldots , (\psi _i,s_{i,\psi _i})$ denote the path to the secondary root, where $\phi _i, \psi _i \in \{1,\ldots , L\}$ and each $s_{i,j}\in \{0,1\}$.

• 2. For $\mathcal{S}_\omega$ with all $1\le \omega \le w$, do the following.

  • (a) To determine the position of $S_i$ in $\mathcal{S}_\omega$, compute $t = i \;\mathrm{mod}\;T$. Transform $t$ to the corresponding $(k,d)$ in the accumulator, by $k = \lceil t/D \rceil$ and $d= t \;\mathrm{mod}\;D$. For all $(k,d)$ correspondent $1\le t \le T$ in $\mathcal{S}_\omega$ (i.e., $(\omega -1)T+1\le i\le \omega T$), set $V_{k,d} = \{I_t(1,s_{i,1}),\ldots , I_t(\phi _i, s_{i,\phi _i})\}$ and $\tilde{V}_{k,d} = \{I_t(\phi _i+1, \overline{s_{i,\phi _i+1}}),\ldots , I_t(\psi _i, \overline{s_{i,\psi _i})}\}$, where $\overline{s_{i,\ell }}$ is the negation of $s_{i,\ell }$.

  • (b) Compute $acc_\omega = \prod _{1\le k\le K}\prod _{1\le d\le D}((\prod _{j\in V_{k,d}}g_{k,n+1-j})^{c_{d}}\cdot (\prod _{j=1}^{\zeta - |V_{k,d}|} g_{k,n+1-{\mathsf {SP}}_{k,d}})^{c_{d}}\cdot (\prod _{j\in \tilde{V}_{k,d}}g_{k,n+1-j})^{\tilde{c}_{d}}).$

• 3. For all $1\le \omega \le w$, compute the AHO signature on pair $(g^\tau , acc_\omega )$: $\varTheta _\omega = (\varTheta _{\omega ,1},\ldots , \varTheta _{\omega ,7})$, using $sk_\mathrm{AHO}^{(4)}$.

• 4. Output the revocation list: $RL_{\tau } = (\tau ,\mathcal{R}_\tau , \{S_i\}_{i=1}^m, \{acc_\omega ,\varTheta _\omega \}_{\omega =1}^w).$

Sign. The inputs are $gpk, \tau , RL_{\tau }, cert_\mathsf {i}, sec_\mathsf {i}$ and the message $M$.

• 1. Using $\mathbf{{Setup}_\mathrm{OTS}}$, generate a key pair $({\mathsf {SK}},{\mathsf {VK}})$ of the one-time signature.

• 2. Using $RL_{\tau }$, find the set $S_{\tilde{\imath }}$ including the signing user. For the subset $S_{\tilde{\imath }}$, let $(1,s_{\tilde{\imath },1}),\ldots , (\phi _{\tilde{\imath }},s_{\tilde{\imath },\phi _{\tilde{\imath }}})$ denote the path from the root to the primary root and let $(1,s_{\tilde{\imath },1}),\ldots , (\psi _{\tilde{\imath }},s_{\tilde{\imath },\psi _{\tilde{\imath }}})$ denote the path to the secondary root. Then, find $\mathcal{S}_{\tilde{\omega }}$ including $S_{\tilde{\imath }}$ by $\tilde{\omega } = \lceil \tilde{\imath }/T \rceil$. To determine the position of $S_{\tilde{\imath }}$ in $\mathcal{S}_{\tilde{\omega }}$, compute $\tilde{t} = \tilde{\imath } \;\mathrm{mod}\;T$. Furthermore, find the corresponding $(\tilde{k},\tilde{d})$ by $\tilde{k} = \lceil \tilde{t}/D \rceil$ and $\tilde{d}= \tilde{t} \;\mathrm{mod}\;D$ satisfying $\tilde{t} = D\cdot (\tilde{k}-1) +\tilde{d}-1$.

• 3. Pick up $acc_{\tilde{\omega }},\varTheta _{\tilde{\omega }} = (\varTheta _{{\tilde{\omega }},1},\ldots , \varTheta _{{\tilde{\omega }},7})$ from $RL_{\tau }$, and $U_{\tilde{t}},P_{\tilde{t}}$, $\sigma _{\tilde{t}}= (\theta _{{\tilde{t}},1},\ldots , \theta _{\tilde{t},7})$ from $cert_\mathsf {i}$. For $\tilde{t}, \tilde{k}, \tilde{d}$, pick up the AHO signature on $(J_{\tilde{t}1},J_{\tilde{t}2}) = (g_{\tilde{k},1}^{c_{\tilde{d}}},g_{\tilde{k},1}^{\tilde{c}_{\tilde{d}}})$, i.e., $\tilde{\sigma }_{\tilde{t}} = (\tilde{\theta }_{\tilde{t}1},\ldots , \tilde{\theta }_{\tilde{t}7})$ from $gpk$. In the same way to Revoke, set $V_{k,d}$ and $\tilde{V}_{k,d}$ for all $(k,d)$ in $\mathcal{S}_{\tilde{\omega }}$. Compute $\delta _{\tilde{k},\tilde{d}} = |U_{\tilde{t}}\cap \tilde{V}_{\tilde{k},\tilde{d}}|$. Pick up the AHO signature on $Q_{\delta _{\tilde{k},\tilde{d}}} = g_n^{\delta _{\tilde{k},\tilde{d}}}$, i.e., $\hat{\sigma }_{\delta _{\tilde{k},\tilde{d}}} = (\hat{\theta }_{\delta _{\tilde{k},\tilde{d}} 1},\ldots , \hat{\theta }_{\delta _{\tilde{k},\tilde{d}} 7})$ from $gpk$.

• 4. Compute the witness of $U_{\tilde{t}}\cap V_{\tilde{k},\tilde{d}} = V_{\tilde{k},\tilde{d}}$ and $U_{\tilde{t}}\cap \tilde{V}_{\tilde{k},\tilde{d}} \ne \emptyset$, as follows. ${W = \prod _{i\in U}\prod _{1\le k\le K}\prod _{1\le d \le D}((\prod _{j\in V_{k,d}}^{j\ne i}g_{k,n+1-j+i})^{c_{d}}\cdot (\prod _{j=1}^{\zeta - |V_{k,d}|,i\ne {\mathsf {SP}}_{k,d}}}$ $g_{k,n+1-{\mathsf {SP}}_{k,d}+i})^{c_{d}}\cdot (\prod _{j\in \tilde{V}_{k,d}}^{j\ne i}g_{k,n+1-j+i})^{\tilde{c}_{d}}).$

• 5. Compute GS commitments $com_{P_{\tilde{t}}}, com_{acc_{\tilde{\omega }}}, com_{W}, com_{J_{\tilde{t}1}}, com_{J_{\tilde{t}2}}, com_{Q_{\delta _{\tilde{k},\tilde{d}}}}, com_X$ to $P_{\tilde{t}}$, $acc_{\tilde{\omega }}, W$, $J_{\tilde{t}1}, J_{\tilde{t}2}$, $Q_{\delta _{\tilde{k},\tilde{d}}}, X$. Then, re-randomize the AHO signatures $\sigma _{\tilde{t}}$, $\tilde{\sigma }_{\tilde{t}}, \hat{\sigma }_{\delta _{\tilde{k},\tilde{d}}}, \varTheta _{\tilde{\omega }}$ to obtain $\sigma '_{\tilde{t}} = \{\theta '_1,\ldots , \theta '_7\}$, $\tilde{\sigma '}_{\tilde{t}}= \{\tilde{\theta '}_1,\ldots , \tilde{\theta '}_7\}, \hat{\sigma '}_{\delta _{\tilde{k},\tilde{d}}} = \{\hat{\theta '}_1,\ldots , \hat{\theta '}_7\}, \varTheta '_{\tilde{\omega }} = \{\varTheta '_1,\ldots , \varTheta '_7\}$, and compute GS commitments $\{com_{\theta '_i}\}_{i\in \{1,2,5\}}$, $\{com_{\tilde{\theta '}_i}\}_{i\in \{1,2,5\}}$, $\{com_{\hat{\theta '}_i}\}_{i\in \{1,2,5\}}$, $\{com_{\varTheta '_i}\}_{i\in \{1,2,5\}}$ to $\{\theta '_i\}_{i\in \{1,2,5\}}$, $\{\tilde{\theta '}_i\}_{i\in \{1,2,5\}}$, $\{\hat{\theta '}_i\}_{i\in \{1,2,5\}}, \{\varTheta '_i\}_{i\in \{1,2,5\}}$.

• 6. Generate $\{\pi _i\}_{i=1}^9$ s.t.

  $$\begin{aligned}&1_\mathcal{T} = e(P_{\tilde{t}},acc_{\tilde{\omega }})\cdot e(g,W)^{-1} \cdot e(J_{\tilde{t}1}, g_n^{\zeta })^{-1}\cdot e(J_{\tilde{t}2}, Q_{\delta _{\tilde{k},\tilde{d}}})^{-1}, \end{aligned}$$

  (2)
  $$\begin{aligned}&A^{(1)} \cdot e(\tilde{\theta }'_3,\tilde{\theta }'_4)^{-1} = e(G^{(1)}_z,\tilde{\theta }'_1)\cdot e(G^{(1)}_r,\tilde{\theta }'_2) \cdot e(G^{(1)}_1,J_{\tilde{t}1}) \cdot e(G^{(1)}_2,J_{\tilde{t}2}),\end{aligned}$$

  (3)
  $$\begin{aligned}&B^{(1)} \cdot e(\tilde{\theta }'_6,\tilde{\theta }'_7)^{-1} = e(H^{(1)}_z,\tilde{\theta }'_1)\cdot e(H^{(1)}_r,\tilde{\theta }'_5) \cdot e(H^{(1)}_1,J_{\tilde{t}1}) \cdot e(H^{(1)}_2,J_{\tilde{t}2}),\end{aligned}$$

  (4)
  $$\begin{aligned}&A^{(2)} \cdot e(\hat{\theta }'_3,\hat{\theta }'_4)^{-1} = e(G^{(2)}_z,\hat{\theta }'_1)\cdot e(G^{(2)}_r,\hat{\theta }'_2) \cdot e(G^{(2)}_1,Q_{\delta _{\tilde{k},\tilde{d}}}),\end{aligned}$$

  (5)
  $$\begin{aligned}&B^{(2)} \cdot e(\hat{\theta }'_6,\hat{\theta }'_7)^{-1} = e(H^{(2)}_z,\hat{\theta }'_1)\cdot e(H^{(2)}_r,\hat{\theta }'_5) \cdot e(H^{(2)}_1,Q_{\delta _{\tilde{k},\tilde{d}}}),\end{aligned}$$

  (6)
  $$\begin{aligned}&A^{(3)} \cdot e(\theta '_3,\theta '_4)^{-1} = e(G^{(3)}_z,\theta '_1)\cdot e(G^{(3)}_r,\theta '_2) \cdot e(G^{(3)}_1,X) \cdot e(G^{(3)}_2,P_{\tilde{t}}),\end{aligned}$$

  (7)
  $$\begin{aligned}&B^{(3)} \cdot e(\theta '_6,\theta '_7)^{-1} = e(H^{(3)}_z,\theta '_1)\cdot e(H^{(3)}_r,\theta '_5) \cdot e(H^{(3)}_1,X) \cdot e(H^{(3)}_2,P_{\tilde{t}}),\end{aligned}$$

  (8)
  $$\begin{aligned}&A^{(4)} \cdot e(\varTheta '_3,\varTheta '_4)^{-1} \cdot e(G^{(4)}_1,g^{\tau })^{-1} = e(G^{(4)}_z,\varTheta '_1)\cdot e(G^{(4)}_r,\varTheta '_2) \cdot e(G^{(4)}_2,acc_{\tilde{\omega }}),\end{aligned}$$

  (9)
  $$\begin{aligned}&B^{(4)} \cdot e(\varTheta '_6,\varTheta '_7)^{-1} \cdot e(H^{(4)}_1,g^{\tau })^{-1} = e(H^{(4)}_z,\varTheta '_1)\cdot e(H^{(4)}_r,\varTheta '_5) \cdot e(H^{(4)}_2,acc_{\tilde{\omega }}). \end{aligned}$$

  (10)

  In the GS proofs, the Eq. (2) shows the accumulator verification, the Eqs. (3), (4) shows the AHO signature verification on $(J_{\tilde{t}1}, J_{\tilde{t}2})$, the Eqs. (5), (6) shows the AHO signature verification on $Q_{\delta _{\tilde{k},\tilde{d}}}$, the Eqs. (7), (8) shows the AHO signature verification on $(X, P_{\tilde{t}})$, and the Eqs. (9), (10) shows the AHO signature verification on $(g^\tau , acc_{\tilde{\omega }})$.

• 7. The remaining process is as the same as in [16]. Using ${\mathsf {VK}}$ as a tag, compute a tag-based encryption [15] of $X$. Namely, select $z_1,z_2\in Z_p$, and compute

  $$ (\varGamma _1,\varGamma _2,\varGamma _3,\varGamma _4,\varGamma _5) = (f_1^{z_1},f_2^{z_2}, X\cdot g^{z_1+z_2}, (g^{{\mathsf {VK}}}\cdot \mathcal{U})^{z_1}, (g^{{\mathsf {VK}}}\cdot \mathcal{V})^{z_2}).$$

• 8. Generate NIZK proofs that $com_{X} = (1,1,X)\cdot \varvec{f}_1^{r_{X,1}}\cdot \varvec{f}_2^{r_{X,2}}\cdot \varvec{f}_3^{r_{X,3}}$ and $(\varGamma _1,\varGamma _2,\varGamma _3)$ is a BBS ciphertext of $X$, as in [16]. For $\varvec{f}_3 = (f_{3,1}, f_{3,2}, f_{3,3})$, we can write $com_{X} = (f_1^{r_{X,1}}\cdot f_{3,1}^{r_{X,3}}, f_2^{r_{X,2}}\cdot f_{3,2}^{r_{X,3}}, X\cdot g^{r_{X,1}+r_{X,2}}\cdot f_{3,3}^{r_{X,3}})$. Thus, we have

  $$\begin{aligned} com_{X}\cdot (\varGamma _1,\varGamma _2,\varGamma _3)^{-1}&= (f_1^{\chi _1}\cdot f_{3,1}^{\chi _3},\ f_2^{\chi _2}\cdot f_{3,2}^{\chi _3},\ g^{\chi _1+\chi _2}\cdot f_{3,3}^{\chi _3}), \end{aligned}$$

  (11)

  where $\chi _1 = r_{X,1} -z_1, \chi _2 = r_{X,2} -z_2, \chi _3 = r_{X,3}$. Compute GS commitments $com_{\chi _i}$ to the exponent $\chi _i$ for $i=1,2,3$ using $\varvec{\tilde{f}}$, and generate the NIZK proofs $\pi _{10}, \pi _{11}, \pi _{12}$ satisfying the three linear relations (11).

• 9. Compute a weakly secure BB signature $\sigma _{{\mathsf {VK}}} = g^{1/(x+{\mathsf {VK}})}$ on ${\mathsf {VK}}$ and the commitment $com_{\sigma _{\mathsf {VK}}}$ to $\sigma _{\mathsf {VK}}$. Next, generate the NIZK proof $\pi _{13}$ satisfying $e(\sigma _{\mathsf {VK}}, X\cdot g^{\mathsf {VK}}) = e(g,g)$.

• 10. Compute a one-time signature

  $$\begin{aligned} \sigma _\mathrm{OTS} = \mathbf{Sign}_\mathrm{OTS}({\mathsf {SK}}, (M,RL_{\tau }, \{\varGamma _i\}_{i=1}^{5}, \{\theta '_i, \tilde{\theta '}_i, \hat{\theta '}_i, \varTheta '_i\}_{i=3,4,6,7},\mathbf {com}, \varvec{\Pi })), \end{aligned}$$

  where $\mathbf {com} = (com_{P_{\tilde{t}}}, com_{acc_{\tilde{\omega }}}, com_{W}, com_{J_{\tilde{t}1}}, com_{J_{\tilde{t}2}}, com_{Q_{\delta _{\tilde{k},\tilde{d}}}}, com_X$, $\{com_{\chi _i}\}_{i=1}^3$, $\{com_{\theta '_i}\}_{i\in \{1,2,5\}}, \{com_{\tilde{\theta '}_i}\}_{i\in \{1,2,5\}}, \{com_{\hat{\theta '}_i}\}_{i\in \{1,2,5\}}, \{com_{\varTheta '_i}\}_{i\in \{1,2,5\}}, com_{\sigma _{\mathsf {VK}}})$, $\varvec{\Pi } = \{\pi _{i}\}_{i=1}^{13}$. Output the signature $\sigma = ({\mathsf {VK}}, \{\varGamma _i\}_{i=1}^{5}, \{\theta '_i, \tilde{\theta '}_i, \hat{\theta '}_i, \varTheta '_i\}_{i=3,4,6,7}$, $\mathbf {com}, \varvec{\Pi }, \sigma _\mathrm{OTS})$.

Verify. The input are $gpk, \tau , RL_{\tau }, \sigma , M$. If

$$\mathbf{Verify}_\mathrm{OTS}({\mathsf {VK}}, (M,RL_{\tau }, \{\varGamma _i\}_{i=1}^{5}, \{\theta '_i, \tilde{\theta '}_i, \hat{\theta '}_i, \varTheta '_i\}_{i=3,4,6,7},\mathbf {com}, \varvec{\Pi }))=0$$

or $\{\varGamma _i\}_{i=1}^{5}$ is not a valid tag-based encryption, output 0. Then, output 1 if all proofs are accepted. Otherwise, output 0.

Open. The inputs are $gpk, \tau , RL_{\tau },\sigma , M, St, osk$. If Verify on $\sigma$ and $M$ outputs 0, output $\perp$. Otherwise, using $osk = (y_1,y_2)$, decrypt $\tilde{X} = \varGamma _3 \cdot \varGamma _1^{-1/y_1}\cdot \varGamma _2^{-1/y_2}$. Search the database $St_{trans}$ to find a record $\langle \mathsf {i}, ({\mathsf {transcript}}_\mathsf {i}, v,X,\{P_t, \sigma _t\}_{1\le t\le T},sig_\mathsf {i})\rangle$ with $X = \tilde{X}$. If the search fails, output $\perp$. Otherwise, output $\mathsf {i}$.

4.3 Security

The proofs of the security are in the full paper.

5 Efficiency

We compare the efficiency of our scheme to the previous scheme [16]. In addition to parameters $N, R$, the efficiency of our system depends on $n, T, K, D$, where $T=K\cdot D$, and $n \approx T\log N$. Here, as in [16], we consider the 128-bit security level, and we assume that the element in $\mathcal{G}$ can be represented by 512 bits.

We compare the constant signature size. The signature in the previous scheme needs 144 $\mathcal{G}$-elements and the size is 9 KB. In our scheme, the signature needs 143 $\mathcal{G}$-elements, whose size is also 9 KB.

In the proposed scheme, we have the trade-off: Decreasing the revocation list size leads to increasing the sizes of public key and membership certificate. Consider the revocation list size. The revocation list consists of a non-cryptographic part related to IDs of revoked members (i.e., $\mathcal{R}_\tau , \{S_i\}_{i=1}^m$) and a cryptographic part of accumulators and the signatures (i.e., $\{acc_\omega ,\varTheta _\omega \}_{\omega =1}^w$). The non-cryptographic part is bounded by $5 \cdot \log N \cdot R$ bits. The cryptographic part in our scheme is bounded by $512\cdot 8 \lceil (2R-1)/T \rceil$ bits, while the part needs at most $512\cdot 7 \lceil (2R-1) \rceil$ bits in [16]. Thus, by increasing $T$, this part is greatly reduced. However, the other efficiency becomes worse as follows. The public key size of our scheme is approximately $2K \cdot T\cdot \log N \cdot 512$ bits. The membership certificate size is approximately $8\cdot 512\cdot T$ bits.

Next, we compare the signing costs. The computational cost of signing is comparable except for the computation of $W$. As discussed in Appendix B, $T$ exponentiations (and $2D$ exponentiations) are the extra cost compared to [16]. However, note that the computation of $W$ is required once every revocation epoch in practice. Namely, after $W$ is computed in an epoch, the following signing does not need the extra cost during the same epoch. Furthermore, we can reduce the computation of $W$ by using $W$ in the previous epoch. Thus, we consider that the extra costs are not a serious issue.

Now we consider concrete examples. We assume $N/R =10$. To balance $K$ and $D$, we set $K=D\approx \sqrt{T}$. Table 1 shows the comparisons of the revocation list size between the previous scheme [16] and the proposed scheme using $T=49, T=100$, in cases of $N=10{,}000, N= 100{,}000, N= 1{,}000{,}000$. As for the cryptographic part ($\{acc_\omega ,\varTheta _\omega \}_{\omega =1}^w$), the size is greatly reduced, as $T$ is increased. Since the non-cryptographic part cannot be reduced, we ignore cases of $T>100$. Similarly, for $N\gg 1{,}000{,}000$, due to the huge data of the non-cryptographic part, any revocable group signatures are essentially impractical.

Table 1. Comparisons of the revocation list size.

Table 2 shows the comparisons of the public key size and the membership certificate size, where $N=1{,}000{,}000$ and $R=100{,}000$. Since the public key size depends on only $\log N$, the size in cases of the other $N,R$ is similar to this table. The membership certificate size is the same when $N,R$ are changed. Compared to [16], the extra sizes in public key and membership certificate are needed, and are increased when $T$ is increased. In real applications, the public key and the certificate are not often distributed. On the other hand, the revocation list has to be distributed every revocation epoch. Thus, we consider that it is sufficiently practical to decrease the revocation list size while increasing the public key and the membership certificate sizes.

As for the signing cost, in our scheme, the extra cost of about 120 exponentiations is required in case of $T=100$. The extra cost is comparable to the computations of commitments $\mathbf {com}$ with about 140 exponentiations. As shown above, the cost can be reduced in the implementation.

Table 2. Public key size and membership certificate size for $T$ ($N=1{,}000{,}000, R=100{,}000$).

Appendices

A Preliminaries

1.1 A.1 Bilinear Groups

Our scheme utilizes the following bilinear groups:

• 1. $\mathcal{G}$ and $\mathcal{T}$ are multiplicative cyclic groups of prime order $p$,

• 2. $g$ is a randomly chosen generator of $\mathcal{G}$,

• 3. $e$ is an efficiently computable bilinear map: $\mathcal{G}\times \mathcal{G}\rightarrow \mathcal{T}$, i.e., (1) for all $u,v\in \mathcal{G}$ and $a,b\in Z$, $e(u^a,v^b)=e(u,v)^{ab}$, and (2) $e(g,g)\ne 1_\mathcal{T}$.

1.2 A.2 Assumptions

As in the underlying scheme [16], the security of our system is based on the DLIN (Decision LINear) assumption [6], the SDH (Strong DH) assumption [5], and the $q$-SFP (Simultaneous Flexible Pairing) assumption [2]. We also adopt $n$-DHE (DH Exponent) assumption [11] for the accumulator.

Definition 1

(DLIN assumption). For all PPT algorithm $\mathcal {A}$, the probability

$$\begin{aligned}&|\mathrm{Pr}[\mathcal {A}(g, g^a, g^b, g^{ac}, g^{bd}, g^{c+d}) = 1] -\mathrm{Pr}[\mathcal {A}(g, g^a, g^b, g^{ac}, g^{bd}, g^{z}) = 1]| \end{aligned}$$

is negligible, where $g \in _R \mathcal{G}$ and $a,b,c,d,z \in _R Z_p$.

Definition 2

( $q$ -SDH assumption). For all PPT algorithm $\mathcal {A}$ , the probability

$$\begin{aligned} \mathrm{Pr}[\mathcal {A}(g,g^{a},\ldots , g^{a^q}) = (b,g^{1/(a+b)})\wedge b \in Z_p] \end{aligned}$$

is negligible, where $g\in _R \mathcal{G}$ and $a \in _R Z_p$.

Definition 3

( $q$ -SFP assumption). For all PPT algorithm $\mathcal {A}$ , the probability

is negligible, where $(g_z, h_z, g_r, h_r, a, \tilde{a}, b, \tilde{b})\in \mathcal{G}^8$ and all tuples $\{(z_j, r_j, s_j, t_j, u_j$, $v_j, w_j)\}_{j=1}^q)$ satisfy the above relations.

Definition 4

( $n$ -DHE assumption). For all PPT algorithm $\mathcal {A}$ , the probability

$$\begin{aligned} \mathrm{Pr}[\mathcal {A}(g,g^{a},\ldots , g^{a^n}, g^{a^{n+2}},\ldots , g^{a^{2n}}) = g^{a^{n+1}}] \end{aligned}$$

is negligible, where $g\in _R \mathcal{G}$ and $a \in _R Z_p$.

1.3 A.3 Structure-Preserving Signatures (AHO Signatures)

We utilize the structure-preserving signatures, since the knowledge of the signature can be proved by Groth-Sahai proofs. As in [16], we adopt the AHO signature scheme in [1, 2]. Using the AHO scheme, we can sign multiple group elements to obtain a constant-size signature.

• AHOKeyGen: Select bilinear groups $\mathcal{G, T}$ with a prime order $p$ and a bilinear map $e$. Select $g,G_r,H_r \in _R \mathcal{G}$, and $\mu _z,\nu _z,\mu ,\nu ,\alpha _a,\alpha _b\in _R Z_p$. Compute $G_z= G_r^{\mu _z}, H_z = H_r^{\nu _z}, G = G_r^{\mu }, H = H_r^{\nu }$, $A = e(G_r,g^{\alpha _a}), B=e(H_r,g^{\alpha _b})$. Output the public key as $pk = (\mathcal{G, T}, p, e, g$, $G_r, H_r, G_z, H_z, G, H, A, B)$, and the secret key as $sk = (\alpha _a, \alpha _b, \mu _z,\nu _z,\mu ,\nu )$.

• AHOSign: Given message $M$ together with $sk$, choose $\beta ,\epsilon , \eta ,\iota ,\kappa \in _R Z_p$, and compute $\theta _1 = g^{\beta }$, and $\theta _2 = g^{\epsilon -\mu _z\beta }M^{-\mu },\quad \theta _3 = G_r^{\eta }, \quad \theta _4 = g^{(\alpha _a-\epsilon )/\eta }, \theta _5 = g^{\iota -\nu _z\beta }M^{-\nu },\quad \theta _6 = H_r^{\kappa }, \quad \theta _7 = g^{(\alpha _b-\iota )/\kappa }$. Output the signature $\sigma = (\theta _1,\ldots , \theta _7)$.

• AHOVerify: Given the message $M$ and the signature $\sigma = (\theta _1,\ldots , \theta _7)$, accept these if

  $A = e(G_z,\theta _1)\cdot e(G_r,\theta _2) \cdot e(\theta _3,\theta _4)\cdot e(G,M)$, $B = e(H_z,\theta _1)\cdot e(H_r,\theta _5) \cdot e(\theta _6,\theta _7) \cdot e(H,M)$.

This signature is existentially unforgeable against chosen-message attacks under the $q$-SFP assumption [2]. Using the re-randomization algorithm in [2], this signature can be publicly randomized to obtain another signature $(\theta '_1,\ldots , \theta '_7)$ on the same message. As a result, in the following Groth-Sahai proof, $(\theta '_i)_{i=3,4,6,7}$ can be safely revealed, while $(\theta '_i)_{i=1,2,5}$ have to be committed.

1.4 A.4 Groth-Sahai (GS) Proofs

To prove the secrets in relations of the bilinear maps, we utilize Groth-Sahai (GS) proofs [14]. As in [16], we adopt the instantiation based on DLIN assumption. For the bilinear groups, the proof system needs a common reference string $(\varvec{f}_1, \varvec{f}_2, \varvec{f}_3) \in \mathcal{G}^3$ for $\varvec{f}_1= (f_1,1,g), \varvec{f}_2 = (1,f_2,g)$ for some $f_1,f_2\in \mathcal{G}$. The commitment to an element $X$ is computed as $\varvec{C} = (1,1,X)\cdot \varvec{f}_1^r\cdot \varvec{f}_2^s \cdot \varvec{f}_3^t$ for $r,s,t\in _R Z_p^*$. In case of the CRS setting for perfectly sound proofs, $\varvec{f}_3 = \varvec{f}_1^{\xi _1}\cdot \varvec{f}_2^{\xi _2}$ for $\xi _1,\xi _2\in _R Z_p^*$. Then, the commitment $\varvec{C} = (f_1^{r+\xi _1t}, f_2^{s+\xi _2t}, Xg^{r+s+t(\xi _1+\xi _2)})$ is the linear encryption in [6]. On the other hand, in the setting of the witness indistinguishability, $\varvec{f}_1, \varvec{f}_2,\varvec{f}_3$ are linearly independent, and thus $\varvec{C}$ is perfectly hiding. The DLIN assumption implies the indistinguishability of the CRS.

The commitment to an exponent $x\in Z_p$ is computed as $\varvec{C} = \varvec{\tilde{f}}^x\cdot \varvec{f}_1^r\cdot \varvec{f}_2^s$ for $r,s\in _R Z_p^*$, for a CRS $\varvec{\tilde{f}}, \varvec{f}_1,\varvec{f}_2$. In the setting of perfectly sound proofs, $\varvec{\tilde{f}}, \varvec{f}_1,\varvec{f}_2$ are linearly independent (As in [16], for example, we can set $\varvec{\tilde{f}} = \varvec{f}_3\cdot (1,1,g)$ with $\varvec{f}_3 = \varvec{f}_1^{\xi _1}\cdot \varvec{f}_2^{\xi _2}$). In the WI setting, $\varvec{\tilde{f}}=\varvec{f}_1^{\xi _1}\cdot \varvec{f}_2^{\xi _2}$ provides a perfectly hiding commitment.

To prove that the committed variables satisfy the pairing relations, the prover prepares the commitments, and replaces the variables in the pairing relations by the commitments. An NIWI (non-interactive witness indistinguishable) proof allows us to prove the set of pairing product equations:

$$\begin{aligned} \prod _{i=1}^n e(A_i, X_i)\cdot \prod _{i=1}^n\prod _{j=1}^n e(X_i, X_j)^{a_{ij}} =t, \end{aligned}$$

for variables $X_1,\ldots , X_n\in \mathcal{G}$ and constants $A_1,\ldots , A_n\in \mathcal{G}, a_{ij}\in Z_p, t\in \mathcal{T}$. NIWI proofs also exist for multi-exponentiation equations:

$$\begin{aligned} \prod _{i=1}^m A_i^{y_i}\cdot \prod _{j=1}^n X_j^{b_j}\cdot \prod _{i=1}^m \prod _{j=1}^n X_j^{y_i\gamma _{ij}} =T, \end{aligned}$$

for variables $X_1,\ldots , X_n\in \mathcal{G}$, $y_1,\ldots , y_m\in Z_p$ and constants $T, A_1,\ldots , A_m\in \mathcal{G}$, $b_1,\ldots , b_n, \gamma _{ij}\in Z_p$. For the multi-exponentiation equations, we can obtain the NIZK (non-interactive zero-knowledge) proofs with no additional cost.

1.5 A.5 Subset Cover Framework for Broadcast Encryption

As in [16], we adopt the subset cover framework for broadcast encryption in [21]. In this framework, a binary tree is used, where each leaf is assigned to each receiver (its secret key). Namely, for $N = 2^{L}$ receivers, the height of the tree is $L$. Let $\mathcal{N}$ be the universe of users and $\mathcal{R}\subset \mathcal{N}$ be the set of revoked receivers. In this framework, the set of non-revoked users is partitioned into $m$ disjoint subsets $S_1,\ldots , S_m$ such that $\mathcal{N}{\setminus } \mathcal{R} = S_1\cup \cdots \cup S_m$.

In the framework, there are mainly the complete subtree (CS) method and the subset difference (SD) method. In the revocable group signature scheme of [16], the SD method is adapted to achieve $O(|\mathcal{R}|)$ revocation list. In this method, the disjoint set $S_i$ is determined by two nodes in the tree, primary node ${v}_{i,\phi _i}$ and secondary node ${v}_{i,\psi _i}$ that is a descendant node of ${v}_{i,\phi _i}$, and $S_i$ consists of the leaves of the subtree rooted by $v_{i,\phi _i}$ that are not in the subtree rooted by $v_{i,\psi _i}$. The number of subsets is bounded by $m=2\cdot |\mathcal{R}|-1$, as proved in [21].

B Evaluation of Witness Computation

In Sect. 5, the efficiency of our scheme is compared to the underlying scheme [16]. Here, we show the detailed efficiency discussion of the witness computation. The computation of $W$ can be replaced:

Then, the number of exponentiations by $c_d,\tilde{c}_d$ is $2D$. The number of multiplications is $T\cdot \log ^2 N$. As discussed in [16], $\log ^2 N$ multiplications is bounded by the cost of a single exponentiation. This is why $T$ exponentiations (and $2D$ exponentiations) are the extra cost compared to [16].

As mentioned in Sect. 5, the witness computation can be reduced by using $W$ in the previous epoch. In the case that the modification to the revocation list does not influence $\mathcal{S}_{\tilde{\omega }}$ including $S_{\tilde{\imath }}$ (i.e., revocations happens in the other covers), the signer does not need to compute $W$. In the other cases, we can also reduce the cost: For only modified covers $S_i$ correspondent $(k,d)$, divide $W$ by the old terms for $(k,d)$ and multiply it by the new terms. Thus, we consider that the extra costs are not a serious issue.