We introduce attribute set based signature (ASBS), a new cryptographic primitive which organizes user attributes into a recursive set based structure such that dynamic constraints can be imposed on how those attributes may be combined to satisfy a signing policy. Compared with attribute based signature (ABS), ASBS is more flexible and efficient in managing user attributes and specifying signing policies. We present a practical construction of ASBS and prove its security in the standard model under three subgroup decision related assumptions. Its efficiency is comparable to that of the most efficient ABS scheme.
1. Introduction
 1.1 Motivation
F
lexible and privacypreserving authentication scheme is a fundamental concern in modern cryptography, and attribute based signature (ABS)
[1]
is proposed as a potential solution. However, as observed by Bobba, Khurana and Prabhakaran
[2]
, attribute based systems are far from being flexible in managing user attributes and specifying signing policies, mainly due to the fact that they organizes user attributes into a single set, and a user can use all possible combinations of attributes issued in her attribute keys to satisfy a policy. For example, consider a graduate student who has enrolled in course 525 and she is also the TA for course 101. Here, both ‘
CourseID: 101’ and ‘Role: TA
’ are valid attributes but their combination is not allowed. To prevent such undesirable combination, these attributes have to be appended into two strings of ‘
Role:TA_CourseID:101
’ and ‘
Role:Grad_CourseID:525
’. However, this approach leads to another undesirable consequence where a singleton attribute, say, ‘
Role:TA
’ , can’t be used alone to satisfy a policy, since attribute based systems only checks the equality of strings and can’t extract a single attribute from a string.
To addresses these limitations, Bobba, Khurana and Prabhakaran present ciphertext policy attribute set based encryption (CPASBE)
[2]
as an enhancement to attributebased encryption (ABE). By organizing user attributes into a recursive set based structure, CPASBE allows users to impose dynamic constraints on how those attributes may be combined to satisfy a policy, that is, policies can be specified to restrict decrypting users to use attributes from a single set or allow them to combine attributes from multiple sets. Moreover, CPASBE can efficiently support multiple value assignments and attribute revocation. Due to these powerful features, CPASBE provides an attractive primitive to realize a flexible and finegrained access control in distributed systems.
Since ABS suffers from almost same problems as ABE, a natural question is whether there exists a practical signature analog of CPASBE, to realize a flexible and privacypreserving authentication mechanism.
 1.2 Contribution
In this paper, we introduce attribute set based signature (ASBS) as an enhancement to ABS. Since ASBS also organizes user attributes into a recursive set based structure, it shares same flexibility and other desirable features with CPASBE; that is, ASBS allows dynamic constraints to be imposed on how those attributes may be combined to satisfy a signing policy, and it also can efficiently support compound attributes, multiple value assignments and attribute revocation. We also construct a practical ASBS and prove its security in the standard model under three subgroup decision related assumptions. The efficiency of our construction is comparable to that of the most efficient ABS scheme.
Although our ASBS may be thought as the signature analog of CPASBE, it can’t be straightforwardly converted from Bobba, Khurana and Prabhakaran’s construction, since it can only be proved secure under both generic group model and random oracle model. In addition, perfect privacy is a specific requirement in our ASBS.
Roughly speaking, a signature in our construction is generated by rerandomizing a secret key, and it is verified by first distributing shares of a secret exponent across some verification components and then checking whether the secret can be recovered by the signature. To do so, we need to extend the rerandomization technique from the ABS scheme due to Okamoto and Takashima
[3]
, in order to accommodate our more complicated key structure. We also adapt the dual system encryption of Lewko and Waters to prove the security of our ASBS. Their technique is originally developed to prove the full security of IBE and ABE
[4
,
5]
.
The primary challenge in our construction is how to manage the recursive set based attribute structure. Specifically, our construction should allow a signing policy to specify whether and how a signer can combine attributes from multiple sets within her attribute structure. To tackle the issue, we introduce the
translating keys
and
translating verification components
. Given a signer’s attribute structure, we randomize attribute keys in each attribute set with a unique exponent. Then a translating key is issued for each attribute set, used to translate the exponent into a constant such that attribute keys in this attribute set can be combined with other attribute keys to satisfy a signing policy. However, this combination can only be performed with the help of the corresponding translating verification component, which is generated by the verifier when the signing policy does specify to do so.
 1.3 Related Work
Because ABS is the most related concept to ours ASBS, we briefly review it as follows.
Maji, Prabhakaran and Rosulek
[1]
presented the first ABS in 2008. This primitive allows a signer to convince a verifer that she holds a set of attributes satisfying the signing policy and has endorsed the message. Their scheme supports very expressive signing policies and is almost optimally efficient, but its security is only proven in generic group model, an artificial model which is not solid enough to guarantee the security.
Motivated by the limitation of
[1]
, several ABS schemes
[6

8
,
15

17]
were presented to be secure
in the standard model
, but they can only achieve
selective security
, a weaker notion of unforgeability than
adaptive security
. In this security model, an adversary is required to announce the target signing policy she intends to attack before seeing the public parameters. In addition, signing policies in most of these ABS schemes are limited to threshold predicate, which is less expressive than necessary.
Maji, Prabhakaran and Rosulek
[9]
presented the first ABS which is adaptively secure in the standard model, but it is much less efficient (in terms of signature size) since it employed the GrothSahai NIZK system as building blocks, in order to prove relations between the bits of elements in the group. By using the technology of dual pairing vector spaces, Okamoto and Takashima
[3]
also presented an ABS scheme which is adaptively secure in the standard model, and their scheme is more expressive, i.e., it allows nonmonotone predicates to express signing policies. They further improved it to accommodate the setting of multiauthority
[10]
. However, the efficiencies of their two schemes are several times worse than that of Maji, Prabhakaran and Rosulek’s ABS scheme
[1]
.
As we mentioned earlier, all of these ABS schemes are not flexible enough in managing user attributes and specifying signing policies. So our goal is to present a construction of ASBS that satisfies at the same time the following properties: (1) it is proved adaptively secure in the standard model, (2) it admits general signing policies, and (3) it is efficient in terms of signature size.
The remainder of the paper is organized as follows. In Section 2, we review some definitions and complexity assumptions. Section 3 defines ASBS and formulizes its security. In Section 4, we present our construction of ASBS and prove its security. Finally, Section 5 concludes the whole paper.
2. Preliminaries
 2.1 Bilinear Groups of Composite Order and Complexity Assumptions
Definition 1 (Bilinear group of composite order)
: A (symmetric) bilinear group of composite order is a tuple (
N
,
G
,
G_{T}
,
ê
) where
N
=
p
_{1}
p
_{2}
p
_{3}
for distinct primes
p
_{1}
,
p
_{2}
,
p
_{3}
,
G
,
G_{T}
are cyclic groups of composite order
N
, and
ê
:
G
×
G
→
G_{T}
is an efficiently computable function with the following properties:
(1) ∀
g
,
h
∈
G
, ∀
a
,
b
∈
Z
_{N}
,
ê
(
g^{a}
,
h^{b}
) =
ê
(
g
,
h
)
^{ab}
(2) The element
ê
(
g
,
g
) is a generator of
G_{T}
.
The security of our construction relies on three subgroup decision related assumptions on bilinear groups of composite order. They have been used by Lewko and Waters to prove the security of their IBE
[4]
and ABE
[5]
. To be concise, in the sequel we use
G_{pi}
or
G_{pipj}
to denote the subgroup of order
p_{i}
or
p_{i} p_{j}
in
G
.
Assumption 1
: Given a bilinear group of composite order (
N
,
G
,
G_{T}
,
ê
) and random
g
∈
G_{p}
_{1}
,
X
_{3}
∈
G_{p}
_{3}
, it is hard to distinguish a random element
T
_{1}
∈
G_{p}
_{1}
_{p}
_{2}
from a random element
T
_{2}
∈
G_{p}
_{1}
Assumption 2
: Given a bilinear group of composite order (
N
,
G
,
G_{T}
,
ê
) and random
g,X
_{1}
∈
G_{p}
_{1}
,
X
_{2}
Y
_{2}
∈
G_{p}
_{2}
,
X
_{3}
Y
_{3}
∈
G_{p}
_{3}
, it is hard to distinguish a random element
T
_{1}
∈
G
from a random element
T
_{2}
∈
G_{p}
_{1}
_{p}
_{3}
.
Assumption 3
: Given a bilinear group of composite order (
N
,
G
,
G_{T}
,
ê
) and random
α
,
s
∈
Z
_{N}
,
g
∈
G_{p}
_{1}
,
X
_{2}
,
Y
_{2}
,
Z
_{2}
∈
G_{p}
_{2}
,
X
_{3}
∈
G_{p}
_{3}
, it is hard to distinguish the element
T
_{1}
=
ê
(
g
,
g
)
^{αs}
from a random element
T
_{2}
∈
G_{T}
.
 2.2 Linear Secret Sharing Scheme and Attribute Structure
Definition 2 (Monotone access structure [11])
: Let P= {
P
_{1}
,
P
_{2}
,…,
P_{l}
} be a set of parties (attributes in our setting). A collection Λ⊆2
^{P}
is
monotone
if ∀
B,C
: if
B
∈Λ and
B
⊆
C
then
C
∈Λ. A monotone access structure is a collection Λ of nonempty subsets of P, and elements in Λ are called as authorized sets.
Definition 3 (Linear secret sharing scheme (LSSS) [11])
: A secret sharing scheme over a set of parties P= {
P
_{1}
,
P
_{2}
,…,
P_{l}
} is called
linear
(over
Z
_{N}
) if,
(1) The shares of each party form a vector over
Z
_{N}
, and
(2) There exists a matrix
A
with
l
rows and
n
columns, and a function
ρ
which maps
A_{x}
, the
x
th row of
A
, to the party
ρ
(
x
) for
x
= 1, …,
l
. Given a random vector
v
= (
s
,
v
_{2}
,…,
v_{n}
)∈
Z
^{n}_{N}
,
A⋅v
is the vector of
l
shares of the secret
s
, and
A_{x}⋅v
belongs to party
ρ
(
x
).
Using standard techniques
[12]
, any monotonic boolean formulas can be converted into an LSSS matrix
A
to represent its access structure Λ. For each authorized set
B
∈Λ, there exists a reconstruction vector
ω
= (
ω
_{1}
,
ω
_{2}
,…,
ω_{l}
)∈
Z
^{l}_{N}
, where
ω_{x}
= 0 if
ρ
(
x
)∉
B
, such that
ω
⋅
A
= (1, 0, …, 0) and Σ
_{ρ(x)∉ B}
ω_{x}A_{x}⋅v=s
. On the contrary, no reconstruction vector exists if
B
∉Λ.
Definition 4 (Attribute structure):
An attribute structure in ASBS is a recursive set where each element of the set is either a set itself (i.e. an attribute structure) or an attribute.
The
depth
of an attribute structure is defined as the number of its recursive levels. Like the CPASBE
[2]
, our construction mainly focuses on the attribute structure with depth 2, where elements at depth 1 can either be attributes or sets but elements at depth 2 can only be attributes, belonging to some sets at depth 1. For each set at depth 1, an
index
, numbered from 1, is assigned to identify it. For the sake of consistency, attributes at depth 1 can be thought to form a set with index of 0. We also abuse the notion of index to an individual attribute, which is defined as the combination of the index of the set it belongs to and its sequence number in the set.
In our construction, a signing policy is expressed by a monotonic boolean formula and a signer’s attributes are described by an attribute structure. If a signer’s attribute structure satisfies the signing policy, the signing policy is realized by the corresponding LSSS matrix and the reconstruction vector is used to generate a signature.
3. Definitions
 3.1 Attribute Set based Signature
Definition 5 (Attribute Set based Signature)
: An attribute set based signature ASBS = {Setup, KGen, Sign, Verify} is a tuple of polynomial time algorithms.
–Setup
(1
^{λ}
) → (
PK
,
MSK
) . On input security parameter 1
^{λ}
, the setup algorithm outputs the public parameters
PK
and a master secret key
MSK
for the attribute authority.
–KGen
(
PK
,
MSK
,
AS
) →
SK
. Given (
PK
,
MSK
) and an user’s attribute structure
AS
, the key generation algorithm outputs a secret key
SK
for the user.
–Sign
(
PK
,
SK
,
M
, (
A
,
ρ
)) →
σ
. The signing algorithm takes in
PK
, a secret key
SK
, a message
M
and a LSSS access structure (
A
,
ρ
) over the universe of attributes. If the attribute structure in SK satisfies the LSSS access structure, it outputs a signature
σ
.
–Verify
(
PK
,
M
, (
A
,
ρ
),
σ
) → 1/0. Given
PK
, a message
M
, a LSSS access structure (
A
,
ρ
) and a signature
σ
, the verification algorithm outputs 1 if
σ
is a valid signature on
M
or 0 otherwise.
 3.2 Security model for ASBS
Perfect privacy and unforgeability are two security properties that ASBS should satisfy. We give their formal definitions as follows.
Definition 6 (Perfect Privacy)
: An ASBS scheme is perfect privacy, if, for all (
PK
,
MSK
) ← Setup(1
^{λ}
), all messages
M
, all attribute structures
AS
^{(1)}
and
AS
^{(2)}
, all secret keys
SK
^{(1)}
← KGen(
PK
,
MSK
,
AS
^{(1)}
) and
SK
^{(2)}
← KGen(
PK
,
MSK
,
AS
^{(2)}
), all access structures (
A
,
ρ
) such that both
AS
^{(1)}
and
AS
^{(2)}
satisfy (
A
,
ρ
), the distributions of
σ
^{(1)}
= Sign(
PK
,
SK
^{(1)}
,
M
, (
A
,
ρ
)) and
σ
^{(2)}
= Sign(
PK
,
SK
^{(2)}
,
M
, (
A
,
ρ
)) are equal.
Definition 7 (Existential Unforgeability)
: For an adversary
A
, we define GameAdv
_{A}
to be its success probability in the following game. An ASBS scheme is existentially unforgeable if GameAdv
_{A}
is negligible for any polynomialtime adversary
A
.
–
Setup
Run (
PK
,
MSK
) ← Setup(1
^{λ}
) and give
PK
to
A
.
–
Queries
A
can adaptively makes a polynomial number of
q
queries of the following two types:
(1) Key Queries
A
can request a secret key for any attribute structure
AS
.
(2) Signing Queries
A
can request a signature for any message, attribute structure
AS
and access structure (
A
,
ρ
), with the restriction that the attribute structure
AS
should satisfy the access structure (
A
,
ρ
).
–Forgery
A
outputs a signature
σ
* on a message
M
* and an access structure (
A
*,
ρ
*).
A
succeeds in the game if
(1) Verify(
PK
,
M
*, (
A
*,
ρ
*),
σ
*) = 1.
(2)
A
has never queried a secret key for an attribute structure
AS
* satisfying (
A
*,
ρ
*).
(3)
A
has never queried a signature on message
M
* and (
A
*,
ρ
*).
4. OUR ASBS
 4.1 Construction
We construct our ASBS in a bilinear group of composite order (
N
,
G
,
G_{T}
,
ê
), where keys and signatures occur in the subgroups
G
_{p1p3}
, while the subgroup
G
_{p2}
is used as the semifunctional space to prove the security of our construction.
–Setup
(1
^{λ}
) The setup algorithm performs the following steps:
(1) Generate a bilinear group (
N
,
G
,
G_{T}
,
ê
) of composite order
N
=
p
_{1}
p
_{2}
p
_{3}
.
(2) Pick random value
α
,
a
∈
Z
_{N}
,
g
∈
G
_{p1}
,
X
_{3}
∈
G
_{p3}
, and choose
u
_{0}
,
u
_{1}
,…,
u_{η}
∈
G
_{p1}
as Water’s hash function
[13]
, where
η
is the length of a message. To be concise, we define
for a message
M
= (
μ
_{1}
,
μ
_{2}
,…,
μ_{η}
).
(3) Let the universe attribute structure be
AS
= {
AS
_{0}
,
AS
_{1}
, …,
AS_{m}
}. For each attribute set
AS_{i}
= {
at_{i}
_{,1}
, …, ,
at_{i,ni}
}, 1≤
i
≤
m
, pick a unique random exponent
b_{i}
∈
Z
_{N}
. For the
j
th attribute appearing in set
AS_{i}
, 0≤
i
≤
m
, 1≤
j
≤
n_{i}
, pick a unique random exponent
h_{ij}
∈
Z
_{N}
.
The algorithm outputs public parameters and the master secret key as:

PK= (N,G,GT,ê,g,ga,ê(g,g)α,u0,u1,…,uη,gbi∀i,ga/bi∀i,Hij=∀i∀j)

MSK= (α,bi∀i,X3)
–KGen
(
PK
,
MSK
,
AS
) The key generation algorithm chooses a unique random
t_{i}
∈
Z
_{N}
for each set
AS_{i}
∈
AS
, 0≤
i
≤
m
. It also chooses random elements
R
_{0}
,R_{i},R'_{i},R_{ij}
∈
G_{p}
_{3}
and outputs the secret key as:

K=gαgat0R0,

Ki=gtiRi,Kij=(Hij)tiRij, 0≤i≤m, 1≤j≤ni

Li=ga(t0+ti)/biR'i, 1≤i≤m
–Sign
(
PK
,
SK
,
M
, (
A
,
ρ
)) Let
A
be an
l
×
n
matrix and
A_{x}
be the
x
th row of
A
. The function
ρ
maps each row number
x
to an attribute’s index
ρ
(
x
), while the function
φ
maps
x
to the index of the set the attribute
ρ
(
x
) belongs to. The algorithm proceeds as follows:
(1) Choose random
t'
_{0}
t'_{ϕ}
_{(x)}
∈
Z
_{N}
for 1≤
x
≤
l
, and blind the secret key
SK
as:

K' =K(ga)t'0= (gαga(t0+‘t0)R0,

K'ϕ(x)=Kϕ(x)gt'ϕ(x)=gtϕ(x)+t'ϕ(x)Rϕ(x),

K'ρ(x)=Kρ(x)(Hρ(x))t'ϕ(x)= (Hρ(x))tϕ(x)+t'ϕ(x)Rρ(x)

L'ϕ(x)=Lϕ(x)(ga/bϕ(x))t'0t'ϕ(x)=ga(t0+t'0+tϕ(x)+t'ϕ(x))/bϕ(x)R'ϕ(x)
(2) Find a reconstruction vector
ω
= (
ω
_{1}
,
ω
_{2}
,…,
ω_{l}
)∈
Z
^{l}_{N}
and two random vectors
β
_{1}
= (
β
_{11}
,
β
_{12}
,…,
β
_{1l}
),
β
_{2}
= (
β
_{21}
,
β
_{22}
,…,
β
_{2l}
), such that
β
_{1}
⋅
A
=
β
_{2}
⋅
A
= (0, 0, …, 0). We discuss the existence of
β
_{1}
,
β
_{2}
in the proof of Theorem 1. Then compute:

σa=K'∏lx=1((K'ρ(x))ωx, (Hρ(x))β1x)F(M)r,σb=gr

σ1,x= (K'ϕ(x))ωxgβ1x,σ2,x= (L'ϕ(x))ωx(ga/bϕ(x))β2x, 1≤x≤l
The algorithm outputs the signature as
σ
= (
σ_{a}
,
σ_{b}
, (
σ
_{1,x}
,
σ
_{2,x}
)
_{x}
_{=1,...,l}
).
–Verify
(
PK
,
M
, (
A
,
ρ
),
σ
) Given a signature
σ
on a message
M
, the algorithm first chooses a random vector
v
= (
s
,
v
_{2}
, ...,
v_{n}
)∈
Z
^{n}_{N}
and generates a group of verification components as follow:

C=gs,Cx=gaAxv(Hρ(x))−s,Ex=gbϕ(x)Axv, 1 ≤x≤l
Then the algorithm outputs 1 if the following verification equation holds
We name the component
L_{i}
in a secret key and
E_{x}
in the verification components as the
translating key
and the
translating verification component
, respectively. During verification, only
simultaneous
use of both a translating key and the corresponding translating verification component can translate the exponents
t_{i}
in
K_{i}
and
K_{ij}
into the constant
t
_{0}
, and the verification succeeds only when all
t_{i}
are translated into
t
_{0}
.
 4.2 Efficiency
To show the efficiency and security of our ASBS, we compare it with existing ABS schemes which support general signing policies in
Table 1
, where
l
and
n
are the size of the underlying LSSS matrix, and
λ
is the security parameter (e.g., 128). The signature size and complexity are measured in terms of the number of group elements and the number of paring operations to verify a signature, respectively. In addition, since there are two constructions are presented in
[9]
, the more efficient construction based on Waters signature is used to measure the signature size, and the underlying GrothSahai NIZK system is instantiated under DLIN Assumption.
Comparison with ABS schemes supporting general signing policies
Comparison with ABS schemes supporting general signing policies
Although some ABS schemes, such as
[6

8
,
15

17]
, have short or even constant signature size, we need not compare with them in
Table 1
, since they only admit threshold signing policies, which can’t provide enough flexibility than necessary. Although some of them, such as
[17]
, can be extended to admit general signing policies, the signature size, as the authors of
[17]
denoted, will drastically increase.
Since the ABS scheme due to Maji, Prabhakaran and Rosulek
[1]
has the best efficiency among all ABS schemes, we consider it as a benchmark. Compared with this ABS scheme, our ASBS has almost same signature size but less complexity.
 4.3 Perfect Privacy
Theorem 1.
Our construction of ASBS can achieve perfect privacy.
Proof.
Given a LSSS access structure (
A
,
ρ
), if rank(
A
) <
l
, there obviously exist polynomial numbers of vectors
β
such that
β
⋅
A
= (0, 0, …, 0). If rank(
A
) =
l
, there exists only one
β
= (0, 0, …, 0) such that
β
⋅
A
= (0, 0, …, 0), but the signing policy is limited to a (
n
,
n
)threshold predicate, which means there is no attribute privacy at all. So we only need to consider the case of rank(
A
) <
l
.
To show that two signatures of
σ
^{(1)}
=
Sign
(
PK
,
SK
^{(1)}
,
M
, (
A
,
ρ
)) and
σ
^{(2)}
=
Sign
(
PK
,
SK
^{(2)}
,
M
, (
A
,
ρ
)) have equal distributions, it suffices to prove that, by choosing proper random
t'_{i}
,
r
and
β
_{1}
,
β
_{2}
, same signatures can be generated from different keys
SK
^{(1)}
and
SK
^{(2)}
. To do so, we choose
r
^{(1)}
=
r
^{(2)}
,
t
_{0}
^{(1)}
+
t
'
_{0}
^{(1)}
=
t
_{0}
=
t
_{0}
^{(2)}
+
t
'
_{0}
^{(2)}
and
for 1 ≤
x
≤
l
. Given
we also choose
β
_{1}
^{(2)}
and
β
_{2}
^{(2)}
by setting
It is easy to check that
β
_{1}
^{(2)}
⋅
A
=
β
_{2}
^{(2)}
⋅
A
= (0, 0, …, 0) and
σ
^{(1)}
=
σ
^{(2)}
.
 4.4 Existential Unforgeability
We adapt the dual system encryption technique
[4
,
5]
to prove the unforgeability of our construction. Specifically, we define two types of semifunctional signatures and an additional semifunctional verification algorithm
VerifySF
. We also define a sequence of games where the first game is the real unforgeable game and in the last game the success probability of any polynomialtime adversary is negligible. Then, by standard hybrid arguments, we prove several lemmas to show that the adversary's success probabilities are indistinguishable among these games. The unforgeability of our construction follows from these lemmas.
–Semifunctional signatures of type 1
Given a normal signature
a semifunctional signature of type 1 is generated by choosing a generator
g
_{2}
∈
G
_{p2}
, random exponents
d
,
e
∈
Z
_{N}
and
f_{x}
∈
Z
_{N}
, and outputting
–Semifunctional signatures of type 2
Given a normal signature
a semifunctional signature of type 2 is generated as
–VerifySF
This algorithm is same as
Verify
except that it chooses a random exponent
c
∈
Z
_{N}
, two random vectors
u,w
∈
Z
^{n}_{N}
, random values
γ_{x}
∈
Z
_{N}
, for each
x
, and random values
z_{ρ}
_{(x)}
∈
Z
_{N}
for each attribute
ρ
(
x
), and generates semifunctional verification components as:
–Game_{real}
: The real security game defined in Section 3.
–Game_{0}
: The real security game with the exception that the algorithm
VerifySF
is used to verify a forged signature.
–
–Game_{k}_{,1}
, 1 ≤
k
≤
q
: Same as Game
_{0}
except that the first
k
− 1 signatures are semifunctional signatures of type 2 and the
k
th key is a semifunctional signature of type 1.
–Game_{k}_{,2}
, 1 ≤
k
≤
q
: Same as Game
_{k}
_{,1}
except that the
k
th signature is also a semifunctional signature of type 2.
–Game_{final}
: In this game, all signatures are semifunctional signatures of type 2, and the forged signature is verified by
VerifySF
.
Lemma 1.
Suppose there exists an adversary
A
such that Game
_{real}
Adv
_{A}
− Game
_{0}
Adv
_{A}
=
ε
, then we can build a simulator
S
that has advantage
ε
in breaking the Assumption 1.
Proof.
The simulator
S
begins by taking in an instance (
g
,
X
_{3}
,
T
) of Assumption 1, where
T
=
g^{s}g^{c}
_{2}
or
g^{s}
for unknown
s,c
∈
Z
_{N}
. It simulates Game
_{real}
or Game
_{0}
as follows:
–Setup
S
generates
PK
and
MSK
by running the algorithm
Setup
.
–Queries
Since
S
knows the
MSK
, it can run algorithms
KGen
and
Sign
to outputs any secret keys and signatures.
–Forgery
Upon receiving a forged signature,
S
chooses a random vector
v
' = (1,
v
'
_{2}
, ...,
v'_{n}
)∈
Z
^{n}_{N}
, and generates verification components as follows:

C=T,Cx=TaAxv'T−sρ(x),Ex=Tbφ(x)Axv'
If
T
=
g^{s}
, we have
C
=
g^{s}
,
E_{x}
=
g
^{bφ(x)Axsv'}
. They are properly distributed normal verification components with the implicit setting of
v
=
sv
'.
If
T
=
g^{s}g^{c}
_{2}
, we have
C
=
g^{s}g^{c}
_{2}
,
They are wellformed semifunctional verification components if we further set
u
=
cav
',
z_{ρ}
_{(x)}
=
cs_{ρ}
_{(x)}
,
cb_{ϕ}
_{(x)}
=
γ_{x}
and
w
=
v
'. Although some values in
G
_{p1}
parts of the verification components, such as
a
,
v
',
s_{ρ}
_{(x)}
,
b_{φ}
_{(x)}
, are reused in
G
_{p2}
parts, it is still properly distributed, since these values modulo
p
_{2}
are uncorrelated from their values modulo
p
_{1}
due to the Chinese Remainder Theorem. Hence
S
can use the output of
A
to break the Assumption 1 with advantage
ε
.
Lemma 2.
Suppose there exists an adversary
A
such that Game
_{k−1,2}
Adv
_{A}
− Game
_{k,1}
Adv
_{A}
=
ε
, then we can build a simulator
S
□ that has advantage
ε
in breaking the Assumption 2.
Proof.
Given an instance (
X
_{1}
X
_{2}
,
X
_{3}
,
Y
_{2}
Y
_{3}
,
T
) of Assumption 2, where
T
=
g^{t}g^{e}
_{2}
R
or
g^{t}R
, for some unknown
t
,
e
∈
eZ
_{N}
and
R
∈
G_{p}
_{3}
,
S
simulates Game
_{k−1,2}
or Game
_{k,1}
as follows.
–Setup
S
generates
PK
and
MSK
by running the algorithm
Setup
.
–Queries
Since
S
knows the
MSK
, it can generate any secret keys by running the algorithm
KGen
.
S
can also generate normal signtures for requests >
k
by running the algorithm
Sign
.
To generate the first
k
− 1 semifunctional signatures,
S
first generates a normal signature
σ'
= (
σ'_{a}
,
σ'_{b}
, (
σ'
_{1,x}
,
σ'
_{2,x}
)
_{x=1}
,...,
l
). Then it choose random
d'
∈
eZ
_{N}
and outputs the signature as
σ
= (
σ'_{a}
(
Y
_{2}
Y
_{3}
)
^{d'}
σ'_{b}
, (
σ'
_{1,x}
,
σ'
_{2,x}
)
_{x=1}
,...,
l
). It is a properly distributed semifunctional signature of type 2 if we implicitly set
To generate the
k
th signature,
S
chooses random
ξ_{ϕ}
_{(x)}
∈
Z
_{N}
,
R'
_{0}
,
R'_{ϕ}
_{(x)}
,
R"_{ϕ}
_{(x)}
,
R'_{ρ}
_{(x)}
∈
G
_{p3}
and
r
∈
Z
_{N}
. It also chooses a reconstruction vector
ω
and two random vectors
β
_{1}
,
β
_{2}
such that
β
_{1}
⋅
A
=
β
_{2}
⋅
A
= (0, 0, …, 0), and outputs:
If
T
=
g^{t}g^{e}
_{2}
R
, we have a properly distributed semifunctional signature of type 1 as follows, where we implicitly set
t
_{0}
=
t
,
t_{ϕ}
_{(x)}
=
t
+
ξ_{ϕ}
_{(x)}
,
f_{x}
= 2
ae
/
b_{ϕ}
_{(x)}
,
R
_{0}
=
R'
_{0}
R^{a}
,
R_{ρ}
_{(x)}
=
R^{sρ}
^{(x)}
R'_{ρ}
_{(x)}
,
R_{ϕ}
_{(x)}
=
RR'_{ρ}
_{(x)}
,
R'_{ϕ}
_{(x)}
=
R
^{2}
R''_{ϕ}
_{(x)}
.
If
T
=
g^{t}R
, we have a properly distributed normal signature with the implicit setting of
t
_{0}
=
t
,
t_{ϕ}
_{(x)}
=
t
+
ξ_{ϕ}
_{(x)}
.
It can be checked that the
k
th signature, in both cases of
T
=
g^{t}g^{e}
_{2}
R
or
T
=
g^{t}R
, can be successfully verified by the algorithm
VerifySF
, so neither
A
□nor
S
can distinguish two games by verifying the
k
th signature.
–Forgery
To simulate the algorithm
VerifySF
,
S
implicitly sets
g^{s}
=
X
_{1}
,
g^{c}
_{2}
=
X
_{2}
and obtains
ê
(
g
,
g
)
^{αs}
by computing
ê
(
g
,
X
_{1}
X
_{2}
)
^{α}
. It also chooses a random vector
u'
= (
a
,
u'
_{2}
,...,
u'_{n}
) and generates verification components as follows:
We can check that
thus it is a properly distributed verification components with the implicit setting of
v
=
sa
^{−1}
u
',
u
=
cu
',
z_{ρ}
_{(x)}
=
cs_{ρ}
_{(x)}
,
γ_{x}
=
cb_{ρ}
_{(x)}
and
w
=
a
^{−1}
u
'.
To sum up, depend on whether
T
∈
G
or
T
∈
G
_{p1p3}
,
S
can properly simulate Game
_{k−1,2}
or Game
_{k,1}
, thus can use the output of
A
to break the Assumption 2 with advantage
ε
.
Lemma 3.
Suppose there exists an adversary
A
such that Game
_{k,1}
Advk
_{A}
− Game
_{k,2}
Advk
_{A}
=
ε
, then we can build a simulator
S
that has advantage
ε
in breaking the Assumption 2.
Proof.
S
simulates the games in almost the same way as it does in the lemma 2, except that it chooses a random exponent
h
∈
Z
_{N}
and generates the
k
th signature as:
Depend on
T
∈
G
or
T
∈
G
_{p1p3}
, it is a properly distributed semifunctional signature of type 2 or normal signature, and in both cases it can’t be verified by the algorithm
VerifySF
due to the extra term (
Y
_{2}
Y
_{3}
)
^{h}
. Thus
S
can also use the output of
A
to break the Assumption 2 with advantage
ε
.
Lemma 4.
Suppose there exists an adversary
A
such that Game
_{q,2}
Advk
_{A}
− Game
_{final}
Advk
_{A}
=
ε
, then we can build a simulator
S
that has advantage
ε
in breaking the Assumption 3.
Proof.
Given an instance (
g^{α}X
_{2}
,
X
_{2}
,
g^{s}Y
_{3}
,
Z
_{2}
,
T
) of Assumption 3, where
T
=
ê
(
g
,
g
)
^{αs}
or
ê
(
g
,
g
)
^{r}
for unknown
α
,
s
,
r
∈
Z
_{N}
,
S
simulates Game
_{q,2}
or Game
_{final}
as follows.
–Setup
S
chooses random exponents
a
,
b_{i}
,
s_{ij}
,
u
_{0}
,
u
_{1}
,…,
u_{η}
∈
Z
_{N}
, and sets
PK
as:

PK= (N,G,GT,ê,g,ga,ê(g,gαX2),u0,u1,…,uη,gbi∀i,ga/bi∀i,Hij=∀i∀j)
–Queries
S
generates a secret key as follows:

K=gαX2gat0(Z2)t0R0

Ki=gtiRi,Kij= (Hij)tiRij, 0 ≤i≤m, 1≤j≤ni

Li=ga(t0+ti)/biR'i, 1≤j≤m
Given such a secret key,
S
generates a signature by running the algorithm
Sign
. The resulting signature is a properly distributed semifunctional signature of type 2 with the implicit setting of
g^{d}
_{2}
=
X
_{2}
(
Z
_{2}
)
^{t0}
.
–Forgery
To simulate the algorithm
VerifySF
,
S
chooses a random vector
u
' = (
a
,
u
'
_{2}
,...,
u'_{n}
), and outputs verification components as follows:
It is a properly distributed semifunctional verification components, with the implicitly setting of
g^{c}
_{2}
=
Y
_{2}
,
v
=
sa
^{−1}
u
',
u
=
cu
',
z_{ρ}
_{(x)}
=
cs_{ρ}
_{(x)}
,
γ_{x}
=
cb_{ρ}
_{(x)}
and
w
=
a
^{−1}
u
'. Then
S
verifies the signature by the verification equation of
ê
(
σ_{a}
,
C
) =
Tê
(
F
(
M
)
s
,
σ_{b}
)∏
^{l}_{x}
_{=1}
ê
(
E_{x}
,
σ
_{2x}
)/
ê
(
C_{x}
,
σ
_{1x}
).
If
T
=
ê
(
g
,
g
)
^{αs}
, it is the original verification equation (1) used in
VerifySF
. Otherwise, due to the random
T
in the verification equation,
S
rejects the forged signature with overwhelming probability. Thus
S
can use the output of
A
to break the Assumption 3 with advantage
ε
.
Theorem 2 (Unforgeability).
Our construction of ASBS is existential unforgeable under Assumptions 1, 2 and 3.
Proof.
It follows from lemma 1 to 4, and the fact that the success probability of any polynomialtime adversary in Game
_{final}
is negligible.
5. Conclusion
In this paper, we introduce attribute set based signature as an enhancement to attribute based signature. ASBS organizes user attributes into a recursive set based structure such that dynamic constraints can be imposed on how those attributes may be combined to satisfy a signing policy. Thus it is more flexible and efficient in managing user attributes and specifying signing policies. We present a practical construction of ASBS and prove its security in the standard model under three subgroup decision related assumptions. Its efficiency is comparable to that of the most efficient ABS scheme.
Our construction relies on a bilinear group of composite order. This requires large group orders to guarantee security. So an interesting direction for future research is to convert it to prime order groups, probably using the technique from
[14]
.
BIO
Baohong Li, Lecturer in School of Electronics and Information Engineering, Xi’an Jiaotong University (XJTU), China. He received his M.S. degree and Ph.D. degree in computer science from XJTU in 2002 and 2006. His current research interests include Network Security and Cryptography.
Yinliang Zhao, Professor in School of Electronics and Information Engineering, Xi’an Jiaotong University (XJTU), China. He received his M.S. degree and Ph.D. degree in computer science from XJTU in 1988 and 1995. His research interests include Network Security, Parallel Computing threadlevel parallelism and Compiler Optimization.
Hongping Zhao, She received her M.S. degree and Ph.D. degree from the Fourth Military Medical University in 2003 and 2006. She is currently a chief engineer in 518th Hosp. of PLA. Her research interests include network security and Management Information System.
Maji H. K.
,
Prabhakaran M.
,
Rosulek M.
2008
“Attributebased signatures: achieving attributeprivacy and collusionresistance,”
IACR Cryptology ePrint Archive
328 
Bobba R.
,
Khurana H.
,
Prabhakaran M.
“Attributesets: a practically motivated enhancement to attributebased encryption,”
in Proc. of 14th European Symposium on Research in Computer Security
2009
587 
604
Okamoto T.
,
Takashima K.
“Efficient attributebased signatures for nonmonotone predicates in the standard model,”
in Proc. of the 14th Int. Conf. on Public Key Cryptography
2011
35 
52
Lewko A.
,
Waters B.
“New techniques for dual system encryption and fully secure HIBE with short ciphertexts,”
in Proc. of 7th Theory of Cryptography Conference
2010
455 
479
Lewko A.
,
Okamoto T.
,
Sahai A.
“Fully secure functional encryption: attributebased encryption and (hierarchical) inner product encryption,”
in Proc. of Advances in Cryptology  EUROCRYPT 2010
2010
62 
91
Li J.
,
Au M. H.
,
Susilo W.
“Attributebased signature and its application,”
in Proc. of 5th ACM Symposium on Information, Computer and Communications Security
2010
60 
69
Shahandashti S. F.
,
SafaviNaini R.
“Threshold attributebased signatures and their application to anonymous credential systems,”
in Proc. of Progress in Cryptology – AFRICACRYPT 2009
2009
198 
216
Guo S.
,
Zeng Y.
“Attributebased signature scheme,”
in Proc. of International Conference on Information Security and Assurancec
2008
509 
511
Maji H. K.
,
Prabhakaran M.
,
Rosulek M.
“Attributebased signatures,”
in Proc. of Cryptographers’Track at the RSA Conference
2011
376 
392
Okamoto T.
,
Takashima K.
“Decentralized attributebased signatures,”
in Proc. of PublicKey Cryptography
2013
125 
142
Beimel A.
,
PhD thesis
1996
“Secure schemes for secret sharing and key distribution,”
Isral institute of technology
PhD thesis
Karchmer M.
,
Karchmer A. W.
“On span programs,”
in Proc. of the 8th IEEE Structure in Complexity Theory Conference
1993
102 
111
Waters B.
“Efficient identitybased encryption without random oracle,”
in Proc. of Advances in Cryptology  EUROCRYPT 2005
2005
114 
127
Lewko A.
“Tools for simulating features of composite order bilinear groups in the prime order setting,”
in Proc. of Advances in Cryptology  EUROCRYPT 2012
2012
318 
335
Herranz J.
,
Laguillaumie F.
,
Libert B.
,
Ràfols C.
“Short attributebased signature for threshold predicates,”
in Proc. of Int. Conf. of the cryptographers’ Track at the RSA
2012
51 
67
Chen C.
,
Chen J.
,
Lim H. W.
“Fully secure attributebased systems with short ciphertexts/signatures and threshold access structures,”
in Proc. of Int. Conf. of the cryptographers’ Track at the RSA
2013
50 
67
Escala A.
,
Herranz J.
,
Morillo P.
“Revocable attributebased signatures with adaptive security in the standard model,”
in Proc. of Progress in Cryptology  AFRICACRYPT 2011
2011
224 
241