1556-6013 (c) 2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TIFS.2017.2738601, IEEE
Transactions on Information Forensics and Security
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. , NO. , 2017 3
the user master secret key).
B. Related Work
Attribute-based encryption was first introduced by Sahai and
Waters [30]. Goyal et al. [8] later formalized two complemen-
tary forms of ABE: ciphertext-policy attribute-based encryp-
tion (CP-ABE) and key-policy attribute-based encryption (KP-
ABE). In a CP-ABE system, a decryption key is associated
with a set of attributes and a ciphertext is associated with
an access policy defined over attributes. KP-ABE is reversed
in that a ciphertext is associated with a set of attributes and a
user’s decryption key is associated with an access policy. There
are many ABE (including CP-ABE and KP-ABE) systems that
have been proposed in the literature [4], [11], [34], [12], [25],
[26], aiming at achieving the balance of efficiency, expressive-
ness and security. However, the relatively expensive decryption
cost has been known as one of the crucial drawbacks of the
standard ABE systems. To address the problem, Green et al.
[9] introduced the outsourced decryption notion, and further
presented concrete ABE systems satisfying the notion. Later,
Lai et al. [10] introduced the verifiability of ABE to verify the
correctness of outsourced decryption. Lin et al. [19] revisited
the verifiable outsourced ABE [10] and proposed a more
efficient construction. In addition to outsourcing decryption, Li
et al. [13], [14] and Ma et al. [21] considered to outsource key-
issuing and encryption, respectively. Qin et al. [28] proposed a
hash-function-based approach to construct ABE with verifiable
outsourced decryption. Mao et al. [22] later proposed generic
constructions of CPA-secure and RCCA-secure ABE systems
with verifiable outsourced decryption from CPA-secure ABE
(with outsourced decryption). We also state that there have
been some variants of ABE applications in the literature, such
as [24], [23], [33], [16], [18], [35], [17], [15]. Unfortunately,
the aforementioned works fail to support expressive access
policy, limited time access control, and the decryption audit-
ing, simultaneously.
II. BACKGROUND
A. Notation
Define [l] = {1, 2, ..., l} for l ∈ N. Let PPT be probabilistic
polynomial-time. We let (v
1
, v
2
, ..., v
n
) be a row vector and
(v
1
, v
2
, ..., v
n
)
⊥
be a column vector. By v
i
we denote the i-th
element in a vector ~v. And by M~v we denote the product of
matrix M with vector ~v. Let Z
l×n
p
be the set of matrices of
size l × n with elements in Z
p
. We let GD = (p, G, G
T
, e)
be the groups and the bilinear mapping description where G
and G
T
are two multiplicative cyclic groups of prime order p
and e : G × G → G
T
is a bilinear map.
B. Access Structure and Linear Secret-Sharing Schemes
Definition 1. (Access Structure [2], [27]) : Let S be the
attribute universe. A collection (respectively, monotone col-
lection) A ⊆ 2
S
of non-empty sets of attributes is an access
structure (respectively, monotone access structure) on S. A
collection A ⊆ 2
S
is called monotone if ∀B, C ∈ A : if
B ∈ A and B ⊆ C, then C ∈ A. The sets in A are called
authorized sets, and the sets not in A are called unauthorized
sets.
Here we restrict our attention to monotone access structure.
Definition 2. (Linear Secret-Sharing Schemes (LSSS) [2],
[27]). Let S denote the attribute universe and p denote a
prime. A secret-sharing scheme
Q
with domain of secrets Z
p
realizing access structure on S is called linear (over Z
p
) if
(1) The shares of a secret s ∈ Z
p
for each attribute form
a vector over Z
p
; (2) For each access structure A on S,
there exists a matrix M with l rows and n columns called
the share-generating matrix for
Q
. For i = 1, ..., l, we define
a function ρ labels row i of M with attribute ρ(i) from the
attribute universe S. When we consider the column vector
~v = (s, r
2
, ..., r
n
), where s ∈ Z
p
is the secret to be shared
and r
2
, ..., r
n
∈ Z
p
are randomly chosen. Then M~v ∈ Z
l×1
p
is the vector of l shares of the secret s according to
Q
. The
share (M~v)
j
“belongs” to attribute ρ(j), where j ∈ [l].
As shown in [2], every linear secret-sharing scheme accord-
ing to the above definition enjoys the linear reconstruction
property, defined as follows: suppose that
Q
is an LSSS for
the access structure A, S
∗
∈ A is an authorized set and let
I ⊂ {1, 2, ..., l} be defined as I = {i ∈ [l] ∧ ρ(i) ∈ S
∗
}.
Then, there exist constants {ω
i
∈ Z
p
}
i∈I
such that for any
valid shares {λ
i
= (M~v)
i
}
i∈I
of a secret s according to
Q
,
P
i∈I
ω
i
λ
i
= s.
C. Prime Order Bilinear Groups.
Let G and G
T
be two multiplicative cyclic groups of prime
order p. Let g be a generator of G and e : G × G → G
T
be a
bilinear map. The bilinear map e has the following properties:
(1) Bilinearity: ∀u, v ∈ G and a, b ∈ Z
p
, we have e(u
a
, v
b
) =
e(u, v)
ab
; (2) Non-degeneracy: e(g, g) 6= 1. We say that G is
a bilinear group if the group operations in G and the bilinear
map e : G×G → G
T
can both be computed efficiently. Notice
that the map e(·, ·) is symmetric since e(g
a
, g
b
) = e(g, g)
ab
=
e(g
b
, g
a
) [27].
D. Complexity Assumption.
The decisional q-bilinear Diffie-Hellman inversion (deci-
sional q-BDHI) problem [7] asks, given the tuple ~y =
(g, g
x
, ..., g
x
q
) as input, if one can distinguish e(g, g)
1/x
from
a random value in G
T
.
Formally, an algorithm A has advantage in solving the
above decisional q-BDHI problem if | Pr[A(~y, e(g, g)
1/x
) =
0] − Pr[A(~y, R) = 0]| ≥ , where the probability is over the
coin tosses of A and the choice of x ∈ Z
∗
p
and R ∈ G
T
. The
decisional q-BDHI assumption holds if all PPT algorithms
have at most a negligible advantage in solving the decisional
q-BDHI problem.
III. AUDITABLE σ-TIME OUTSOURCED ABE SYSTEM
A. System Model
We build our system in the key/data encapsulation mecha-
nism (KEM/DEM) setting [31] where an ABE ciphertext (i.e.,
the KEM ciphertext) encrypts a symmetric session key and