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.

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.