# Anr-Hiding Revocable Group Signature Scheme: Group Signatures with the Property of Hiding the Number of Revoked Users

Authors: Keita Emura; Atsuko Miyaji; Kazumasa Omote
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

If there are many displaced workers in a company, then a person who goes for job hunting might not select this company. That is, the number of members who quit is quite negative information. Similarly, in revocable group signature schemes, if one knows (or guesses) the number of revoked users (sayr), then one may guess the reason behind such circumstances, and it may lead to harmful rumors. However, no previous revocation procedure can achieve hiding r. In this paper, we propose the first revocable group signature scheme, where r is kept hidden, which we call r-hiding revocable group signature. To handle this property, we newly define the security notion called anonymity with respect to the revocation which guarantees the unlinkability of revoked users.


---

## Body

## 1. Introduction

Imagine that there are many users who have stopped using a service. If this fact is published, then how would the newcomers feel about this? One may guess the reason behind such circumstances and may judge that those users did not find the service attractive or the service fee is expensive. The same thing may occur in other cases; for example, if there are many displaced workers in a company, then a person who goes for job hunting might not select this company. For example, the person might imagine there are many problematic employees in this company or might imagine the labor environment may not be good. That is, the number of members who quit is quite negative information.Group Signature. Many cryptographic attempts for the revocation of rights of users have been considered so far. In this paper, we mainly focus on group signature. The concept of group signature was investigated by Chaum and van Heyst [1]. A typical usage of group signature is described as follows. The group manager (GM) issues a membership certificate to a signer. A signer makes a group signature by using their own membership certificate and sends it (with a signed message) to a verifier. The verifier anonymously verifies whether a signer is a member of a group or not. That is, the verifier checks the possession of a membership certificate without revealing themself. In order to handle some special cases (e.g., an anonymous signer behaves maliciously), GM can identify the actual signer through the open procedure. Since verifiers do not have to identify individual signers, group signature is a useful and powerful tool for protecting signers’ privacy.As additional functionality of group signature, anonymity revocation has been introduced [2–11], where no revoked users can make a valid group signature or revoked users can be publicly detected even if they try to make a group signature. (Since a long RSA modulus might lead to certain inefficiency aspects (e.g., long signatures, heavy complexity costs, and so on), we exclude RSA-based revocable group signatures (e.g., [12, 13]) in this paper.) However, the number of revoked users (say r) is revealed in all previous revocable group signature schemes. As mentioned previously, the number of revoked users r is quite negative information. Next, we introduce applications of revocable group signature for outsourcing businesses [14] and biometric authentication [15] as concrete examples, where revealing r may lead to harmful rumors.Concrete Example
1 (identity management). In this application, presented in [14], there are four entities: a user, outsourcee, opening manager (OM), and revocation manager (RM). Let outsourcee be in charge of providing the service to legitimate users. When a user requests the service, the user makes a group signature and sends it to outsourcee. Due to anonymity of the underlying group signature scheme, outsourcee does not have to identify individual users (protect users’ privacy). One important thing is that outsourcee does not have to manage a list of identities of users. That is, the risk of leaking user information (i.e., the user list) can be minimized, and this is the merit of using group signature in identity management. After a certain interval, for charging a service fee, OM detects a user by using the opening procedure of group signature. If a user does not pay a fee (or when a user wants to leave the service), then OM announces the identity of this user to RM, and RM revokes this user from the system. In this system, if r is revealed, then one may think that there might be many dropout users who have stopped using the service; that is, this service may not be interesting, or he/she have not paid the service fee; namely, the service fee may be expensive and so on. That is, “revealing r” may lead to harmful rumors.Concrete Example
2 (biometric authentication). In this application presented in [15], there are four entities: a human user, a sensor client, a card issuer, and a service provider. A human user authenticates himself/herself to the service provider by using his/her biometric data preserved on a plastic card. A card issuer (with a group master secret key) issues a card to a human user which contains a signing key and his/her biometric data. Moreover, the card issuer can revoke users if malicious behavior occurs or a user loses his/her card. A sensor client extracts human user’s biometric trait (e.g., iris is used in [15]) and communicates with the service provider, so that the user will be authenticated by the service provider. The service provider verifies a group signature and provides a service (e.g., open a door) if the signature is valid. Due to anonymity, the service provider does not identify who the user is; even sensitive biometric information is treated. In this system, if someone knows r in this application, they may think that there might be many malicious behaviors, or there might be many lost cards; that is, good management may deteriorate, and so on. That is, “revealing r” may lead to harmful rumors.Our Target. So, our main target is to propose a revocable group signature scheme with the property of hiding the number of revoked users r, which we call r-hiding revocable group signature. Then, we need to investigate the methodology for achieving the following.(1)
The size of any value does not depend onr.
(2)
The costs of any algorithm do not depend onr, except the revocation algorithm executed by GM.
(3)
Revoked users are unlinkable. In particular, if revoked users are linkable, then anyone can guess (i.e., not exactly obtain) r by linking and counting revoked users. Although we assume that an adversary can obtain the polynomial (of the security parameter) number of group signatures, this assumption is not unreasonable (actually, the adversary can be allowed to access the signing oracle in polynomial times). In addition, r is also a polynomial-size value. That is, this guessing attack works given that revoked users are linkable.However, no previous revocable signature scheme satisfying all requirements above has been proposed. For example, in revocable group signatures [2, 4, 11] (which are based on updating the group public values, e.g., using accumulators), either the size of public value or the costs of updating membership certificate depend on r. Nakanishi et al. [6] proposed a novel technique of group signature, where no costs of theGSign algorithm (or theVerify algorithm also) depend on r. However, their methodology requires that r signatures are published to make a group signature, and therefore r is revealed. Recently, Libert-Peters-Yung proposed two scalable group signature schemes [7, 8] by applying the Naor-Naor-Lotspeich (NNL) broadcast encryption framework [16]. However, at least one cost depends on r (e.g., O
(
r
)-size revocation list is required for signing in [7, 8] (of subset difference variant) and O
(
r
log
⁡
(
N
/
r
)
)-size revocation list is required for signing in [8] (of complete subtree variant) and N (the number of users) are publicly available). Therefore, r is revealed. In [3, 5, 10, 17, 18] (which are verifier-local revocation (VLR) type group signature schemes), revoked users are linkable. In this case, anyone can guess r by executing the verification procedure. For the sake of clarity, we introduce the Nakanishi-Funabiki methodology [10] as follows: let RL
=
{
h
x
1
,
h
x
2
,
…
,
h
x
r
} be the revocation list, where x
i is the secret value of revoked user U
i. Note that, by adding dummy values, we can easily expand the size of revocation list |
RL
|. So, we can assume that r is not revealed from the size of RL, but r is revealed (or rather, guessed) as follows. Each group signature σ (made by U
j) contains f
x
j
+
β and h
β for some random β and some group elements f and h. If U
j has been revoked, then there exists h
x
i such that e
(
f
x
j
+
β
,
h
)
=
e
(
h
x
i
h
β
,
f
) holds. By counting such i, one can easily guess r even if RL is expanded by dummy values. Since each value in RL is linked to a user (i.e., h
x
i is linked to U
i), even if values in RL are randomized (e.g., (
h
x
i
)
r
i for some random r
i), this connection between a user and a value in RL is still effective. So, one can easily guess r even if RL is randomized.From the above considerations, no previous revocation procedure can be applied for hidingr. One solution has been proposed in [19], where only the designated verifier can verify the signature. By preventing the verification of signature from the third party, r is not revealed from the viewpoint of the third party. However, this scheme (called anonymous designated verifier signature) is not publicly verifiable and is not group signature any longer. Next, as another methodology, we may consider multigroup signatures [20, 21] with two groups (valid user group and revoked user group). However, this attempt does not work, since each user is given his/her membership certificate (corresponding to the group he/she belongs to) in the initial setup phase, and the revocation procedure is executed after the setup phase.Our Contribution. In this paper, we propose the first r-hiding revocable group signature scheme in the random oracle model by applying attribute-based group signature (ABGS) [22–25]. By considering two attributes: (
1
) valid group user and (
2
) the user’s identity, we can realize the property of hiding r. To handle this property, we newly define the security notion called anonymity with respect to the revocation. As the main difference among our anonymity definition and previous ones, to guarantee the unlinkability of revoked users, A can issue the revocation queries against the challenge users. Our scheme is secure under the computational Diffie-Hellman (CDH) assumption, the decision Diffie-Hellman (DDH) assumption over a bilinear group (i.e., the external Diffie-Hellman (XDH) assumption), the decision linear (DLIN) assumption, the hidden strong Diffie-Hellman (HSDH) assumption, and the q-strong Diffie-Hellman (SDH) assumption, in the random oracle model. We apply the Boldyreva multisignature scheme [26] to revoke each user.Related Work. There were several security definitions of group signatures until the Bellare-Micciancio-Warinschi work [27], which we call the BMW model. They showed that full-anonymity and full-traceability are enough to capture all security requirements that appeared before their work. Bellare et al. [28] extended the BMW model, which we call the BSZ model, to handle the dynamic group setting, where a user can join the system even after the system setup phase. Later, Sakai et al. [29] further extended the BSZ model for preventing signature hijacking. Independently, Kiayias and Yung also give a formal definition with dynamic join [30, 31], and Libert et al. [7, 8] extended to the KY model for revocable group signature.Efficient group signature schemes in the random oracle model have been proposed in [2, 4, 32] and in the standard model [5, 33, 34]. Technically, (honest verifier) zero knowledge proofs of knowledge and the Fiat-Shamir heuristic [35] are mainly applied for constructing group signatures in the random oracle model, and Groth-Sahai proofs [36] and structure-preserving signatures [37] are mainly applied for constructing group signatures in the standard model. Though the above schemes are constructed over bilinear groups, lattice-based group signature schemes also have been proposed [38–40]. Usually, encryption schemes are applied for implementing the open algorithm; however, encryption-free group signatures schemes have been proposed in [41, 42].As group signatures with an additional functionality, a new open functionality, which we call message-dependent opening, has been proposed in [43–45], where a signed message-dependent token is generated by an authority called admitter and an opener who has the opening key can open the group signatures using the corresponding token. Forward secure group signature schemes have been proposed [46–49], where users can update their secret signing key periodically, and group signatures made by the secret keys of previous periods remain secure even if a secret key is exposed. Revocable group signature schemes with backward unlinkability have been proposed [5, 9, 10, 18], where even after a user is revoked, group signatures made by this user before the revocation remain anonymous. Identity-based analogue of group signature also has been proposed in [50, 51].As feasibility results, a group signature secure in the BMW model implies CCA-secure public key encryption (PKE) [52, 53], and a group signature secure in the Sakai et al. model implies PKENO [54], where PKENO stands for public key encryption with noninteractive opening [55]. Moreover, a group signature with message-dependent opening implies identity-based encryption [44].


## 2. Preliminaries

In this section, we give definitions of bilinear groups and complexity assumptions and introduce cryptographic tools which are applied in our construction. Let PPT mean probabilistic polynomial time, andx
←
$
X means that an element x is chosen at uniform random from a set X.


### 2.1. Bilinear Groups and Complexity Assumptions

Definition 1 (bilinear groups).
LetG
1, G
2, and G
T be cyclic groups with prime order p, and G
1
=
〈
g
〉 and G
2
=
〈
h
〉. Let e
:
G
1
×
G
2
→
G
T be an (efficient computable) bilinear map with the following properties: (
1
) bilinearity: for all (
g
,
g
′
)
∈
G
1
2 and (
h
,
h
′
)
∈
G
2
2, e
(
g
g
′
,
h
)
=
e
(
g
,
h
)
e
(
g
′
,
h
) and e
(
g
,
h
h
′
)
=
e
(
g
,
h
)
e
(
g
,
h
′
) hold, and (
2
) nondegeneracy: e
(
g
,
h
)
≠
1
T, where 1
T is the unit element over G
T.Definition 2 (the computational Diffie-Hellman (CDH) assumption).
We say that the CDH assumption holds if, for all PPT adversaryA, Pr
[
A
(
g
1
,
g
1
a
,
g
1
b
)
=
g
1
a
b
] is negligible, where g
1
←
$
G
1 and (
a
,
b
)
←
$
Z
p
2.Definition 3 (the decision Diffie-Hellman (DDH) assumption).
We say that the DDH assumption holds if, for all PPT adversaryA, |
Pr
[
A
(
g
1
,
g
1
′
,
g
1
x
,
g
1
′
x
)
=
0
]
-
Pr
[
A
(
g
1
,
g
1
′
,
g
1
x
,
g
1
′
r
)
=
0
]
| is negligible, where (
g
1
,
g
1
′
)
←
$
G
1
2 and (
x
,
r
)
←
$
Z
p
2 with x
≠
r.Definition 4 (the decision linear (DLIN) assumption [2]).
We say that the DLIN assumption holds if, for all PPT adversaryA, |
Pr
[
A
(
u
,
v
,
h
,
u
a
,
v
b
,
h
a
+
b
)
=
0
]
-
Pr
[
A
(
u
,
v
,
h
,
u
a
,
v
b
,
η
)
=
0
]
| is negligible, where (
u
,
v
,
h
,
η
)
←
$
G
2
4 and (
a
,
b
)
←
$
Z
p
2.Definition 5 (the hidden strong Diffie-Hellman (HSDH) assumption [34]).
We say thatl-HSDH assumption holds if, for all PPT adversary A, Pr
[
A
(
g
1
,
h
,
h
ω
,
(
g
1
1
/
(
ω
+
c
i
)
,
h
x
i
)
i
=
1
,
…
,
l
)
=
(
g
1
1
/
(
ω
+
x
)
,
h
x
)
∧
∀
x
i
≠
x
] is  negligible, where (
g
1
,
h
)
←
$
G
1
×
G
2, (
ω
,
x
1
,
…
,
x
l
)
←
$
Z
p
l
+
1 and x
∈
Z
p.Definition 6 (the strong Diffie-Hellman (SDH) assumption [56]).
We say thatq-SDH assumption holds if, for all PPT adversary A, Pr
[
A
(
g
1
,
h
,
h
ω
,
h
ω
2
,
…
,
h
ω
q
)
=
(
g
1
1
/
(
ω
+
x
)
,
x
)
] is negligible, where (
g
1
,
h
)
←
$
G
1
×
G
2,  ω
←
$
∈
Z
p, and x
∈
Z
p.Definition 7 (the external Diffie-Hellman (XDH) assumption [4]).
Let(
G
1
,
G
2
,
G
T
) be a bilinear group. We say that the XDH assumption holds if for all PPT adversary A, the DDH assumption over G
1 holds.


### 2.2.  Other Cryptographic Tools

In this section, we introduce cryptographic tools applied for our construction.BBS+ Signature [2, 6, 32, 57]. Let L be the number of signed messages and let (
G
1
,
G
2
,
G
T
) be a bilinear group. Select g
,
g
1
,
…
,
g
L
←
$
G
1, h
←
$
G
2, and ω
←
Z
p, and compute Ω
=
g
ω. The signing key is ω and the verification key is (
p
,
G
1
,
G
2
,
G
T
,
e
,
g
,
g
1
,
…
,
g
L
+
1
,
h
,
Ω
). For a set of signed messages (
m
1
,
…
,
m
L
)
∈
Z
p
L, choose r
,
y
←
$
Z
p, and compute A
=
(
g
1
m
1
⋯
g
L
m
L
g
L
+
1
r
g
)
1
/
(
ω
+
y
). For a signature (
A
,
r
,
y
), the verification algorithm output 1 if e
(
A
,
Ω
h
y
)
=
e
(
g
1
m
1
⋯
g
L
m
L
g
L
+
1
r
,
h
) holds. The BBS+ signature scheme satisfies existential unforgeability against chosen message attack (EUF-CMA) under the q-SDH assumption. (First an adversary A is given vk from the challenger C. Then A sends messages to C and obtains the corresponding signatures. Finally, A outputs a message/signature pair (
M
*
,
σ
*
). We say that A wins if (
M
*
,
σ
*
) is valid and A has not sent M
* as a signing query. The EUF-CMA security guarantees that the probability Pr
[
A
wins
] is negligible.)Linear Encryption [2]. A public key is pk
=
(
u
,
v
,
h
)
∈
G
2 such that u
X
1
=
v
X
2
=
h for X
1
,
X
2
∈
Z
p. The corresponding secret key is (
X
1
,
X
2
). For a plaintext M
∈
G
2, choose δ
1
,
δ
2
←
$
Z
p and compute a ciphertext C
=
(
F
1
,
F
2
,
F
3
), where F
1
=
M
·
h
δ
1
,
δ
2, F
2
=
u
δ
1, and F
3
=
v
δ
2. C can be decrypted as M
=
F
1
/
F
2
X
1
F
3
X
2. The linear encryption is IND-CPA secure under the DLIN assumption. (First an adversary A is given pkfrom the challenger C. Then A sends the challenge message (
M
0
*
,
M
1
*
) to C, and C chooses μ
←
$
{
0,1
} and computes the challenge ciphertext C
* which is a ciphertext of M
μ
*. A is given C
* and outputs a bit μ
′. The IND-CPA security guarantees that |
Pr
[
μ
=
μ
′
]
-
1
/
2
| is negligible.)Signature Based on Proof of Knowledge. In our group signature, we apply the conversion of the underlying interactive zero knowledge (ZK) proof into noninteractive ZK (NIZK) proof by applying the Fiat-Shamir heuristic [35]. We describe such converted signature based on proof of knowledge (SPK) as SPK
{
x
:
(
y
,
x
)
∈
R
}
(
M
), where x is the knowledge to be proved, R is a relation (e.g., y
=
g
x in the case of the knowledge of the discrete logarithm), and M is a signed message. The SPK has an extractor of the proved knowledge from two accepting protocol views whose commitments are the same but challenges are different.


## 2.1. Bilinear Groups and Complexity Assumptions

Definition 1 (bilinear groups).
LetG
1, G
2, and G
T be cyclic groups with prime order p, and G
1
=
〈
g
〉 and G
2
=
〈
h
〉. Let e
:
G
1
×
G
2
→
G
T be an (efficient computable) bilinear map with the following properties: (
1
) bilinearity: for all (
g
,
g
′
)
∈
G
1
2 and (
h
,
h
′
)
∈
G
2
2, e
(
g
g
′
,
h
)
=
e
(
g
,
h
)
e
(
g
′
,
h
) and e
(
g
,
h
h
′
)
=
e
(
g
,
h
)
e
(
g
,
h
′
) hold, and (
2
) nondegeneracy: e
(
g
,
h
)
≠
1
T, where 1
T is the unit element over G
T.Definition 2 (the computational Diffie-Hellman (CDH) assumption).
We say that the CDH assumption holds if, for all PPT adversaryA, Pr
[
A
(
g
1
,
g
1
a
,
g
1
b
)
=
g
1
a
b
] is negligible, where g
1
←
$
G
1 and (
a
,
b
)
←
$
Z
p
2.Definition 3 (the decision Diffie-Hellman (DDH) assumption).
We say that the DDH assumption holds if, for all PPT adversaryA, |
Pr
[
A
(
g
1
,
g
1
′
,
g
1
x
,
g
1
′
x
)
=
0
]
-
Pr
[
A
(
g
1
,
g
1
′
,
g
1
x
,
g
1
′
r
)
=
0
]
| is negligible, where (
g
1
,
g
1
′
)
←
$
G
1
2 and (
x
,
r
)
←
$
Z
p
2 with x
≠
r.Definition 4 (the decision linear (DLIN) assumption [2]).
We say that the DLIN assumption holds if, for all PPT adversaryA, |
Pr
[
A
(
u
,
v
,
h
,
u
a
,
v
b
,
h
a
+
b
)
=
0
]
-
Pr
[
A
(
u
,
v
,
h
,
u
a
,
v
b
,
η
)
=
0
]
| is negligible, where (
u
,
v
,
h
,
η
)
←
$
G
2
4 and (
a
,
b
)
←
$
Z
p
2.Definition 5 (the hidden strong Diffie-Hellman (HSDH) assumption [34]).
We say thatl-HSDH assumption holds if, for all PPT adversary A, Pr
[
A
(
g
1
,
h
,
h
ω
,
(
g
1
1
/
(
ω
+
c
i
)
,
h
x
i
)
i
=
1
,
…
,
l
)
=
(
g
1
1
/
(
ω
+
x
)
,
h
x
)
∧
∀
x
i
≠
x
] is  negligible, where (
g
1
,
h
)
←
$
G
1
×
G
2, (
ω
,
x
1
,
…
,
x
l
)
←
$
Z
p
l
+
1 and x
∈
Z
p.Definition 6 (the strong Diffie-Hellman (SDH) assumption [56]).
We say thatq-SDH assumption holds if, for all PPT adversary A, Pr
[
A
(
g
1
,
h
,
h
ω
,
h
ω
2
,
…
,
h
ω
q
)
=
(
g
1
1
/
(
ω
+
x
)
,
x
)
] is negligible, where (
g
1
,
h
)
←
$
G
1
×
G
2,  ω
←
$
∈
Z
p, and x
∈
Z
p.Definition 7 (the external Diffie-Hellman (XDH) assumption [4]).
Let(
G
1
,
G
2
,
G
T
) be a bilinear group. We say that the XDH assumption holds if for all PPT adversary A, the DDH assumption over G
1 holds.


## 2.2.  Other Cryptographic Tools

In this section, we introduce cryptographic tools applied for our construction.BBS+ Signature [2, 6, 32, 57]. Let L be the number of signed messages and let (
G
1
,
G
2
,
G
T
) be a bilinear group. Select g
,
g
1
,
…
,
g
L
←
$
G
1, h
←
$
G
2, and ω
←
Z
p, and compute Ω
=
g
ω. The signing key is ω and the verification key is (
p
,
G
1
,
G
2
,
G
T
,
e
,
g
,
g
1
,
…
,
g
L
+
1
,
h
,
Ω
). For a set of signed messages (
m
1
,
…
,
m
L
)
∈
Z
p
L, choose r
,
y
←
$
Z
p, and compute A
=
(
g
1
m
1
⋯
g
L
m
L
g
L
+
1
r
g
)
1
/
(
ω
+
y
). For a signature (
A
,
r
,
y
), the verification algorithm output 1 if e
(
A
,
Ω
h
y
)
=
e
(
g
1
m
1
⋯
g
L
m
L
g
L
+
1
r
,
h
) holds. The BBS+ signature scheme satisfies existential unforgeability against chosen message attack (EUF-CMA) under the q-SDH assumption. (First an adversary A is given vk from the challenger C. Then A sends messages to C and obtains the corresponding signatures. Finally, A outputs a message/signature pair (
M
*
,
σ
*
). We say that A wins if (
M
*
,
σ
*
) is valid and A has not sent M
* as a signing query. The EUF-CMA security guarantees that the probability Pr
[
A
wins
] is negligible.)Linear Encryption [2]. A public key is pk
=
(
u
,
v
,
h
)
∈
G
2 such that u
X
1
=
v
X
2
=
h for X
1
,
X
2
∈
Z
p. The corresponding secret key is (
X
1
,
X
2
). For a plaintext M
∈
G
2, choose δ
1
,
δ
2
←
$
Z
p and compute a ciphertext C
=
(
F
1
,
F
2
,
F
3
), where F
1
=
M
·
h
δ
1
,
δ
2, F
2
=
u
δ
1, and F
3
=
v
δ
2. C can be decrypted as M
=
F
1
/
F
2
X
1
F
3
X
2. The linear encryption is IND-CPA secure under the DLIN assumption. (First an adversary A is given pkfrom the challenger C. Then A sends the challenge message (
M
0
*
,
M
1
*
) to C, and C chooses μ
←
$
{
0,1
} and computes the challenge ciphertext C
* which is a ciphertext of M
μ
*. A is given C
* and outputs a bit μ
′. The IND-CPA security guarantees that |
Pr
[
μ
=
μ
′
]
-
1
/
2
| is negligible.)Signature Based on Proof of Knowledge. In our group signature, we apply the conversion of the underlying interactive zero knowledge (ZK) proof into noninteractive ZK (NIZK) proof by applying the Fiat-Shamir heuristic [35]. We describe such converted signature based on proof of knowledge (SPK) as SPK
{
x
:
(
y
,
x
)
∈
R
}
(
M
), where x is the knowledge to be proved, R is a relation (e.g., y
=
g
x in the case of the knowledge of the discrete logarithm), and M is a signed message. The SPK has an extractor of the proved knowledge from two accepting protocol views whose commitments are the same but challenges are different.


## 3. Definitions of Group Signature with the Property of Hiding the Number of Revoked Users

Here, we define the syntax of revocable group signature and security requirements (anonymity with respect to the revocation and traceability) by adapting [6]. Note that our definition follows the static group settings as in the BMW model [27], but we can easily handle the dynamic group settings as in the BSZ model [28] (and nonframeability) by adding an interactive join algorithm.Definition 8 (syntax ofr-hiding revocable group signature).
Setup. This probabilistic setup algorithm takes as input the security parameter 1
κ and returns public parameters params.
KeyGen. This probabilistic key generation algorithm (for GM) takes as input the maximum number of users N and params and returns the group public key gpk, GM’s secret key msk, all user’s secret key {
us
k
i
}
i
∈
[
1
,
N
], and the initial revocation-dependent value T
0.
GSign. This probabilistic signing algorithm (for a user U
i) takes as input gpk, us
k
i, a signed message M, and a revocation-dependent value (in the period t) T
t and returns a group signature σ.
Verify. This deterministic verification algorithm takes as input gpk,M, σ, and T
t and returns 1 if σ is a valid group signature and 0 otherwise.
Revoke. This (potentially) probabilistic revocation algorithm takes as input gpk, msk, a set of revoked users R
L
t
+
1
=
{
U
i
}, and T
t and returns T
t
+
1.
Open. This deterministic algorithm takes as input msk and a valid pair(
M
,
σ
) and returns the identity of the signer of σ ID. If ID is not a group member, then the algorithm returns 0.In theRevoke algorithm, we setR
L
0
=
∅ and assume that the nonrevoked users in t are {
U
1
,
…
,
U
N
}
∖
R
L
t. Under this setting, boomerang users (who rejoin the group) are available (i.e., U
i such that U
i
∈
R
L
t
-
1 and U
i
∉
R
L
t). In addition, if an invalid pair (
M
,
σ
) is input to theOpen algorithm, then theOpen algorithm easily detects this fact by using theVerify algorithm. So, we exclude this case from the definition of theOpen algorithm.Next, we define anonymity with respect to the revocation and traceability. As the main difference among our anonymity definition and previous ones,A can issue the revocation queries against the challenge users in order to guarantee the unlinkability of revoked users. Note that we do not consider the CCA-anonymity, where an adversary A can issue the open queries. So, we just handle the CPA-anonymity [2] only in this paper. However, as mentioned by Boneh et al. [2], the CCA-anonymity can be handled by applying a CCA secure public key encryption for implementing the open algorithm.Definition 9 (anonymity with respect to the revocation).
Setup. The challenger C runs theSetup algorithm and theKeyGen algorithm and obtains params, gpk, msk, and all {
us
k
i
}
i
=
1
N. C gives params and gpkto A and sets t
=
0, R
U
0
=
∅, and CU
=
∅, where R
U
0 denotes the (initial) set of IDs of revoked users and CU denotes the set of IDs of corrupted users.
Queries.A can issue the following queries.Revocation. A can request the revocation of users I
D
i
1
,
…
,
I
D
i
k
t
+
1 for some constant k
t
+
1
∈
[
1
,
N
]. C runs T
t
+
1
←
Revoke
(
msk
,
{
I
D
i
1
,
…
,
I
D
i
k
t
+
1
}
,
T
t
) and adds I
D
i
1
,
…
,
I
D
i
k
t
+
1 to R
U
t
+
1.
Signing.  A can request a group signature on a message M for a user U
i where I
D
i
∉
CU. C runs σ
← GSign
(
gpk
,
us
k
i
,
M
,
T
t
), where T
t is the current revocation-dependent value and gives σ to A.
Corruption. A can request the secret key of a user U
i. C adds I
D
i to CU and gives us
k
i to A.
Challenge. A sends a message M
* and two users U
i
0 and U
i
1, where I
D
i
0
,
I
D
i
1
∉
CU. C chooses a bit b
←
{
0,1
} and runs σ
*
←
G
S
i
g
n
(
gpk
,
usk
i
b
,
M
*
,
T
t
*
), where T
t
* is the current revocation-dependent value and gives σ
* to A.
Queries. It is the same as the previous one (note that no corruption query for the challenge users is allowed).
Output. A outputs a guessing bit b
′
∈
{
0,1
}.
We say that anonymity holds if, for all PPT adversariesA, the advantage
(1)
A
d
v
A
anon
(
κ
)
∶
=
|
Pr
[
b
=
b
′
]
-
1
2
|
is negligible.There are two types of revocable group signature such that(
1
) any users can make a valid group signature, but anyone can check whether a signer has been revoked or not [3, 5, 10, 17], or (
2
) no revoked user can make a valid group signature without breaking traceability [2, 4, 6, 11]. We implicitly require the second type of revocable group signature, since clearly anonymity is broken if one of the challenge users is revoked in a first type scheme. We also require that the challenger C (that has msk) can break traceability to compute the challenge group signature σ
* for the case that a challenger user is revoked. Note that since msk is used for generating user’s secret keys, obviously any entity with msk makes an “untraceable” group signature, and this fact does not detract the security of our group signature.One may think that the above anonymity definition can be extended thatA can issue the corruption query against the challenge users as in the full-anonymity [27]. It might be desired that r is not revealed even if revoked users reveal their secret signing keys, since their signing keys are already meaningless (i.e., the rights of signing have expired). For example, if users are not intentionally revoked (e.g., a user has not paid in the outsourcing businesses example [14]), then users might reveal their secret signing keys to compromise the systems. Or, even if users are intentionally revoked (e.g., they feel that this service is not interesting in the outsourcing businesses example), they might reveal their secret signing keys as a crime for pleasure. However, even if r is kept hidden when revoked users reveal their secret signing keys, one can easily guess r by counting the number of revealed secret keys. So, in our opinion such secret key leakage resilient property is too strong, and therefore, our proposed group signature does not follow this leakage property.Next, we define traceability.Definition 10 (traceability).
Setup. The challenger C runs theSetup algorithm and theKeyGen algorithm and obtains params, gpk, msk, and all {
us
k
i
}
i
=
1
N. C gives params and gpk to A and sets t
=
0, R
U
0
=
∅, and CU
=
∅, where R
U
0 denotes the (initial) set of IDs of revoked users and CU denotes the set of IDs of corrupted users.
Queries.A can issue the following queries.
Revocation.A can request the revocation of users I
D
i
1
,
…
,
I
D
i
k
t
+
1 for some constant k
t
+
1
∈
[
1
,
N
]. C runs T
t
+
1
←
R
e
v
o
k
e
(
msk
,
{
I
D
i
1
,
…
,
I
D
i
k
t
+
1
}
,
T
t
) and adds I
D
i
1
,
…
,
I
D
i
k
t
+
1 to R
U
t
+
1.
GSigning.A can request a group signature on a message M for a user U
i where I
D
i
∉
CU. C runs σ
← GSign
(
gpk
,
us
k
i
,
M
,
T
t
), where T
t is the current revocation-dependent value and gives σ to A.
Corruption.A can request the secret key of a user U
i. C adds I
D
i to CU and gives us
k
i to A.
Opening.A can request to a group signature σ on a message M. C returns the result ofOpen(
msk
,
M
,
σ
) to A.
Output.A outputs a past interval t
*
≤
t for the current interval t, and (
M
*
,
σ
*
).
We say thatA wins if (
1
)
∧
(
2
)
∧
(
(
3
)
∨
(
4
)
) holds, where(1)
Verify
(
gpk
,
M
*
,
σ
*
,
T
t
*
)
=
1,
(2)
A did not obtain σ
* by making a signing query at M
*,
(3)
forI
D
i
*
←
Open
(
msk
,
M
*
,
σ
*
), I
D
i
*
∉
CU,
(4)
forI
D
i
*
←
Open
(
msk
,
M
*
,
σ
*
), I
D
i
*
∈
R
U
t
*.
We say that traceability holds if, for all PPT adversariesA, the advantage
(2)
A
d
v
A
trace
(
κ
)
∶
=
Pr
[
A
wins
]
is negligible.


## 4. Proposed Group Signature Scheme with Hiding of the Number of Revoked Users

In this section, we propose anr-hiding revocable group signature scheme by applying ABGS. Before explaining our scheme, we introduce ABGS as follows.Attribute-Based Group Signature (ABGS). ABGS [22–25, 58] is a kind of group signature, where a user with a set of attributes can prove anonymously whether he/she has these attributes or not. Anonymity means a verifier cannot identify who the actual signer is among group members. As a difference from attribute-based signature (ABS) [59–68], there is an opening manager (as in group signatures) who can identify the actual signer (anonymity revocation), and a verifier can “explicitly” verify whether a user has these attributes or not [22, 24, 25]. By applying this explicit attribute verification, anonymous survey for the collection of attribute statistics is proposed [22]. As one exception, the Fujii et al. ABGS scheme [23] achieves signer-attribute privacy (as in ABS), where a group signature does not leak which attributes were used to generate it, except that assigned attributes satisfy a predicate. As another property (applied in our construction), the dynamic property has been proposed in [22], where the attribute predicate can be updated without reissuing the user’s secret keys.Our Methodology. We consider two attributes: (1) valid group user and (2) the user’s identity (say U
i), and apply the dynamic property of ABGS [22] and the signer-attribute privacy of ABGS [23]. Here we explain our methodology. Let the initial access tree be represented as in Figure 1.Figure 1
Initial access tree.Due to the signer-attribute privacy, a userU
i can anonymously prove that he/she has attributes “valid group user” and “U
i.” Namely, anyone can verify whether the signer’s attributes satisfy the access tree, without detecting the actual attribute (i.e., the user’s identity).When a user (sayU
1) is revoked, the tree structure is changed as in Figure 2.Figure 2
Modified access tree.Due to the dynamic property of ABGS, this modification can be done without reissuing the user’s secret keys. By removing the attribute “valid group user” from the subtree ofU
1, we can express the revocation of U
1, since U
1 cannot prove that his/her attributes satisfy the current access tree.In addition, we propose randomization and dummy attribute techniques to implement the revocation procedure (Figure3). We apply the Boldyreva multisignature scheme [26], since it is applied for the computation of the membership certificate in the Fujii et al. ABGS. Let t be the time interval and let v denote the attribute “valid group user.”Figure 3
Our randomization and dummy attribute technique.For a nonrevoked userU
i, GM publishes the dummy value g
1
s
v
,
t
,
i
x
i. Then U
i can compute g
1
(
s
v
,
t
,
i
+
s
i
)
x
i
(
=
H
i
) from d
T
,
t
,
i
=
g
1
s
v
,
t
,
i
x
i and U
i’s secret key B
i
=
g
1
s
i
x
i. Let U
i be revoked in the time interval t
+
1. Then, GM publishes a randomized dummy value g
1
s
v
,
t
+
1
,
i
′ (instead of g
1
s
v
,
t
+
1
,
i
x
i), and therefore, U
i cannot compute g
(
s
v
,
t
+
1
,
i
+
s
i
)
x
i due to the CDH assumption. Note that (
g
1
s
v
,
t
+
1
,
i
+
s
i
,
g
1
s
v
,
t
+
1
,
i
x
i
) and (
g
1
s
v
,
t
+
1
,
i
+
s
i
,
g
1
s
v
,
t
+
1
,
i
′
) are indistinguishable under the XDH assumption, where the DDH assumption holds in G
1. So, no one can decide whether U
i is a revoked user or not by observing either (
g
1
s
v
,
t
+
1
,
i
+
s
i
,
g
1
s
v
,
t
+
1
,
i
x
i
) or (
g
1
s
v
,
t
+
1
,
i
+
s
i
,
g
1
s
v
,
t
+
1
,
i
′
). This is our main idea for preventing revealing the number of revoked users r.Next, we give our group signature scheme.Construction 1 (proposedr-hiding revocable group signature scheme).
Setup(1
κ). Select a bilinear group (
G
1
,
G
2
,
G
T
) with prime order p and a bilinear map e
:
G
1
×
G
2
→
G
T, g
,
g
1
,
…
,
g
4
,
g
~
←
$
G
1, h
~
←
$
G
2. Output params
=
(
p
,
G
1
,
G
2
,
G
T
,
e
,
g
,
g
1
,
g
2
,
g
3
,
g
4
,
g
~
,
h
~
,
H
), where H
:
{
0,1
}
*
→
Z
p is a hash function modeled as a random oracle.
KeyGen
(
p
a
r
a
m
s
,
N
). Let (
U
1
,
…
,
U
N
) be all users. Set t
=
0. Select ω
1
,
ω
2
,
X
1
,
X
2
,
x
1
,
…
,
x
N
,
s
1
,
…
,
s
N
←
$
Z
p
*. Compute(i)
u
,
v
,
h
∈
G
2 with the condition u
X
1
=
v
X
2
=
h(note that (
u
,
v
,
h
) is a public key of the linear encryption and (
X
1
,
X
2
) is the corresponding secret key),
(ii)
K
i
,
1
=
g
1
1
/
(
ω
1
+
x
i
), K
i
,
2
=
h
x
i, and B
i
=
g
1
s
i
x
i for all i
∈
[
1
,
N
],
(iii)
Ω
1
=
h
ω
1 and Ω
2
=
h
ω
2.For all i
∈
[
1
,
N
], choose s
v
,
0
,
i
,
y
0
,
i
,
r
0
,
i
←
$
Z
p
*. If s
v
,
0
,
i
+
s
i
=
0
mod
⁡
p, then choose s
v
,
0
,
i again until s
v
,
0
,
i
+
s
i
≠
0
mod
⁡
p holds. Set s
T
,
0
,
i
:
=
s
v
,
0
,
i
+
s
i and compute(i)
h
T
,
0
,
i
=
g
1
s
T
,
0
,
i,
(ii)
A
0
,
i
=
(
g
1
s
T
,
0
,
i
g
2
t
g
3
r
0
,
i
g
4
)
1
/
(
ω
2
+
y
0
,
i
) (which is a BBS+ signature for signed messages (
s
T
,
0
,
i
,
t
)
),
(iii)
d
T
,
0
,
i
∶
=
g
1
s
v
,
0
,
i
x
i.Set Sign
(
s
T
,
0
,
i
,
i
)
∶
=
(
A
0
,
i
,
y
0
,
i
,
r
0
,
i
). Output(i)
gpk
=
(
params
,
Ω
1
,
Ω
2
,
u
,
v
,
H
), where H
:
{
0,1
}
*
→
Z
p
* is a hash function which is modeled as a random oracle,
(ii)
msk
=
(
X
1
,
X
2
,
s
1
,
…
,
s
N
,
s
v
,
0,1
,
…
,
s
v
,
0
,
N
,
x
1
,
…
,
x
N
,
reg
∶
=
{
(
K
i
,
2
,
i
)
}
i
=
1
N
),
(iii)
us
k
i
=
(
K
i
,
1
,
K
i
,
2
,
B
i
) for all i
∈
[
1
,
N
], and 0,
(iv)
T
0
=
{
(
Sign
(
s
T
,
0
,
i
,
i
)
,
h
T
,
0
,
i
,
d
T
,
0
,
i
)
}
i
=
1
N.GSign
(
g
p
k
,
u
s
k
i
,
M
,
T
t
). Let U
i be a nonrevoked user in the current time interval t. That is, for (
Sign
(
s
T
,
t
,
i
,
i
)
,
h
T
,
t
,
i
,
d
T
,
t
,
i
)
∈
T
t, h
T
,
t
,
i
=
g
1
s
v
,
t
,
i
+
s
i
∶
=
g
1
s
T
,
t
,
i and d
T
,
t
,
i
=
g
1
s
v
,
t
,
i
x
i hold for some unknown exponent s
v
,
t
,
i
∈
Z
p
*. U
i chooses r
1
,
r
2
,
…
,
r
10
,
δ
1
,
δ
2
←
$
Z
p
*, sets α
=
-
r
1
r
2, β
=
-
r
2
r
4, β
′
=
r
5
y
t
,
i
-
r
4, γ
=
r
2
r
6
+
r
7, γ
′
=
r
4
r
8
+
r
9, and γ
′′
=
r
10
y
t
,
i, and computes
(3)
H
i
=
B
i
·
d
T
,
t
,
i
=
g
1
s
i
x
i
+
s
v
,
t
,
i
x
i
=
h
T
,
t
,
i
x
i
,
T
1
=
K
i
,
1
g
~
r
1
,
T
2
=
K
i
,
2
h
~
r
2
,
T
3
=
H
i
g
~
r
3
,
T
4
=
h
T
,
t
,
i
g
~
r
4
,
T
5
=
A
t
,
i
g
~
r
5
,
C
1
=
g
r
1
g
~
r
6
,
C
2
=
g
α
g
~
r
7
,
C
3
=
g
r
2
g
~
r
8
,
C
4
=
g
β
g
~
r
9
,
C
5
=
g
r
10
g
~
-
r
5
,
C
6
=
g
γ
′′
g
~
-
r
4
,
F
1
=
K
i
,
2
h
δ
1
+
δ
2
,
F
2
=
u
δ
1
,
F
3
=
v
δ
2
.
Next, we explain the relations proved in SPK V which proves the following three things.(1)
A signer has a valid(
K
i
,
1
,
K
i
,
2
) generated by theKeyGen algorithm.
(i)
(
K
i
,
1
,
K
i
,
2
) can be verified by using the public value Ω
1 such that
(4)
e
(
K
i
,
1
,
Ω
1
K
i
,
2
)
=
e
(
g
1
,
h
)
.
(ii)
SinceK
i
,
1 (resp., K
i
,
2) is hidden such that T
1
=
K
i
,
1
g
~
r
1, (resp., T
2
=
K
i
,
2
h
~
r
2), this relation is represented as
(5)
e
(
T
1
,
Ω
1
T
2
)
e
(
g
1
,
h
)
=
e
(
g
~
,
Ω
1
T
2
)
r
1
e
(
T
1
,
h
~
)
r
2
e
(
g
~
,
h
~
)
α
.
(iii)
We need to guarantee the relationα
=
-
r
1
r
2 in the relation above. To prove this, introduce an intermediate value γ
=
r
2
r
6
+
r
7 and prove that
(6)
C
1
=
g
r
1
g
~
r
6
∧
C
2
=
g
α
g
~
r
7
∧
C
2
=
C
1
-
r
2
g
~
γ
.
Note that C
2
=
C
1
-
r
2
g
~
γ
=
(
g
r
1
g
~
r
6
)
-
r
2
g
~
γ
=
g
-
r
1
r
2
g
~
-
r
2
r
6
+
γ
=
g
α
g
~
r
7 yields α
=
-
r
1
r
2 and γ
=
r
2
r
6
+
r
7.
(2)
A signer has not been revoked.
(i)
A nonrevoked signer can computeH
i
=
h
T
,
t
,
i
log
⁡
h
K
i
,
2
=
(
g
1
s
T
,
t
,
i
)
x
i from B
i and d
T
,
t
,
i, where s
T
,
t
,
i is a signed message of A
t
,
i. These satisfy the following relations:
(7)
e
(
h
T
,
t
,
i
,
K
i
,
2
)
=
e
(
H
i
,
h
)
,
e
(
A
t
,
i
,
Ω
2
h
y
t
,
i
)
=
e
(
g
1
s
T
,
t
,
i
g
2
t
g
3
r
t
,
i
g
4
,
h
)
.
(ii)
SinceH
i, h
T
,
t
,
i, and A
i are hidden such that T
3
=
H
i
g
~
r
3, T
4
=
h
T
,
t
,
i
g
~
r
4, and T
5
=
A
t
,
i
g
~
r
5, these relations are represented as
(8)
e
(
T
4
,
T
2
)
e
(
T
3
,
h
)
=
e
(
g
~
,
T
2
)
r
4
e
(
T
4
,
h
~
)
r
2
e
(
g
~
,
h
~
)
β
e
(
g
~
,
h
)
r
3
,
e
(
T
5
,
Ω
2
)
e
(
g
4
,
h
)
e
(
T
4
,
h
)
e
(
g
2
,
h
)
t
=
e
(
g
~
,
Ω
2
)
r
5
e
(
g
3
,
h
)
r
t
,
i
e
(
g
~
,
h
)
β
′
e
(
T
5
,
h
)
y
t
,
i
.
(iii)
We need to guarantee the relationsβ
=
-
r
2
r
4 and β
′
=
r
5
y
t
,
i
-
r
4 in the relations above. To prove these, introduce intermediate values γ
′
=
r
4
r
8
+
r
9 and γ
′′
=
r
10
y
t
,
i and prove that
(9)
C
3
=
g
r
2
g
~
r
8
∧
C
4
=
g
β
g
~
r
9
∧
C
4
=
C
3
-
r
4
g
~
γ
′
,
C
5
=
g
r
10
g
~
-
r
5
∧
C
6
=
g
γ
′′
g
~
-
r
4
∧
C
6
=
C
5
y
t
,
i
g
~
β
′
.
(iv)
As inα and γ explained before, relations β
=
-
r
2
r
4, β
′
=
r
5
y
t
,
i
-
r
4, γ
′
=
r
4
r
8
+
r
9, and γ
′′
=
r
10
y
t
,
i are obtained from the relations above.
(v)
Note that(
A
t
,
i
,
r
t
,
i
,
y
t
,
i
) is a BBS+ signature for signed messages (
s
T
,
t
,
i
,
t
), and therefore V depends on the current time interval t.
(3)
A value for theOpen algorithm is included in σ.
(i)
(
F
1
,
F
2
,
F
3
) is a ciphertext (of the linear encryption scheme) of the plaintext K
i
,
2, which can be computed by decrypting (
F
1
,
F
2
,
F
3
) using msk.According to the above explanations, compute the SPK V proving the following relations (we give the detailed SPK V in the Appendix):
(10)
V
=
SPK
{
(
r
1
,
r
2
,
r
3
,
r
4
,
r
5
,
r
6
,
r
7
,
r
8
,
r
9
,
r
10
,
y
t
,
i
,
r
t
,
i
,
α
,
β
,
β
′
,
γ
,
γ
′
,
γ
′′
,
δ
1
,
δ
2
)
:
e
(
g
~
,
Ω
2
)
r
5
e
(
g
3
,
h
)
r
t
,
i
e
(
g
~
,
h
)
β
′
e
(
T
5
,
h
)
y
t
,
i
mmmmmm
e
(
T
1
,
Ω
1
T
2
)
e
(
g
1
,
h
)
=
e
(
g
~
,
Ω
1
T
2
)
r
1
e
(
T
1
,
h
~
)
r
2
e
(
g
~
,
h
~
)
α
mmmmmmmmmmmmm
∧
e
(
T
4
,
T
2
)
e
(
T
3
,
h
)
mmmmmmmmmmmm
=
e
(
g
~
,
T
2
)
r
4
e
(
T
4
,
h
~
)
r
2
e
(
g
~
,
h
~
)
β
e
(
g
~
,
h
)
r
3
mmmmmmmmmmmm
∧
e
(
T
5
,
Ω
2
)
e
(
g
4
,
h
)
e
(
T
4
,
h
)
e
(
g
2
,
h
)
t
mmmmmmmmmmmmm
=
e
(
g
~
,
Ω
2
)
r
5
e
(
g
3
,
h
)
r
t
,
i
e
(
g
~
,
h
)
β
′
e
(
T
5
,
h
)
y
t
,
i
mmmmmmmmmmmmm
∧
C
1
=
g
r
1
g
~
r
6
∧
C
2
=
g
α
g
~
r
7
∧
C
2
mmmmmmmmmmmmm
=
C
1
-
r
2
g
~
γ
∧
C
3
=
g
r
2
g
~
r
8
∧
C
4
=
g
β
g
~
r
9
∧
C
4
mmmmmmmmmmmmm
=
C
3
-
r
4
g
~
γ
′
∧
C
5
=
g
r
10
g
~
-
r
5
∧
C
6
=
g
γ
′′
g
~
-
r
4
∧
C
6
mmmmmmmmmmmmm
=
C
5
y
t
,
i
g
~
β
′
∧
T
2
F
1
=
h
~
r
2
h
δ
1
+
δ
2
∧
F
2
mmmmmmmmmmmmm
e
(
g
~
,
Ω
2
)
r
5
e
(
g
3
,
h
)
r
t
,
i
e
(
g
~
,
h
)
β
′
e
(
T
5
,
h
)
y
t
,
i
=
u
δ
1
∧
F
3
=
v
δ
2
h
~
r
2
h
δ
1
+
δ
2
}
(
M
)
.
Output σ
=
(
C
1
,
C
2
,
C
3
,
C
4
,
C
5
,
C
6
,
F
1
,
F
2
,
F
3
,
T
1
,
T
2
,
T
3
,
T
4
,
T
5
,
V
).Verify
(
g
p
k
,
M
,
σ
,
T
t
). Return 1 if σ is a valid group signature and 0 otherwise. We give the procedure of the verification algorithm in the Appendix.Revoke
(
g
p
k
,
m
s
k
,
{
U
i
}
,
T
t
). Let R
L
t
+
1
:
=
{
U
i
} be a set of revoked users. Set t
→
t
+
1. For all i
∈
{
i
∣
U
i
∈
R
L
t
+
1
}, choose s
v
,
t
+
1
,
i
′
←
$
Z
p
*. For all i
∈
[
1
,
N
], choose s
v
,
t
+
1
,
i
,
y
t
+
1
,
i
,
r
t
+
1
,
i
←
$
Z
p
* (until s
v
,
t
+
1
,
i
+
s
i
≠
0
mod
⁡
p holds), set s
T
,
t
+
1
,
i
:
=
s
v
,
t
+
1
,
i
+
s
i, and compute
(11)
h
T
,
t
+
1
,
i
=
g
s
T
,
t
+
1
,
i
,
A
t
+
1
,
i
=
(
g
1
s
T
,
t
+
1
,
i
g
2
t
+
1
g
3
r
t
+
1
,
i
g
4
)
1
/
(
ω
2
+
y
t
+
1
,
i
)
,
and compute d
T
,
t
+
1
,
i such that
(12)
d
T
,
t
+
1
,
i
=
{
g
1
s
v
,
t
+
1
,
i
x
i
(
U
i
∉
R
L
t
+
1
)
g
1
s
v
,
t
+
1
,
i
′
(
U
i
∈
R
L
t
+
1
)
,
and set Sign
(
s
T
,
t
+
1
,
i
,
i
)
=
(
A
t
+
1
,
i
,
y
t
+
1
,
i
,
r
t
+
1
,
i
). Output T
t
+
1
=
{
(
Sign
(
s
T
,
t
+
1
,
i
,
i
)
,
h
T
,
t
+
1
,
i
,
d
T
,
t
+
1
,
i
)
}
i
=
1
N.Open
(
g
p
k
,
m
s
k
,
M
,
σ
). Compute F
1
/
F
2
X
1
F
3
X
2
=
K and search i such that (
K
i
,
2
,
i
)
∈
reg and K
=
K
i
,
2. If there is no such i, output 0. Otherwise, output i.In our scheme, no public values have size dependent onr and no costs of theGSign algorithm (or theVerify algorithm) depend on r or N. In addition, our scheme satisfies anonymity with respect to the revocation which guarantees the unlinkability of revoked users. So, in our scheme, no r is revealed.


## 5. Security Analysis

Theorem 11.
The proposed group signature scheme satisfies anonymity with respect to the revocation under the DLIN assumption and the XDH assumption in the random oracle model.Proof.
This proof contains three games, Games 0, 1, and 2. Game 0 is the same as anonymity game. In Game 1, alld
T
,
t
,
i where i
∈
[
1
,
N
] is randomly chosen. Let A
1 be the adversary who breaks anonymity with respect to the revocation of our scheme and let B
1 be the simulator. First, B
1 chooses all values and sets up the scheme as in Game 0, except all d
T
,
t
,
i, where i
∈
[
1
,
N
] are randomly chosen. Note that still B
1 can answer all queries issued from A
1 since B
1 knows all secret values and can compute h
T
,
t
,
i
x
i for all i
∈
[
1
,
N
]. Under the XDH assumption, Game 0 and Game 1 are identical.
Game 2 is the same as Game 1, except that the challenge group signature contains the challenge ciphertext of the linear encryption. In Game 2, letC
2 be the challenger of the linear encryption and let A
2 be the adversary who breaks anonymity with respect to the revocation of our scheme. We construct algorithm B
2 that breaks the IND-CPA security of the linear encryption. First, C
2 gives the public key of the linear encryption (
u
,
v
,
h
). B
2 chooses all values, except for (
u
,
v
,
h
), and therefore B
2 can answer all queries issued from A
2. In the challenge phase, A
2 sends (
M
*
,
U
i
0
,
U
i
1
). Let h
x
i
0 and h
x
i
1 be (a part of) secret key of U
i
0 and U
i
1, respectively. B
2 sets M
0
*
:
=
h
x
i
0 and M
1
*
:
=
h
x
i
1 and sends (
M
0
*
,
M
1
*
) to C
2 as the challenge messages of the linear encryption. C
2 sends the challenge ciphertext C
*. B
2 sets C
*
=
(
F
1
,
F
2
,
F
3
) and computes the challenge group signature σ
*. Note that B
2 does not know the random number (
δ
1
*
,
δ
2
*
) and μ
∈
{
0,1
} such that C
*
=
(
h
x
i
μ
h
δ
1
*
+
δ
2
*
,
u
δ
1
*
,
v
δ
2
*
), since (
δ
1
*
,
δ
2
*
,
μ
) are chosen by C. So, B
2 uses the backpatch of the random oracle H for computing σ
* and includes C
* in σ
*. Then, all values (except for C
*) are independent of μ. Note that even if U
i
μ is revoked in the challenge interval, B
2 can compute σ
*, since B
2 knows msk. Finally, A
2 outputs the guessing bit μ
′
∈
{
0,1
}. B
2 outputs μ
′ as the guessing bit of the IND-CPA game of the linear encryption.Theorem 12.
The proposed group signature scheme satisfies traceability under theN-HSDH assumption, the CDH assumption, and the N
t-SDH assumption, where t is the final time interval that A outputs (
M
*
,
σ
*
).Proof.
From the winning conditions of traceability, that is, eitherI
D
i
*
∉
CU or I
D
i
*
∈
R
U
t
*, an adversary is divided into the following three types: A
1, A
2, and A
3, as follows: let A
1 be an adversary who outputs (
M
*
,
σ
*
), where for I
D
i
*
←
Open
(
msk
,
M
*
,
σ
*
), I
D
i
*
∉
CU and U
i
*
∈
{
U
1
,
…
,
U
N
} hold. Let A
2 be an adversary who outputs (
M
*
,
σ
*
), where for I
D
i
*
←
Open
(
msk
,
M
*
,
σ
*
), I
D
i
*
∉
CU and U
i
*
∉
{
U
1
,
…
,
U
N
} hold. In addition, let A
3 be an adversary who outputs (
M
*
,
σ
*
), where for I
D
i
*
←
Open
(
msk
,
M
*
,
σ
*
), I
D
i
*
∈
R
U
t
* holds (note that since I
D
i
*
∈
R
U
t
*, U
i
*
∈
{
U
1
,
…
,
U
N
} holds).
We construct an algorithmB
1 (resp., B
2 and B
3) that breaks the N-HSDH assumption (resp., q-SDH assumption, where q is the number of signing queries, and the CDH assumption) by using A
1 (resp., A
2 and A
3).
First, we describeB
1. Let g
1
,
h
,
h
ω
1
,
{
(
g
1
1
/
(
ω
1
+
x
i
)
,
h
x
i
)
}
i
=
1
,
…
,
N be an N-HSDH instance. B
1 selects U
i
*
∈
{
U
1
,
…
,
U
N
}, and choose all values, except for g
1, h, and Ω
1
∶
=
h
ω
1. B
1 answers queries issued by A
1 as follows.
Revocation. A
1 requests the revocation of users I
D
i
1
,
…
,
I
D
i
k
t for some constant k
t
∈
[
1
,
N
]. Since B
1 knows ω
2, B
1 adds I
D
i
1
,
…
,
I
D
i
k
t to R
U
t and simply returns the result of the Revoke algorithm.
GSigning. A
1 requests a group signature on a message M for a user U
i where I
D
i
∉
CU. Since B
1 does not know g
1
x
i, B
1 computes σ by using the backpatch of the random oracle H and gives σ to A.
Corruption. A
1 requests the secret key of a user U
i. If U
i
=
U
i
*, then B
1 aborts. Otherwise, B
1 sets (
g
1
1
/
(
ω
1
+
x
i
)
,
h
x
i
)
=
(
K
i
,
1
,
K
i
,
2
), chooses s
i
′
←
$
Z
p
*, sets s
i
′
=
s
i
x
i, and computes B
i
=
g
s
i
′. B
1 adds I
D
i to CU and gives (
K
i
,
1
,
K
i
,
2
,
B
i
) to A
1.
Opening. Since B
1 has (
X
1
,
X
2
), B
1 simply returns the result of theOpen algorithm.
Finally,A
1 outputs a past interval t
*
≤
t for the current interval t and a pair (
M
*
,
σ
*
). By using the extractor of SPK, B
1 gets (
K
i
,
1
*
,
K
i
,
2
*
,
H
i
*
), where e
(
K
i
,
1
*
,
Ω
1
K
i
,
2
*
)
=
e
(
g
1
,
h
), e
(
h
T
,
t
,
i
,
K
i
,
2
*
)
=
e
(
H
i
*
,
h
), F
1
=
K
i
,
2
*
h
δ
1
+
δ
2, F
2
=
u
δ
1, and F
3
=
v
δ
2 hold. From (
F
1
,
F
2
,
F
3
), B
1 obtains i by using theOpen algorithm. If i
≠
i
*, then B
1 aborts. Otherwise, B
1 outputs (
K
i
,
1
*
,
K
i
,
2
*
) as a solution of the N-HSDH problem.
Next, we describeB
2 that outputs a forged BBS+ signature. Let C be the challenger of the BBS+ signature. B
2 is given (
g
,
g
1
,
g
2
,
g
3
,
g
4
,
h
,
Ω
2
) from C. B
2 chooses all values, except for (
g
,
g
1
,
g
2
,
g
3
,
g
4
,
h
,
Ω
2
). For each revocation query, B
2 issues N signing queries to C for obtaining A
·
,
i. So, B
2 needs to issue the signing query in N
t times. For other queries, B
2 can answer since B
2 knows all other secret values. Finally, A
3 outputs a past interval t
*
≤
t for the current interval t and a pair (
M
*
,
σ
*
). By using the extractor of SPK, B
2 gets (
A
t
*
,
i
*
,
y
t
*
,
i
*
,
r
t
*
,
i
*
), where e
(
A
t
*
,
i
*
,
Ω
2
h
y
t
*
,
i
*
)
=
e
(
g
1
s
T
,
t
*
,
i
*
g
2
t
*
g
3
r
t
*
,
i
*
g
4
,
h
). Note that since U
i
*
∉
{
U
1
,
…
,
U
N
}, B
2 does not obtain (
A
t
*
,
i
*
,
y
t
*
,
i
*
,
r
t
*
,
i
*
) from C. So, B
2 outputs a forged BBS+ signature (
A
t
*
,
i
*
,
y
t
*
,
i
*
,
r
t
*
,
i
*
).
Finally, we describeB
3 that breaks the CDH assumption. Let (
g
1
,
g
1
a
,
g
1
b
) be an CDH instance. B
3 selects U
i
*
∈
{
U
1
,
…
,
U
N
}, sets x
i
*
:
=
a and s
i
*
:
=
b, and chooses all values, except for g
1 and us
k
i
*. B
3 answers queries issued by A
3 as follows.
Revocation. A
3 requests the revocation of users I
D
i
1
,
…
,
I
D
i
k
t for some constant k
t. Since B
3 knows ω
2, B
3 adds I
D
i
1
,
…
,
I
D
i
k
t to R
U
t and simply returns the result of theRevoke algorithm.
GSigning. A
3 requests a group signature on a message M for a user U
i where I
D
i
∉
CU. B
3 computes σ by using the backpatch of the random oracle H and gives σ to A.
Corruption. A
3 requests the secret key of a user U
i. If U
i
=
U
i
*, then B
3 aborts. Otherwise, B
3 adds I
D
i to CU and gives (
K
i
,
1
,
K
i
,
2
,
B
i
) to A
3.
Opening. Since B
3 has (
X
1
,
X
2
), B
3 simply returns the result of theOpen algorithm.
Finally,A
3 outputs a past interval t
*
≤
t for the current interval t and a pair (
M
*
,
σ
*
). By using the extractor of SPK, B
3 gets H
i
*, where e
(
K
i
,
1
*
,
Ω
1
K
i
,
2
*
)
=
e
(
g
1
,
h
), e
(
h
T
,
t
,
i
,
K
i
,
2
*
)
=
e
(
H
i
*
,
h
), F
1
=
K
i
,
2
*
h
δ
1
+
δ
2, F
2
=
u
δ
1, and F
3
=
v
δ
2 hold. From (
F
1
,
F
2
,
F
3
), B
3 obtains i by using theOpen algorithm. If i
≠
i
*, then B
3 aborts. Otherwise, B
3 solves the CDH problem as follows. Since U
i
∈
R
L
t, B
3 has computed g
1
s
v
,
t
,
i
*
·
g
1
b
=
g
1
s
v
,
t
,
i
*
+
s
i
* and g
1
s
v
,
t
,
i
*
′. That is, H
i
*
=
B
i
*
·
g
1
s
v
,
t
,
i
*
x
i
=
g
1
a
b
+
a
s
v
,
t
,
i
*
x
i holds. So, B
3 outputs H
i
*
/
(
g
1
a
)
s
v
,
t
,
i
*
=
g
1
a
b as the solution of the CDH problem.


## 6. Discussion: Toward Efficient and Standard Model Construction

One drawback of our scheme is that the number of public values depends onN, since no common attribute can be applied for implementing the revocation procedure of “each” user. So, one may think that there might be a more trivial construction (without applying ABGS) if such a big-size public value is allowed. For example, as one of the most simple group signature constructions, let g
x
1
,
…
,
g
x
N be users’ public keys, and GM randomizes these values such that y
1
∶
=
(
g
x
1
)
r
GM
,
…
,
y
N
∶
=
(
g
x
N
)
r
GM and publishes y
∶
=
g
r
GM. Each user (say U
i) proves the knowledge of x
i for the relation (
g
r
GM
)
x
i using the OR relation such that SPK
{
x
:
y
x
=
y
1
∨
⋯
∨
y
x
=
y
N
}
(
M
) to hide the identity i
∈
[
1
,
N
]. If a user (say U
j) is revoked, then GM publishes a random value R
j (instead of (
g
x
j
)
r
GM). In this case, the number of revoked users is not revealed under the DDH assumption, since (
g
,
g
x
j
,
g
r
GM
,
(
g
x
j
)
r
GM
) is a DDH tuple. However, this trivial approach requires N-dependent signing/verification cost, whereas our scheme achieves constant proving costs.As another candidate, Sudarsono et al. [69] proposed an attribute-based anonymous credential system by applying an efficient pairing-based accumulator proposed by Camenisch et al. [70]. Since the Sudarsono et al. construction follows AND/OR relations of attributes, a revocable group signature scheme with the property of hiding r might be constructed. However, it is not obvious whether 2-DNF (disjunctive normal form) formulae ∨
i
=
1
N
(
valid
group
user
∧
U
i
) can be implemented or not in the Sudarsono et al. attribute-based proof system. Later, Begum et al. [71] proposed an attribute-based anonymous credential system for CNF (conjunctive normal form) formulae which can be converted to DNF formulae. However, these constructions require the N-dependent-size (N is the number of attributes in this context) public values to update the witness of users as in our group signature scheme. So, we insist that proposing a revocable group signature scheme with both the property of hiding r and constant proving costs is not trivial even if such a large-size public key is allowed.Libert et al. [72] proposed anonymous broadcast encryption, where information of a set of authorized users S (indicated by a user who encrypts a plaintext M) is not revealed from a ciphertext, except for the size of S. More precisely, they first considered a scheme, where there are N public keys (N is the total number of users in this context) and the user encrypts M (resp., 0) by using the corresponding user’s public key if a user belongs to S (resp., does not belong to S), using key-private public key encryption [73]. Though the size of ciphertext is O
(
N
), no information of S, including its size, is revealed. In order to improve the size of ciphertext of their first scheme, Abdalla et al. applied robust encryption [74] and constructed an anonymous broadcast encryption scheme whose ciphertext size is O
(
|
S
|
). In other words, they can reduce the ciphertext size at the expense of information of the size of S. In r-hiding group signature, the size of the set of revoked user needs to be hidden. To do so, we essentially use the same methodology of the Libert et al.’s first scheme, that is, adding dummies. Though an anonymous broadcast encryption scheme with sublinear size ciphertext has been proposed [75], this scheme only achieves outsider anonymity, where the receiver’s identities are hidden from outsiders; this security notion seems not enough for our purpose. Therefore, if an efficient anonymous broadcast encryption scheme which hides the size of S can be constructed, then we might construct more efficient r-hiding group signature scheme by using the methodology of recent group signature schemes [7, 8], where nonrevocable users prove the decryption ability of a ciphertext of a broadcast encryption scheme.Another (theoretical) drawback of our construction is using random oracles. Actually, a typical group signature construction methodology for standard model construction has been appearing in several papers after the Groth construction [33], that is, using Groth-Sahai proofs [36] and structure-preserving signatures [37]. By applying this methodology, we can expect that an r-hiding revocable group signature scheme in the standard model can be constructed. However, big-size public values problem still remains. So, we need to propose a novel methodology for proposing an r-hiding revocable group signature scheme with small-size public key, even in the random oracle model.Under a XDH-hard elliptic curve with 170-bitp (as in [4, 10]), the size of signature is 7242 bits, where the size of an element of G
1 is 171 bits, the size of an element of G
2 is 513 bits, and the size of the challenge c is 80 bits. Since the size of signature in [4] (resp., in [10]) is 1444 (resp., 1533) bits, there might be space for improvement of the signature size.


## 7. Conclusion

In this paper, for the first time we pointed out that the number of revoked usersr is quite negative information in group signature, and we propose a revocable group signature scheme with the property of hiding r, by applying ABGS. As a matter of first priority, proposing such a group signature scheme with small-size public parameter is an interesting future work. Then, we may be able to apply the standard model construction methodology for constructing an efficient scheme in the standard model.



---

*Source: 983040-2014-06-02.xml*