# Efficient Attribute-Based Secure Data Sharing with Hidden Policies and Traceability in Mobile Health Networks

Authors: Changhee Hahn; Hyunsoo Kwon; Junbeom Hur
Journal: Mobile Information Systems
 (2016)

---

## Abstract

Mobile health (also written as mHealth) provisions the practice of public health supported by mobile devices. mHealth systems let patients and healthcare providers collect and share sensitive information, such as electronic and personal health records (EHRs) at any time, allowing more rapid convergence to optimal treatment. Key to achieving this is securely sharing data by providing enhanced access control and reliability. Typically, such sharing follows policies that depend on patient and physician preferences defined by a set of attributes. In mHealth systems, not only the data but also the policies for sharing it may be sensitive since they directly contain sensitive information which can reveal the underlying data protected by the policy. Also, since the policies usually incur linearly increasing communication costs, mHealth is inapplicable to resource-constrained environments. Lastly, access privileges may be publicly known to users, so a malicious user could illegally share his access privileges without the risk of being traced. In this paper, we propose an efficient attribute-based secure data sharing scheme in mHealth. The proposed scheme guarantees a hidden policy, constant-sized ciphertexts, and traces, with security analyses. The computation cost to the user is reduced by delegating approximately 50% of the decryption operations to the more powerful storage systems.


---

## Body

## 1. Introduction

mHealth is an abbreviation for mobile health, which can encompass a wide range of healthcare technologies such as mobile computing, medical sensors, and communication technologies [1]. Rapid growth in wireless communications, availability and miniaturization of mobile devices, and computing resources in parallel with mobile and wearable systems can boost the wide adoption of mHealth. Such developments can greatly impact on and reshape the processes of existing healthcare services. For instance, semiconductor-implanted smart intelligent sensors will allow drugs to be delivered in real time to a personal server when they sense a patient who needs a dose of drugs. Personal servers, such as mobile devices, supply global connectivity to the storage center, which can thereby serve clinical healthcare from a distance [2]. The storage center holds the information that forms the electronic health record (EHR), a digital version of a patient’s paper chart. Physicians intermittently upload diagnostic reports based on their observations of the EHRs stored in the storage center. Figure 1 shows an example of an mHealth monitoring and data transfer system. Reportedly, a growing number of healthcare-specific mobile applications are available, and it has been estimated that about 500 million patients around the globe will be in the reach of such apps as of 2015 [3].Figure 1
Typical system architecture of mHealth monitoring systems.EHRs contain sensitive information such as patients’ medical history, diagnoses, immunization dates, allergies, and medications, which are bound to the real identities of patients. That is, whoever can freely access the storage center is able to learn both the identity and clinical information of a specific patient, which clearly threatens the patient’s privacy. Thus, privacy concerns are arguably a major issue, and related requirements are enacted nationwide. For example, in the United States compliance to HIPPA (Health Information Technology for Economic and Clinical Health Act) encourages healthcare providers to not only adopt EHRs but also keep them confidential [4]. This clearly indicates that EHRs must be kept under strict conditions and be accessible only by the authorized user.Unfortunately, standard encryption schemes are not suitable for mHealth systems for the following reasons [5].(i)
Absence of Proper Access Control. Well-known encryption schemes, such as AES, guarantee the confidentiality of data if security parameters are well-chosen. However, such schemes are not designed to support fine-grained access control.
(ii)
Expensive Key Management. Public key encryption schemes do not support one-to-many relationships between the ciphertext and decryption key, necessitating the burdensome distribution and management of public keys.Since healthcare delivery is a decentralized process taking place across many institutional boundaries, standard approaches to securing health records include role-based access control because the flexible assignment of permissions to a wide range of user is possible only with fine-grained access control. At the same time, the confidentiality of EHRs must be maintained without hindering clinical care by denying legitimate access requests of authorized users, such as doctors, nurses, lab technicians, researchers, and receptionists [6, 7]. Thus, a variety of policy-based encryption schemes have been proposed to share data securely and provide reliable access control [8–11]. These schemes are promising in that the accessibility of shared data is dependent on the user’s capacity to satisfy a given policy. Furthermore, encryptors do not require a priori knowledge of the recipients, such as identities or certificates. Specifically, ciphertext policy attribute-based encryption (CP-ABE) allows the construction of policies by utilizing attributes as public keys, thereby protecting shared data against unauthorized users [12–16]. As access to EHRs varies across the space of uneven distributions of healthcare providers and consumers and among population groups with different socioeconomic and demographic characteristics [17], CP-ABE is a convincing alternative to the conventional cryptographic primitive for mHealth. CP-ABE can provide fine-grained and flexible access control to the shared data in mHealth systems.It is notable that not only the data, but also the policies for sharing that data are sensitive. Typically, the access policies may reveal sensitive information, such as the underlying data, the identity of a patient, or symptoms indicating what diseases a patient is suffering from. To some extent, patients are reluctant to expose such private information, preferring instead to keep their privacy intact through securing both the EHRs and their access policies. Although CP-ABE provides a desirable access policy, it has one drawback: the access policies attached to ciphertexts are public. From these access policies, unauthorized users can learn information about the underlying data itself. This weakness is known as the policy privacy problem.To overcome the policy privacy problem, several CP-ABE schemes with hidden access policies were proposed [9, 18]. In these schemes, the encryptor-chosen access policies are associated with each ciphertext in a way hidden such that even an authorized user learns no information about the underlying policy other than that he is authorized to decrypt. Although these schemes feature hidden policies, they suffer from being inefficient; that is, the ciphertext size is linear with respect to the number of attributes in the access policy.To limit ciphertext size, Zhou et al. introduced a CP-ABE scheme which provides both a hidden access policy and a constant-sized ciphertext [19]. However, their scheme lacks user traceability. In general, most CP-ABE schemes supporting constant-sized ciphertext or hidden access policies cannot trace malicious users who illegally share their decryption keys. Specifically, the secret keys of policy-based encryption consist of sharable attributes so that the decryption keys have no uniquely identifiable information. Thus, if a malicious user leaks his decryption key to others, then there is no clear evidence indicating that the key belongs to him. Although Li et al. proposed a CP-ABE scheme featuring a hidden access policy and traceability [20], it lacks constant-sized ciphertext, resulting in increased communication and storage costs.Contribution. In this paper, we propose an efficient attribute-based secure data sharing scheme for mHealth with hidden policies and traceability. The proposed scheme enforces hidden access policies with wildcards and supports constant-sized ciphertext, regardless of the number of attributes. Also, we embed a uniquely identifiable point into each decryption key in order to prevent the user from intentionally distributing the decryption key to others, thereby achieving traceability. Additionally, the proposed scheme allows users to outsource part of the decryption process to the more powerful storage center to minimize computation cost at the user side. Our performance results show that the storage center computes almost 50% of the decryption process on behalf of users. To the best of our knowledge, this is the first construction that achieves all these functionalities simultaneously.Organization. The rest of this paper is organized as follows. We begin with a discussion of related work in Section 2. In Section 3, we describe the cryptographic background and define a general CP-ABE with a hidden policy, constant-sized ciphertext, and traceability. Section 4 describes the mHealth architecture and security model. In Section 5, we present the construction of the proposed scheme in detail, followed by a performance analysis in Section 6. We analyze its security in Section 7 and conclude the paper in Section 8.


## 2. Related Work

The idea of Identity-Based Encryption (IBE) was first introduced by Shamir [21]. In IBE, the encryptor makes an access policy based on an identity, and only a user with the matching identity obtains the decryption privilege. Encryption by identity, however, leads to the following limitations: lack of one-to-many relationship between the ciphertext and decryption key and the need for the encryptor to know each user’s identity in advance. Later, Sahai and Waters introduced Fuzzy Identity-Based Encryption, which is the first prototype of attribute-based encryption (ABE) [22]. While the IBE scheme views an identity as a string of characters, in ABE, an identity is viewed as a set of descriptive attributes (a.k.a., identity set) such as name and affiliation. The ABE scheme allows the encryption of a message based on some identity set ω
′, and the decryption ability is given if and only if a user’s set ω is close enough to ω
′ to satisfy a system-defined threshold. This property enables fine-grained access control and a one-to-many relationship between a ciphertext and its receivers since anyone whose identity set satisfies a given threshold can obtain the decryption privilege. However, the threshold semantics are not very expressive and cannot support fine-grained access control. This drawback means that the threshold-based ABE scheme cannot be applied to more general systems.In CP-ABE [12–16], a ciphertext is associated with an access policy and decryption keys are labeled with an arbitrary number of attributes. The encryptor specifies an access policy over encryptor-chosen attributes. The access right is given if and only if the attributes in the decryption key satisfy the access policy in the ciphertext. In these schemes, however, the size of a ciphertext has a linear relationship with the number of attributes in the access policies, resulting in inapplicability for resource-constrained environments.To limit the size of ciphertexts, Zhou and Huang proposed constant-sized CP-ABE (C-CP-ABE) with a logicalAND access policy with wildcards [23]. This scheme limits the size of each ciphertext to up to 300 bytes in total, where a ciphertext consists of encrypted data, an access policy, and 2 bilinear group elements. Chen et al. further improved the C-CP-ABE scheme in terms of security [24] making it CPA-secure under a well-established assumption in the standard model without loss of efficiency. Overall, these schemes successfully make the size of ciphertexts constant. However, they reveal the underlying access policy publicly.While previous works feature open access policies, Hur introduced a CP-ABE scheme with hidden access policy in smart grid [9]. To preserve policy privacy, a one-way anonymous key agreement scheme is used as a building block in order to replace identity hashes with user-generated pseudonyms. However, this scheme does not support constant-sized ciphertext. Interestingly, an efficient CP-ABE scheme with a hidden policy was proposed [19]. In this scheme, AND-gate access policies with wildcards are used and each ciphertext header requires 2 bilinear group elements, each of which is limited to 100 bytes in total. Also, access policies are obfuscated by computing the intersection between a given access policy and an all-wildcard attribute set. This technique, however, partially leaks the access policy, because unauthorized users can guess at a minimum which attributes are treated asdo not care. In addition, the user must run the decryption algorithm at least once, to determine whether he satisfies the access policy, since only decryption failure notifies whether the decryption key satisfies the underlying access policy.The ability to resist illegal key sharing is a highly desirable characteristic for ABE. To achieve this, Li et al. introduced a user-accountable CP-ABE scheme that binds user identity in the private key, thereby allowing illegally-shared keys to be traced [25]. Although this methodology has also been adopted by other traceable CP-ABE schemes [26, 27], none of them fully support either constant-sized ciphertext or hidden access policies. In addition to supporting these features, in this paper, we also insert a unique identifier into each private key such that any key can be traced in constant time, regardless of the number of attributes.


## 3. Preliminaries

### 3.1. Bilinear Map

LetG
0 be a multiplicative cyclic group of large prime order p. The bilinear map e is defined as follows: e
:
G
0
×
G
0
→
G
1, where G
1 is the codomain of e. The bilinear map e has the following properties:(i)
Bilinearty.
e
(
P
a
,
Q
b
)
=
e
(
P
,
Q
)
a
b, where ∀
P
,
Q
∈
G
0
,
∀
a
,
b
∈
Z
p
∗
.
(ii)
Symmetry. One has ∀
P
,
Q
∈
G
0
,
e
(
P
,
Q
)
=
e
(
Q
,
P
)
.
(iii)
Nondegeneracy.
e
(
g
,
g
)
≠
1, where g is the generator of G
0
.
(iv)
Computability. There exists an efficient algorithm to compute the bilinear map e.


### 3.2. Security Assumption

The security of the proposed scheme is based on the Bilinear Diffie-Hellman Exponent assumption (BDHE) [28]. Let G
0 be a bilinear group of large prime order p and let g be a generator of G
0. The K-BDHE problem in G
0 is defined as follows. Given the vector of 2
K
+
1 elements (1)
h
,
g
,
g
α
,
g
α
2
,
…
,
g
α
K
,
g
α
K
+
2
,
…
,
g
α
2
K
∈
G
0
2
K
+
1as the input where g
α
K
+
1 is not in the vector, the goal of the computational K-BDHE problem is to compute e
(
g
,
h
)
α
K
+
1. Define the set Y
g
,
α
,
K as (2)
Y
g
,
α
,
K
=
g
α
,
g
α
2
,
…
,
g
α
K
,
g
α
K
+
2
,
…
,
g
α
2
K
.Then, we have the following definition.Definition 1 (Decisional K-BDHE).
The decisionalK-BDHE assumption is said to be hold in G
0 if there is no probabilistic polynomial time adversary who is able to distinguish (3)
h
,
g
,
Y
g
,
α
,
K
,
e
g
,
h
α
K
+
1
,
h
,
g
,
Y
g
,
α
,
K
,
e
g
,
h
Rwith nonnegligible advantage, where α
,
R
∈
Z
p and g
,
h
∈
G
0 are chosen independently and uniformly at random.We exploit Boneh et al.’sl-Strong Diffie-Hellman assumption (l-SDH) to prove traceability [29]. Given a (
l
+
1
)-tuple g
,
g
x
,
g
x
2
,
…
,
g
x
l as input where x
∈
Z
p
∗ is chosen uniformly at random, the l-SDH assumption is stated as follows: there is no probabilistic polynomial time adversary who is able to output c
,
g
1
/
(
x
+
c
)
∈
Z
p
∗
×
G
0 with nonnegligible probability, where c is not allowed to be zero.Formally, we have the followingl-SDH assumption.Assumption 2 (l-SDH).
Thel-Strong Diffie-Hellman problem in G
0 is defined as follows: given a (
l
+
1
)-tuple g
,
g
x
,
g
x
2
,
…
,
g
x
l as input, output c
,
g
1
/
(
x
+
c
)
∈
Z
p
∗
×
G
0. An algorithm A has advantage ϵ in solving l-SDH in G
0 if the following holds:(4)
Pr
⁡
A
g
,
g
x
,
g
x
2
,
…
,
g
x
l
=
c
,
g
1
/
x
+
c
≥
ϵ
,where the probability is over the random choice of x in Z
p
∗.Definition 3.
Thel-SDH assumption is (
t
,
ϵ
)-secure if no t-time algorithm has advantage at least ϵ in solving the l-SDH problem in G
0.


### 3.3. Access Policy

Given an attribute universeU
=
{
A
1
,
A
2
,
…
,
A
k
}, each A
i has one of three values {
A
i
+
,
A
i
-
,
A
i
∗
}, where A
i
+ denotes that the user has A
i, A
i
- denotes that the user does not have A
i or A
i is not a proper attribute of this user, and A
i
∗ denotes a wildcard specifyingdo not care. We define the user’s attribute set as follows.Definition 4.
LetL
=
{
A
1
+
,
-
,
A
2
+
,
-
,
…
,
A
k
+
,
-
} be a user’s attribute set, where A
i
+
,
-
∈
{
A
i
+
,
A
i
-
} and k is the order of the attribute universe. Then, L
=
L
+
∪
L
-, where L
+
=
A
i
+
∣
∀
i
∈
1
,
…
,
k and L
-
=
A
i
-
∣
∀
i
∈
1
,
…
,
k. One has L
+
∩
L
-
=
∅.Next we define theAND-gate access policy as follows.Definition 5.
LetW
=
{
A
1
,
…
,
A
k
} be anAND-gate access policy where A
i
∈
{
A
i
+
,
A
i
-
,
A
i
∗
}. Denote L
⊨
W that the user’s attribute set L satisfies W. Then, (5)
L
⊨
W
⟺
W
⊂
L
∪
A
1
∗
,
…
,
A
k
∗
.


### 3.4. One-Way Anonymous Key Agreement

In this paper, the key idea used to obfuscate attributes in the policy starts from Boneh-Franklin Identity-Based Encryption [30]. In their scheme, a private key generator (PKG) takes the role of issuing private keys. It generates a private key d
i
=
H
(
I
D
i
)
s
∈
G
0 for each user I
D
i using a master secret s, where H
:
{
0,1
}
∗
→
G
0 is a cryptographic hash function.Based on [30], Kate et al. proposed a one-way anonymous key agreement scheme by replacing H
(
I
D
i
) with a pseudonym chosen by each user [31]. This scheme guarantees anonymity for just one receiver when two users engage in it. We give a specific example as follows. Suppose Alice and Bob hold identity I
D
A and identity I
D
B, respectively, and they are clients of the same key authority which holds a master secret s. Given the private key d
A
=
Q
A
s
=
H
(
I
D
A
)
s, Alice wants to communicate with Bob, without disclosing her identity.To achieve this, the key agreement protocol runs as follows:(1)
Alice computesQ
B
=
H
(
I
D
B
), chooses a random r
A
∈
Z
p
∗, sets a pseudonym P
A
=
Q
A
r
A, and computes the session key K
A
,
B
=
e
(
d
A
,
Q
B
)
r
A
=
e
(
Q
A
,
Q
B
)
s
r
A. She sends the pseudonym P
A to Bob.
(2)
Given his private keyd
B, Bob computes the session key K
A
,
B
=
e
(
P
A
,
d
B
)
=
e
(
Q
A
,
Q
B
)
s
r
A.In this noninteractive manner, the session key is implicitly authenticated such that Alice is assured that the no one can derive the key other than Bob. Based on the BDH assumption, this protocol is proved to be secure in the random oracle model satisfying unconditional anonymity, no impersonation, and session key secrecy. To hide the policy we exploit the technique used in [9] as a building block instead of building a new method for policy obfuscation from scratch.


### 3.5. Definitions

In this section, we define a general CP-ABE with hidden policy, constant-sized ciphertexts, and traceability capabilities for secure data sharing. The scheme consists of the following seven algorithms:(i)
S
e
t
u
p
(
k
)
→
(
M
K
,
P
K
). The Setup algorithm takes as input the number of attributes k. It outputs a public key PK and a master key MK and initializes an identity table T
=
∅.
(ii)
K
e
y
G
e
n
(
M
K
,
P
K
,
L
,
i
d
)
→
(
S
K
). The key generation algorithm takes as input the master key MK, the public key PK, and the user’s attribute set L with identity id. It outputs a decryption key SK and inserts id into T.
(iii)
E
n
c
r
y
p
t
(
P
K
,
W
,
M
)
→
(
C
T
). The encryption algorithm takes as input the public key PK, an access policy W, and a message M. It outputs a ciphertext CT such that only the users whose decryption keys satisfying W should be able to extract M. CT is associated with the obfuscated policy W.
(iv)
G
e
n
T
o
k
e
n
(
S
K
u
,
Λ
)
→
(
T
K
Λ
,
u
). The token generation algorithm takes as input the user u’s secret key S
K
u and a set of attributes Λ
⊨
W. It outputs a token T
K
Λ
,
u.
(v)
P
D
e
c
r
y
p
t
(
T
K
Λ
,
u
,
C
T
)
→
(
C
T
′
). The partial decryption algorithm takes as input the token and outputs a partially decrypted ciphertext CT
′ for a user u.
(vi)
D
e
c
r
y
p
t
(
P
K
,
S
K
,
C
T
′
,
C
T
)
→
M
or
⊥. The decryption algorithm takes as input the public key PK, a decryption key SK, and ciphertexts C
T
′, CT. If L
⊨
W, then it outputs a message M, where L is the user’s attribute set and W is the access policy. Otherwise, it outputs ⊥ which indicates the failure of decryption.
(vii)
T
r
a
c
e
(
P
K
,
S
K
,
T
)
→
i
d
or
⊤. The tracing algorithm takes as input the public key PK, a decryption key SK, and the table T. It determines whether SK iswell-formed indicating that SK is the real output of KeyGen. If SK is well-formed, the algorithm outputs an identity id which corresponds to SK. Otherwise it outputs ⊤ implying that SK is not well-formed. Thewell-formed decryption key is guaranteed to work correctly in the well-formed decryption process.In the proposed scheme, each public key component is mapped to an attribute valueA
i. When encrypting data, the encryptor specifies an access policy W, where A
i
∈
{
+
,
-
,
∗
}. The decryption succeeds only when the user’s attribute set L satisfies the (obfuscated) policy W.


## 3.1. Bilinear Map

LetG
0 be a multiplicative cyclic group of large prime order p. The bilinear map e is defined as follows: e
:
G
0
×
G
0
→
G
1, where G
1 is the codomain of e. The bilinear map e has the following properties:(i)
Bilinearty.
e
(
P
a
,
Q
b
)
=
e
(
P
,
Q
)
a
b, where ∀
P
,
Q
∈
G
0
,
∀
a
,
b
∈
Z
p
∗
.
(ii)
Symmetry. One has ∀
P
,
Q
∈
G
0
,
e
(
P
,
Q
)
=
e
(
Q
,
P
)
.
(iii)
Nondegeneracy.
e
(
g
,
g
)
≠
1, where g is the generator of G
0
.
(iv)
Computability. There exists an efficient algorithm to compute the bilinear map e.


## 3.2. Security Assumption

The security of the proposed scheme is based on the Bilinear Diffie-Hellman Exponent assumption (BDHE) [28]. Let G
0 be a bilinear group of large prime order p and let g be a generator of G
0. The K-BDHE problem in G
0 is defined as follows. Given the vector of 2
K
+
1 elements (1)
h
,
g
,
g
α
,
g
α
2
,
…
,
g
α
K
,
g
α
K
+
2
,
…
,
g
α
2
K
∈
G
0
2
K
+
1as the input where g
α
K
+
1 is not in the vector, the goal of the computational K-BDHE problem is to compute e
(
g
,
h
)
α
K
+
1. Define the set Y
g
,
α
,
K as (2)
Y
g
,
α
,
K
=
g
α
,
g
α
2
,
…
,
g
α
K
,
g
α
K
+
2
,
…
,
g
α
2
K
.Then, we have the following definition.Definition 1 (Decisional K-BDHE).
The decisionalK-BDHE assumption is said to be hold in G
0 if there is no probabilistic polynomial time adversary who is able to distinguish (3)
h
,
g
,
Y
g
,
α
,
K
,
e
g
,
h
α
K
+
1
,
h
,
g
,
Y
g
,
α
,
K
,
e
g
,
h
Rwith nonnegligible advantage, where α
,
R
∈
Z
p and g
,
h
∈
G
0 are chosen independently and uniformly at random.We exploit Boneh et al.’sl-Strong Diffie-Hellman assumption (l-SDH) to prove traceability [29]. Given a (
l
+
1
)-tuple g
,
g
x
,
g
x
2
,
…
,
g
x
l as input where x
∈
Z
p
∗ is chosen uniformly at random, the l-SDH assumption is stated as follows: there is no probabilistic polynomial time adversary who is able to output c
,
g
1
/
(
x
+
c
)
∈
Z
p
∗
×
G
0 with nonnegligible probability, where c is not allowed to be zero.Formally, we have the followingl-SDH assumption.Assumption 2 (l-SDH).
Thel-Strong Diffie-Hellman problem in G
0 is defined as follows: given a (
l
+
1
)-tuple g
,
g
x
,
g
x
2
,
…
,
g
x
l as input, output c
,
g
1
/
(
x
+
c
)
∈
Z
p
∗
×
G
0. An algorithm A has advantage ϵ in solving l-SDH in G
0 if the following holds:(4)
Pr
⁡
A
g
,
g
x
,
g
x
2
,
…
,
g
x
l
=
c
,
g
1
/
x
+
c
≥
ϵ
,where the probability is over the random choice of x in Z
p
∗.Definition 3.
Thel-SDH assumption is (
t
,
ϵ
)-secure if no t-time algorithm has advantage at least ϵ in solving the l-SDH problem in G
0.


## 3.3. Access Policy

Given an attribute universeU
=
{
A
1
,
A
2
,
…
,
A
k
}, each A
i has one of three values {
A
i
+
,
A
i
-
,
A
i
∗
}, where A
i
+ denotes that the user has A
i, A
i
- denotes that the user does not have A
i or A
i is not a proper attribute of this user, and A
i
∗ denotes a wildcard specifyingdo not care. We define the user’s attribute set as follows.Definition 4.
LetL
=
{
A
1
+
,
-
,
A
2
+
,
-
,
…
,
A
k
+
,
-
} be a user’s attribute set, where A
i
+
,
-
∈
{
A
i
+
,
A
i
-
} and k is the order of the attribute universe. Then, L
=
L
+
∪
L
-, where L
+
=
A
i
+
∣
∀
i
∈
1
,
…
,
k and L
-
=
A
i
-
∣
∀
i
∈
1
,
…
,
k. One has L
+
∩
L
-
=
∅.Next we define theAND-gate access policy as follows.Definition 5.
LetW
=
{
A
1
,
…
,
A
k
} be anAND-gate access policy where A
i
∈
{
A
i
+
,
A
i
-
,
A
i
∗
}. Denote L
⊨
W that the user’s attribute set L satisfies W. Then, (5)
L
⊨
W
⟺
W
⊂
L
∪
A
1
∗
,
…
,
A
k
∗
.


## 3.4. One-Way Anonymous Key Agreement

In this paper, the key idea used to obfuscate attributes in the policy starts from Boneh-Franklin Identity-Based Encryption [30]. In their scheme, a private key generator (PKG) takes the role of issuing private keys. It generates a private key d
i
=
H
(
I
D
i
)
s
∈
G
0 for each user I
D
i using a master secret s, where H
:
{
0,1
}
∗
→
G
0 is a cryptographic hash function.Based on [30], Kate et al. proposed a one-way anonymous key agreement scheme by replacing H
(
I
D
i
) with a pseudonym chosen by each user [31]. This scheme guarantees anonymity for just one receiver when two users engage in it. We give a specific example as follows. Suppose Alice and Bob hold identity I
D
A and identity I
D
B, respectively, and they are clients of the same key authority which holds a master secret s. Given the private key d
A
=
Q
A
s
=
H
(
I
D
A
)
s, Alice wants to communicate with Bob, without disclosing her identity.To achieve this, the key agreement protocol runs as follows:(1)
Alice computesQ
B
=
H
(
I
D
B
), chooses a random r
A
∈
Z
p
∗, sets a pseudonym P
A
=
Q
A
r
A, and computes the session key K
A
,
B
=
e
(
d
A
,
Q
B
)
r
A
=
e
(
Q
A
,
Q
B
)
s
r
A. She sends the pseudonym P
A to Bob.
(2)
Given his private keyd
B, Bob computes the session key K
A
,
B
=
e
(
P
A
,
d
B
)
=
e
(
Q
A
,
Q
B
)
s
r
A.In this noninteractive manner, the session key is implicitly authenticated such that Alice is assured that the no one can derive the key other than Bob. Based on the BDH assumption, this protocol is proved to be secure in the random oracle model satisfying unconditional anonymity, no impersonation, and session key secrecy. To hide the policy we exploit the technique used in [9] as a building block instead of building a new method for policy obfuscation from scratch.


## 3.5. Definitions

In this section, we define a general CP-ABE with hidden policy, constant-sized ciphertexts, and traceability capabilities for secure data sharing. The scheme consists of the following seven algorithms:(i)
S
e
t
u
p
(
k
)
→
(
M
K
,
P
K
). The Setup algorithm takes as input the number of attributes k. It outputs a public key PK and a master key MK and initializes an identity table T
=
∅.
(ii)
K
e
y
G
e
n
(
M
K
,
P
K
,
L
,
i
d
)
→
(
S
K
). The key generation algorithm takes as input the master key MK, the public key PK, and the user’s attribute set L with identity id. It outputs a decryption key SK and inserts id into T.
(iii)
E
n
c
r
y
p
t
(
P
K
,
W
,
M
)
→
(
C
T
). The encryption algorithm takes as input the public key PK, an access policy W, and a message M. It outputs a ciphertext CT such that only the users whose decryption keys satisfying W should be able to extract M. CT is associated with the obfuscated policy W.
(iv)
G
e
n
T
o
k
e
n
(
S
K
u
,
Λ
)
→
(
T
K
Λ
,
u
). The token generation algorithm takes as input the user u’s secret key S
K
u and a set of attributes Λ
⊨
W. It outputs a token T
K
Λ
,
u.
(v)
P
D
e
c
r
y
p
t
(
T
K
Λ
,
u
,
C
T
)
→
(
C
T
′
). The partial decryption algorithm takes as input the token and outputs a partially decrypted ciphertext CT
′ for a user u.
(vi)
D
e
c
r
y
p
t
(
P
K
,
S
K
,
C
T
′
,
C
T
)
→
M
or
⊥. The decryption algorithm takes as input the public key PK, a decryption key SK, and ciphertexts C
T
′, CT. If L
⊨
W, then it outputs a message M, where L is the user’s attribute set and W is the access policy. Otherwise, it outputs ⊥ which indicates the failure of decryption.
(vii)
T
r
a
c
e
(
P
K
,
S
K
,
T
)
→
i
d
or
⊤. The tracing algorithm takes as input the public key PK, a decryption key SK, and the table T. It determines whether SK iswell-formed indicating that SK is the real output of KeyGen. If SK is well-formed, the algorithm outputs an identity id which corresponds to SK. Otherwise it outputs ⊤ implying that SK is not well-formed. Thewell-formed decryption key is guaranteed to work correctly in the well-formed decryption process.In the proposed scheme, each public key component is mapped to an attribute valueA
i. When encrypting data, the encryptor specifies an access policy W, where A
i
∈
{
+
,
-
,
∗
}. The decryption succeeds only when the user’s attribute set L satisfies the (obfuscated) policy W.


## 4. mHealth Architecture

### 4.1. System Model

In mHealth systems, intelligent wireless sensors perform data acquisition and processing [32]. Individual sensors monitor certain physiological signals and communicate with each other and the personal server such as a tablet PC as shown in Figure 1. Then, the personal server integrates the data received from the different sensors and plays the role of a gateway by sending data to the upper layer of the mHealth system. From a security point of view, the mHealth system components are categorized as follows:(1)
Trust Authority. This is a key entity that issues the public and secret parameters for the mHealth system. It publishes diverse access privileges to individual entities based on their attributes. The trust authority is assumed to be fully trusted in the mHealth system [10].
(2)
Storage Center. This is a data repository center that stores EHRs. In mHealth systems, hospitals or clinics with certain qualifications certified by the trust authority can be employed as a storage center. It is assumed to be honest-but-curious [10]. Thus, it will honestly execute the assigned tasks and like to learn as much information from the encrypted data as possible.
(3)
Encryptor. This is a patient who generates data and sends it to the storage center. It uses mobile devices to interact with the storage center. Encryptors are responsible for defining access policy based on attributes, obfuscating the policy, associating it with the data, and encrypting the data according to the policy. Hereafter, we will use “encryptor” and “patient” interchangeably.
(4)
User. This includes entities such as the patient, physicians, nurses, lab technicians, researchers, or receptionists who want to access EHRs contained in the storage center. A user will be authorized to decrypt a ciphertext given by the storage center if and only if his key satisfies the access policy of that ciphertext.


### 4.2. Security Model

CPA Security. The security model of the proposed scheme is similar to that of the CP-ABE scheme with constant-sized ciphertexts [23] except that each key query is labeled with an explicit identity and attributes are obfuscated. We first introduce the semantic security game. A CP-ABE scheme is considered to be CPA-secure if no probabilistic polynomial time adversaries have nonnegligible advantages in the following CPA security game.(i)
Init. The adversary chooses a challenge access policy W and gives it to the challenger.
(ii)
Setup. The challenger runs the Setup algorithm and gives the adversary the public parameter PK.
(iii)
Phase 1. The adversary queries the challenger for decryption keys corresponding to (
id
,
L
), where L
⊭
W. The challenger answers with a decryption key SK for L. The adversary repeats this phase adaptively.
(iv)
Challenge. The challenger obtains C
0
,
C
1
,
Key by running the Encrypt algorithm. The challenger sets Ke
y
0
=
Key and picks a random Ke
y
1 of the same length as Ke
y
0. It then flips a random coin β
∈
{
0,1
} and gives C
0
,
C
1
,
Ke
y
β to the adversary.
(v)
Phase 2. It is the same as Phase 1.
(vi)
Guess. The adversary outputs a guess β
′
∈
{
0,1
}.The adversary wins the game ifβ
′
=
β under the restriction that L cannot satisfy the access policy W. The adversary may run Phase 2 to make multiple key queries in the midst of the challenge. Note that the adversary declares the access policy at the start of the game.The advantage of an adversary in this game is defined as(6)
Pr
⁡
β
′
=
β
-
1
2
.Traceability. The traceability definition for the proposed scheme is described by the following security game:(i)
Setup. The challenger runs the Setup algorithm to obtain the public parameter PK. Then, the challenger gives PK to the adversary.
(ii)
KeyQuery. The adversary makes decryption key queries q-times to the challenger, where sets of attributes i
d
1
,
L
1
,
…
,
(
i
d
q
,
L
q
) correspond to decryption keys.
(iii)
KeyForgery. The adversary outputs a decryption key S
K
∗.The adversary wins the game if the following holds:(1)
T
r
a
c
e
(
P
K
,
S
K
∗
,
T
)
≠
⊥.
(2)
T
r
a
c
e
(
P
K
,
S
K
∗
,
T
)
∉
{
i
d
1
,
…
,
i
d
q
}.Then, the advantage of the adversary in this game is(7)
Pr
⁡
Trace
PK
,
S
K
∗
,
T
∉
⊥
∪
i
d
1
,
…
,
i
d
q
.Definition 6.
A traceable ciphertext policy attribute-based encryption scheme is fully traceable if all polynomial time adversaries have at most negligible advantage in this game.Policy Privacy. While sharing data in the mHealth system, the storage center or unauthorized users must learn no information about the attributes associated with the access policy of the encrypted data. Also, even authorized users should not obtain any information about these attributes other than the fact that they are authorized to access the data.


## 4.1. System Model

In mHealth systems, intelligent wireless sensors perform data acquisition and processing [32]. Individual sensors monitor certain physiological signals and communicate with each other and the personal server such as a tablet PC as shown in Figure 1. Then, the personal server integrates the data received from the different sensors and plays the role of a gateway by sending data to the upper layer of the mHealth system. From a security point of view, the mHealth system components are categorized as follows:(1)
Trust Authority. This is a key entity that issues the public and secret parameters for the mHealth system. It publishes diverse access privileges to individual entities based on their attributes. The trust authority is assumed to be fully trusted in the mHealth system [10].
(2)
Storage Center. This is a data repository center that stores EHRs. In mHealth systems, hospitals or clinics with certain qualifications certified by the trust authority can be employed as a storage center. It is assumed to be honest-but-curious [10]. Thus, it will honestly execute the assigned tasks and like to learn as much information from the encrypted data as possible.
(3)
Encryptor. This is a patient who generates data and sends it to the storage center. It uses mobile devices to interact with the storage center. Encryptors are responsible for defining access policy based on attributes, obfuscating the policy, associating it with the data, and encrypting the data according to the policy. Hereafter, we will use “encryptor” and “patient” interchangeably.
(4)
User. This includes entities such as the patient, physicians, nurses, lab technicians, researchers, or receptionists who want to access EHRs contained in the storage center. A user will be authorized to decrypt a ciphertext given by the storage center if and only if his key satisfies the access policy of that ciphertext.


## 4.2. Security Model

CPA Security. The security model of the proposed scheme is similar to that of the CP-ABE scheme with constant-sized ciphertexts [23] except that each key query is labeled with an explicit identity and attributes are obfuscated. We first introduce the semantic security game. A CP-ABE scheme is considered to be CPA-secure if no probabilistic polynomial time adversaries have nonnegligible advantages in the following CPA security game.(i)
Init. The adversary chooses a challenge access policy W and gives it to the challenger.
(ii)
Setup. The challenger runs the Setup algorithm and gives the adversary the public parameter PK.
(iii)
Phase 1. The adversary queries the challenger for decryption keys corresponding to (
id
,
L
), where L
⊭
W. The challenger answers with a decryption key SK for L. The adversary repeats this phase adaptively.
(iv)
Challenge. The challenger obtains C
0
,
C
1
,
Key by running the Encrypt algorithm. The challenger sets Ke
y
0
=
Key and picks a random Ke
y
1 of the same length as Ke
y
0. It then flips a random coin β
∈
{
0,1
} and gives C
0
,
C
1
,
Ke
y
β to the adversary.
(v)
Phase 2. It is the same as Phase 1.
(vi)
Guess. The adversary outputs a guess β
′
∈
{
0,1
}.The adversary wins the game ifβ
′
=
β under the restriction that L cannot satisfy the access policy W. The adversary may run Phase 2 to make multiple key queries in the midst of the challenge. Note that the adversary declares the access policy at the start of the game.The advantage of an adversary in this game is defined as(6)
Pr
⁡
β
′
=
β
-
1
2
.Traceability. The traceability definition for the proposed scheme is described by the following security game:(i)
Setup. The challenger runs the Setup algorithm to obtain the public parameter PK. Then, the challenger gives PK to the adversary.
(ii)
KeyQuery. The adversary makes decryption key queries q-times to the challenger, where sets of attributes i
d
1
,
L
1
,
…
,
(
i
d
q
,
L
q
) correspond to decryption keys.
(iii)
KeyForgery. The adversary outputs a decryption key S
K
∗.The adversary wins the game if the following holds:(1)
T
r
a
c
e
(
P
K
,
S
K
∗
,
T
)
≠
⊥.
(2)
T
r
a
c
e
(
P
K
,
S
K
∗
,
T
)
∉
{
i
d
1
,
…
,
i
d
q
}.Then, the advantage of the adversary in this game is(7)
Pr
⁡
Trace
PK
,
S
K
∗
,
T
∉
⊥
∪
i
d
1
,
…
,
i
d
q
.Definition 6.
A traceable ciphertext policy attribute-based encryption scheme is fully traceable if all polynomial time adversaries have at most negligible advantage in this game.Policy Privacy. While sharing data in the mHealth system, the storage center or unauthorized users must learn no information about the attributes associated with the access policy of the encrypted data. Also, even authorized users should not obtain any information about these attributes other than the fact that they are authorized to access the data.


## 5. Proposed Scheme

### 5.1. System Architecture

The proposed data sharing process in the mHealth system runs as follows. An encryptor defines the access policy with a set of attributes, encrypts the EHRs associated with clinical reports under the policy, and uploads the ciphertext and the obfuscated policy to the storage center. When a user wants to access the uploaded data, he first generates a token using his attributes and sends it to the storage center. If the attributes in the token satisfy the access policy, then the storage center partially decrypts the ciphertext and sends the result to the user. Then, the user finishes the decryption of the ciphertext using his secret key and the partially decrypted ciphertext as inputs. The outline of data sharing process is depicted in Figure2.Figure 2
Overview of the proposed data sharing process.


### 5.2. Scheme Construction

The proposed scheme is constructed on the basis of the following seven algorithms as follows.S
e
t
u
p
(
k
)
→
(
M
K
,
P
K
). Given k attributes {
A
1
,
A
2
,
…
,
A
k
} as the attribute universe, the proposed scheme has K
=
3
k attribute values such that A
i
∈
{
A
i
+
,
A
i
-
,
A
i
∗
}. Specifically, we map {
A
1
+
,
A
2
+
,
…
,
A
k
+
} to {
1,2
,
…
,
k
}, {
A
1
-
,
A
2
-
,
…
,
A
k
-
} to {
k
+
1
,
k
+
2
,
…
,
2
k
}, and {
A
1
∗
,
A
2
∗
,
…
,
A
k
∗
} to {
2
k
+
1,2
k
+
2
,
…
,
3
k
}.LetG
0 be a bilinear group of prime order p. The Setup algorithm chooses a random generator g
∈
G
0 and random α
,
β
,
γ
∈
Z
p. For i
=
1,2
,
…
,
K
,
K
+
2
,
…
,
2
K, it computes g
i
=
g
α
i. Then, it computes v
=
g
γ and h
=
g
β. The master and public keys are set to M
K
=
α
,
β
,
γ; P
K
=
g
,
g
1
,
…
,
g
K
,
g
K
+
2
,
…
,
g
2
K
,
v
,
h
∈
G
0
2
K
+
1. The algorithm initializes an identity table T
=
∅.K
e
y
G
e
n
(
M
K
,
P
K
,
L
u
t
,
i
d
u
t
)
→
(
S
K
u
t
). Assume that each user u
t is tagged with an attribute set L
u
t
=
L
u
t
+
∪
L
u
t
-, where L
u
t
+
⊂
{
1,2
,
…
,
k
} and L
u
t
-
⊂
{
k
+
1
,
k
+
2
,
…
,
2
k
}. The KeyGen algorithm randomly chooses a
,
c
∈
Z
p
∗, {
r
1
,
r
2
,
…
,
r
k
}
∈
Z
p. Then, it computes r
=
∑
i
=
1
k
‍
r
i, D
′
′
=
g
r and D
=
g
r
γ
/
(
a
+
c
). For all j
∈
L
u
t, it computes D
′
′
′
=
H
(
j
)
β, where H is a hash function H
:
{
0,1
}
∗
→
G
0.Next, the algorithm computes the following:(i)
For everyi
∈
L
u
t
+, compute D
i
=
g
γ
c
α
i
+
r
i
′
/
a
+
c, where i
′
=
i.
(ii)
For everyi
∈
L
u
t
-, compute D
i
=
g
γ
c
α
i
+
r
i
′
/
a
+
c, where i
′
=
i
-
k.
(iii)
For everyi
∈
L
u
t
∗, compute D
i
=
g
γ
c
α
i
+
r
i
′
/
a
+
c, where i
′
=
i
-
2
k.The decryption key for useru
t is set to(8)
S
K
u
t
=
D
=
g
r
γ
/
a
+
c
,
D
i
∣
i
∈
L
u
t
+
,
L
u
t
-
,
L
u
t
∗
,
D
′
=
c
,
D
′
′
=
g
r
,
D
′
′
′
=
H
j
β
,
D
a
=
g
a
.Note that 1
/
(
a
+
c
) is computed modulo p. If g
c
d
(
a
+
c
,
p
)
≠
1 or c is already in T, the algorithm is run repeatedly with another random c
∈
Z
p
∗. Then, it puts a tuple (
c
,
i
d
u
t
) into T and uploads i
d
u
t
,
{
g
i
D
′
∣
∀
i
∈
L
u
t
} to the storage center.E
n
c
r
y
p
t
(
P
K
,
W
,
M
)
→
(
C
T
). W is anAND-gate access policy with k attributes specified by an encryptor u
b, where each attribute is either positive/negative or wildcard. The algorithm chooses a random b
∈
Z
p
∗ and computes s
j
=
e
h
b
,
H
(
j
), H
1
(
s
j
) for all j
∈
W, where H
1 is a hash function H
:
G
1
→
{
0,1
}
log
⁡
p. Then, the access policy W is obfuscated by replacing each attribute with H
1
(
s
j
).Next, the algorithm picks a randomt
∈
Z
p and computes a one-time symmetric key Key
=
e
(
g
K
,
g
1
)
k
t. It encrypts the message M as {
M
}
Key and computes g
t. Then, it computes v
∏
j
∈
W
‍
g
K
+
1
-
j
t. The ciphertext CT is set to (9)
CT
=
W
,
M
Key
,
C
0
=
g
t
,
C
1
=
v
∏
j
∈
W
g
K
+
1
-
j
t
,
i
d
u
t
,
g
b
.The encryptor uploads CT to the storage center.G
e
n
T
o
k
e
n
(
S
K
u
t
,
Λ
)
→
(
T
K
Λ
,
u
t
). When a user u
t needs to access the ciphertext of u
b in the storage center with a set of attributes Λ
⊨
W, u
t receives g
b from the storage center and generates the token for Λ as follows. For all j
∈
Λ, the algorithm computes s
j
=
e
(
g
b
,
D
j
′
′
′
)
=
e
g
b
,
H
(
j
)
β. Then, it constructs the token T
K
Λ
,
u
t
=
{
I
j
∣
∀
j
∈
Λ
,
I
j
=
H
1
(
s
j
)
}. Each I
j will be used as an index for the obfuscated attribute j. The user u
t sends T
K
Λ
,
u
t to the storage center.P
D
e
c
r
y
p
t
(
T
K
Λ
,
u
t
,
C
T
)
→
(
C
T
′
). Given T
K
Λ
,
u
t from the user u
t, the storage center checks if each I
j in the token satisfies the access policy associated with CT. If satisfied, the storage center partially decrypts CT using i
d
u
t
,
{
g
i
D
′
∣
∀
i
∈
L
u
t
} as (10)
A
i
=
e
g
i
D
′
,
C
1
=
e
g
,
v
∏
j
∈
W
g
K
+
1
-
j
α
i
t
D
′
=
e
g
,
g
γ
+
∑
j
∈
W
α
K
+
1
-
j
α
i
t
D
′
=
e
g
,
g
α
i
t
D
′
γ
+
t
D
′
∑
j
∈
W
α
K
+
1
-
j
+
ifor all i
∈
W. Then, it computes a production of all A
i as CT
′
=
∏
i
∈
W
‍
A
i. The storage center sends CT
′ to u
t.D
e
c
r
y
p
t
(
P
K
,
S
K
u
t
,
C
T
′
,
C
T
)
→
M
or
⊥. On receipt of the partially decrypted ciphertext CT
′ from the storage center, the user u
t computes B
i for all i
∈
W as (11)
B
i
=
e
C
0
,
∏
j
∈
W
,
j
≠
i
g
K
+
1
-
j
+
i
D
′
·
D
i
=
e
g
,
g
t
D
′
∑
j
∈
W
,
j
≠
i
α
K
+
1
-
j
+
i
+
t
γ
D
′
α
i
+
r
i
/
a
+
c
.Then, it computes B
=
∏
i
∈
W
‍
B
i and divides CT
′ by B. Using the quotient term C
T
′
/
B, the user concludes decryption as follows:(12)
CT
′
B
·
e
D
,
C
0
=
CT
′
B
·
e
g
γ
r
/
a
+
c
,
g
t
=
e
g
,
g
D
′
k
t
α
K
+
1
.Then,(13)
CT
′
B
·
e
D
,
C
0
1
/
D
′
=
e
g
,
g
k
t
α
K
+
1
=
e
g
α
K
,
g
α
k
t
=
e
g
K
,
g
1
k
t
=
Key
.The user decrypts {
M
}
Key.T
r
a
c
e
P
K
,
S
K
u
,
T
→
i
d
u
or
⊤. S
K
u is called well-formed if it passes the following conditions hold: (14)
D
′
∈
Z
p
∗
,
D
,
D
i
,
D
′
′
∈
G
0
2
K
+
1
,
e
D
a
·
g
D
′
,
D
=
e
v
,
D
′
′
≠
1
.If S
K
u is well-formed, the algorithm searches D
′ in T. If D
′ is in T, the algorithm outputs the corresponding i
d
u, and if not, the algorithm outputs the corresponding i
d
∅ indicating that the corresponding identity never appears in T. If S
K
u is not well-formed, the algorithm outputs ⊤.


## 5.1. System Architecture

The proposed data sharing process in the mHealth system runs as follows. An encryptor defines the access policy with a set of attributes, encrypts the EHRs associated with clinical reports under the policy, and uploads the ciphertext and the obfuscated policy to the storage center. When a user wants to access the uploaded data, he first generates a token using his attributes and sends it to the storage center. If the attributes in the token satisfy the access policy, then the storage center partially decrypts the ciphertext and sends the result to the user. Then, the user finishes the decryption of the ciphertext using his secret key and the partially decrypted ciphertext as inputs. The outline of data sharing process is depicted in Figure2.Figure 2
Overview of the proposed data sharing process.


## 5.2. Scheme Construction

The proposed scheme is constructed on the basis of the following seven algorithms as follows.S
e
t
u
p
(
k
)
→
(
M
K
,
P
K
). Given k attributes {
A
1
,
A
2
,
…
,
A
k
} as the attribute universe, the proposed scheme has K
=
3
k attribute values such that A
i
∈
{
A
i
+
,
A
i
-
,
A
i
∗
}. Specifically, we map {
A
1
+
,
A
2
+
,
…
,
A
k
+
} to {
1,2
,
…
,
k
}, {
A
1
-
,
A
2
-
,
…
,
A
k
-
} to {
k
+
1
,
k
+
2
,
…
,
2
k
}, and {
A
1
∗
,
A
2
∗
,
…
,
A
k
∗
} to {
2
k
+
1,2
k
+
2
,
…
,
3
k
}.LetG
0 be a bilinear group of prime order p. The Setup algorithm chooses a random generator g
∈
G
0 and random α
,
β
,
γ
∈
Z
p. For i
=
1,2
,
…
,
K
,
K
+
2
,
…
,
2
K, it computes g
i
=
g
α
i. Then, it computes v
=
g
γ and h
=
g
β. The master and public keys are set to M
K
=
α
,
β
,
γ; P
K
=
g
,
g
1
,
…
,
g
K
,
g
K
+
2
,
…
,
g
2
K
,
v
,
h
∈
G
0
2
K
+
1. The algorithm initializes an identity table T
=
∅.K
e
y
G
e
n
(
M
K
,
P
K
,
L
u
t
,
i
d
u
t
)
→
(
S
K
u
t
). Assume that each user u
t is tagged with an attribute set L
u
t
=
L
u
t
+
∪
L
u
t
-, where L
u
t
+
⊂
{
1,2
,
…
,
k
} and L
u
t
-
⊂
{
k
+
1
,
k
+
2
,
…
,
2
k
}. The KeyGen algorithm randomly chooses a
,
c
∈
Z
p
∗, {
r
1
,
r
2
,
…
,
r
k
}
∈
Z
p. Then, it computes r
=
∑
i
=
1
k
‍
r
i, D
′
′
=
g
r and D
=
g
r
γ
/
(
a
+
c
). For all j
∈
L
u
t, it computes D
′
′
′
=
H
(
j
)
β, where H is a hash function H
:
{
0,1
}
∗
→
G
0.Next, the algorithm computes the following:(i)
For everyi
∈
L
u
t
+, compute D
i
=
g
γ
c
α
i
+
r
i
′
/
a
+
c, where i
′
=
i.
(ii)
For everyi
∈
L
u
t
-, compute D
i
=
g
γ
c
α
i
+
r
i
′
/
a
+
c, where i
′
=
i
-
k.
(iii)
For everyi
∈
L
u
t
∗, compute D
i
=
g
γ
c
α
i
+
r
i
′
/
a
+
c, where i
′
=
i
-
2
k.The decryption key for useru
t is set to(8)
S
K
u
t
=
D
=
g
r
γ
/
a
+
c
,
D
i
∣
i
∈
L
u
t
+
,
L
u
t
-
,
L
u
t
∗
,
D
′
=
c
,
D
′
′
=
g
r
,
D
′
′
′
=
H
j
β
,
D
a
=
g
a
.Note that 1
/
(
a
+
c
) is computed modulo p. If g
c
d
(
a
+
c
,
p
)
≠
1 or c is already in T, the algorithm is run repeatedly with another random c
∈
Z
p
∗. Then, it puts a tuple (
c
,
i
d
u
t
) into T and uploads i
d
u
t
,
{
g
i
D
′
∣
∀
i
∈
L
u
t
} to the storage center.E
n
c
r
y
p
t
(
P
K
,
W
,
M
)
→
(
C
T
). W is anAND-gate access policy with k attributes specified by an encryptor u
b, where each attribute is either positive/negative or wildcard. The algorithm chooses a random b
∈
Z
p
∗ and computes s
j
=
e
h
b
,
H
(
j
), H
1
(
s
j
) for all j
∈
W, where H
1 is a hash function H
:
G
1
→
{
0,1
}
log
⁡
p. Then, the access policy W is obfuscated by replacing each attribute with H
1
(
s
j
).Next, the algorithm picks a randomt
∈
Z
p and computes a one-time symmetric key Key
=
e
(
g
K
,
g
1
)
k
t. It encrypts the message M as {
M
}
Key and computes g
t. Then, it computes v
∏
j
∈
W
‍
g
K
+
1
-
j
t. The ciphertext CT is set to (9)
CT
=
W
,
M
Key
,
C
0
=
g
t
,
C
1
=
v
∏
j
∈
W
g
K
+
1
-
j
t
,
i
d
u
t
,
g
b
.The encryptor uploads CT to the storage center.G
e
n
T
o
k
e
n
(
S
K
u
t
,
Λ
)
→
(
T
K
Λ
,
u
t
). When a user u
t needs to access the ciphertext of u
b in the storage center with a set of attributes Λ
⊨
W, u
t receives g
b from the storage center and generates the token for Λ as follows. For all j
∈
Λ, the algorithm computes s
j
=
e
(
g
b
,
D
j
′
′
′
)
=
e
g
b
,
H
(
j
)
β. Then, it constructs the token T
K
Λ
,
u
t
=
{
I
j
∣
∀
j
∈
Λ
,
I
j
=
H
1
(
s
j
)
}. Each I
j will be used as an index for the obfuscated attribute j. The user u
t sends T
K
Λ
,
u
t to the storage center.P
D
e
c
r
y
p
t
(
T
K
Λ
,
u
t
,
C
T
)
→
(
C
T
′
). Given T
K
Λ
,
u
t from the user u
t, the storage center checks if each I
j in the token satisfies the access policy associated with CT. If satisfied, the storage center partially decrypts CT using i
d
u
t
,
{
g
i
D
′
∣
∀
i
∈
L
u
t
} as (10)
A
i
=
e
g
i
D
′
,
C
1
=
e
g
,
v
∏
j
∈
W
g
K
+
1
-
j
α
i
t
D
′
=
e
g
,
g
γ
+
∑
j
∈
W
α
K
+
1
-
j
α
i
t
D
′
=
e
g
,
g
α
i
t
D
′
γ
+
t
D
′
∑
j
∈
W
α
K
+
1
-
j
+
ifor all i
∈
W. Then, it computes a production of all A
i as CT
′
=
∏
i
∈
W
‍
A
i. The storage center sends CT
′ to u
t.D
e
c
r
y
p
t
(
P
K
,
S
K
u
t
,
C
T
′
,
C
T
)
→
M
or
⊥. On receipt of the partially decrypted ciphertext CT
′ from the storage center, the user u
t computes B
i for all i
∈
W as (11)
B
i
=
e
C
0
,
∏
j
∈
W
,
j
≠
i
g
K
+
1
-
j
+
i
D
′
·
D
i
=
e
g
,
g
t
D
′
∑
j
∈
W
,
j
≠
i
α
K
+
1
-
j
+
i
+
t
γ
D
′
α
i
+
r
i
/
a
+
c
.Then, it computes B
=
∏
i
∈
W
‍
B
i and divides CT
′ by B. Using the quotient term C
T
′
/
B, the user concludes decryption as follows:(12)
CT
′
B
·
e
D
,
C
0
=
CT
′
B
·
e
g
γ
r
/
a
+
c
,
g
t
=
e
g
,
g
D
′
k
t
α
K
+
1
.Then,(13)
CT
′
B
·
e
D
,
C
0
1
/
D
′
=
e
g
,
g
k
t
α
K
+
1
=
e
g
α
K
,
g
α
k
t
=
e
g
K
,
g
1
k
t
=
Key
.The user decrypts {
M
}
Key.T
r
a
c
e
P
K
,
S
K
u
,
T
→
i
d
u
or
⊤. S
K
u is called well-formed if it passes the following conditions hold: (14)
D
′
∈
Z
p
∗
,
D
,
D
i
,
D
′
′
∈
G
0
2
K
+
1
,
e
D
a
·
g
D
′
,
D
=
e
v
,
D
′
′
≠
1
.If S
K
u is well-formed, the algorithm searches D
′ in T. If D
′ is in T, the algorithm outputs the corresponding i
d
u, and if not, the algorithm outputs the corresponding i
d
∅ indicating that the corresponding identity never appears in T. If S
K
u is not well-formed, the algorithm outputs ⊤.


## 6. Performance Analysis

In this section, we analyze the performance of the proposed scheme compared with the previous schemes including a constant-sized ciphertexts scheme [23], a hidden policy scheme [25], and a traceability scheme [26]. We compare each scheme in several ways such as the computational cost of encryption and decryption and the ciphertext length and in terms of the complexity assumption. Also, we implemented the proposed scheme to evaluate its actual performance. We programmed our system using the Java-based pairing based cryptography (jPBC) library [33] on a GIGABYTE desktop with 4 Intel Core i5-3570 3.40 GHz CPUs, 4 GB RAM, and running Windows 7 Ultimate K.Table1 shows the results of comparing the different schemes. The notations we use in the table are as follows: t denotes the number of attributes involved in the access policy, n denotes the number of attributes in the attribute universe, ex denotes the exponentiation operation, and denotes p the paring operation. Note that, following convention, the bit-length of the expression of the access policy and its computational costs over Z
p are ignored.Table 1
Comparison of different schemes.
Enc.
Dec.
Ciphertext length
Assumption
Constant-sized ciphertexts [23]
2
e
x
2
t
p
+
e
x
2
G
0
+
G
1
n-DBDH
Hidden policy [25]
(
t
+
2
)
e
x
(
2
t
+
1
)
p
+
t
e
x
(
t
+
1
)
G
0
+
G
1
DBDH
Traceability [26]
(
2
t
+
3
)
e
x
(
2
t
+
1
)
p
+
t
e
x
2
(
t
+
1
)
G
0
+
G
1
l-BDHI
Proposed
2
e
x
+
t
p
(
2
t
+
1
)
(
p
+
e
x
)
3
G
0
+
G
1
n-BDHEIn terms of computational cost, the constant-sized ciphertext scheme [23] shows the best encryption phase efficiency, requiring a constant number of exponentiations. The proposed scheme also needs two exponentiations in data encryption, but an additional t
p operations are required to obfuscate the access policy. In the decryption phase, the proposed scheme requires more computations than [23] since the user identity is exponentiated to every attribute value to support traceability. In contrast to [25, 26], the proposed scheme requires approximately t number of exponentiations. With regard to the ciphertext length, the proposed scheme and [23] guarantee constant-sized ciphertext. On the other hand, the hidden policy scheme [25] and the traceability scheme [26] incur linearly increasing ciphertexts as the attribute number t increases. Overall, the proposed scheme is efficient in terms of the ciphertext size and provides hidden policy traceability at the cost of more exponentiation operations.Figure3 shows the computation overhead incurred in the core algorithms, Setup, KeyGen, Encrypt, GenToken, Decrypt, PDecrypt, and Trace, under various conditions. Figure 3(a) shows how system-wide setup time varies according to the number of attributes. Figure 3(b) shows the total key generation time against different numbers of attributes. The setup occurs only once at the start of the system, and key generation occurs every time a new user joins. Figure 3(c) shows encryption time against different numbers of attributes. It increases linearly due to the time taken to obfuscate the policy attached to the data. Figure 3(d) shows the token generation time against the number of attributes. The token generation process requires a pairing operation time linear to the number of attributes. Figure 3(e) shows the partial decryption time at the storage center and decryption time at the user against the number of attributes. Interestingly, the storage center can undertake nearly 50% of whole decryption process on behalf of users. This property can be most useful for relatively resource-constrained user side devices. Lastly, Figure 3(f) shows the trace time with different numbers of attributes and users. The trace time depends only but not strongly on the number of users.Figure 3
Time costs of different algorithms.
(a)
Setup time
(b)
Key generation time
(c)
Encryption time
(d)
Token generation time
(e)
Decryption and partial decryption time
(f)
Trace time with different number of usersFurther Efficiency Improvement. jPBC is a complete Java port of the PBC library which was originally written in C [34]. Java is widely considered to be slower than C because Java programs run on the Java Virtual Machine rather than directly on the computer’s processor. Based on this, we additionally provide benchmark comparison results between jPBC and PBC in order to demonstrate how fast the proposed scheme can be when it is implemented in C language [33]. Table 2 shows the performance comparison between Java and C with respect to pairing and exponentiation operations conducted on the same machine. The two libraries were applied to the curve y
2
=
x
3
+
x over the field F
q for some prime q
=
3
m
o
d
4. The order of F
q is some prime factor of q
+
1 [33]. Since the cost of the pairing operation in PBC is approximately 12 seconds less than in jPBC, PBC is expected to improve the performance of pairing-dependent algorithms, such as GenToken and policy obfuscation process in Encrypt, by up to 81
%. Similarly, the cost of the exponentiation operations in G
1 and G
T are reduced by 14.47 and 1.583 seconds, respectively. Such a difference between the two libraries implies that moving from Java to C implementation of the proposed scheme can speed up the Setup and KeyGen algorithms by approximately 77.8
% and the PDecrypt and Decrypt algorithms by approximately 74.9
%.Table 2
jPBC and PBC benchmark comparison results [33].
Operation
jPBC
PBC
Pairing
14.654
2.688
Exponentiation inG
1
18.592
4.122
Exponentiation inG
T
2.112
0.529
Exponentiation inZ
r
0.068
0.087


## 7. Security Analysis

### 7.1. Data Confidentiality

In this section, we reduce the chosen plaintext attack (CPA) security of the proposed scheme to a decisionalK-BDHE problem. Given an access policy W, a user with an attribute set L
⊭
W colludes with x
≤
k decryption proxies. Intuitively, this attack works successfully if L
∪
{
i
1
,
…
,
i
x
}
⊨
W. Based on the CPA security game in Section 4.2, we have the following.Theorem 7.
If a probabilistic polynomial time adversary wins the CPA security game with a nonnegligible advantage, then one can construct a simulator that distinguishes aK-DBHE tuple with a nonnegligible advantage.Proof.
Suppose that an adversaryA’s advantage for winning the game is ϵ. Then, we can construct a simulator B which solves the decisional K-BDHE problem with the advantage ϵ
/
2. The simulator B takes an input vector h
,
g
,
Y
g
,
α
,
K
,
Z, where Z is either e
(
g
,
h
)
α
K
+
1 or a random element in G
0. Then, B breaks the decisional K-BDHE problem with the advantage ϵ
/
2. Specifically, B takes a random decisional K-BDHE challenge h
,
g
,
Y
g
,
α
,
K
,
Z as input, where Z is either Z
=
e
(
g
,
h
)
α
K
+
1 or a random value.
Next,B runs the following CPA game with the role of challenger. (i)
Init. A sends an access policy W to B.
(ii)
Setup. B runs the Setup algorithm to obtain PK and chooses a random d
∈
Z
p. Then, B computes (15)
v
=
g
d
∏
j
∈
W
g
K
+
1
-
j
-
1
=
g
γ
.
B outputs the public key PK
=
g
,
Y
g
,
α
,
K
,
v
∈
G
0
2
K
+
1.
Phase 1. The adversary A submits L, where L
⊭
W. Then, there exists j
∈
L such that j
+
k
∈
W, where j
∈
{
1
,
…
,
k
}, or j
-
k
∈
W, where j
∈
{
k
+
1
,
…
,
2
k
}.
Fori
=
1
,
…
,
k, B picks k random r
i
∈
Z
p and sets r
=
r
1
+
⋯
+
r
k. Next, B randomly chooses a
,
c
∈
Z
p
∗ and computes (16)
D
=
g
d
∏
j
∈
W
g
K
+
1
-
j
-
1
r
/
a
+
c
=
g
γ
r
/
a
+
c
.Next, B computes (17)
D
i
=
g
i
d
∏
j
∈
W
g
K
+
1
-
j
+
i
-
c
·
∏
j
∈
W
g
K
+
1
-
j
-
r
i
′
/
a
+
c
,where i falls into one of the following conditions: (1) i
+
k
∈
W for all i
∈
L
+, (2) i
-
k
∈
W for all i
∈
L
-, and (3) i
∉
W for all i
∈
L
∗.
Then, eachD
i is valid such that (18)
D
i
=
g
d
∏
j
∈
W
g
K
+
1
-
j
-
1
c
α
i
+
r
i
′
/
a
+
c
=
g
γ
c
α
i
+
r
i
′
/
a
+
c
.
Challenge. B sets C
0
=
h and C
1
=
h
d and gives the challenge C
0
,
C
1
,
Z
k to A. Note that C
0
=
h
=
g
t for some t such that (19)
h
d
=
g
d
t
=
g
d
∏
j
∈
W
g
K
+
1
-
j
-
1
·
∏
j
∈
W
g
K
+
1
-
j
t
=
v
∏
j
∈
W
g
K
+
1
-
j
t
,and Z
k
=
Key if Z
=
e
(
g
,
h
)
α
(
K
+
1
).
Phase 2. Repeat Phase 1.
Guess. The adversary A outputs a guess b
′, where b
′
=
0 implies that Z
=
e
(
g
,
h
)
α
K
+
1. If b
′
=
1, then Z is a random element which indicates that P
r
B
(
h
,
g
,
Y
g
,
α
,
K
,
Z
)
=
0
=
1
/
2. Note that each decryption proxy p
i
(
r
) simulates a legal decryption key component with a random r. Specifically, the adversary A passes r as a guess of r
i
′ which is embedded in D
i, where i
∈
W. We further define a decryption proxy to model collusion attacks.Definition 8.
Given2
k decryption proxies in the security game, each decryption proxy p
i
(
r
)
=
g
γ
c
α
i
+
r
/
(
a
+
c
), where r
∈
Z
p and i
∈
{
1
,
…
,
2
k
}.Lemma 9 (collision with 1 decryption proxy).
Suppose thatA has issued q queries and there is only 1 attribute i
∉
W, where A makes l queries to p
i
(
r
). The probability that none of the queries returns a legal decryption key component of any q is 1
-
q
/
p
l.Proof.
The probability that at least one query returns an illegal decryption key component of anyq is 1
-
q
/
p. Thus, if none of the l queries succeeds, then Pr
⁡
r
≠
r
i
′
=
1
-
q
/
p
l, where r is a random number in the decryption proxy and r
i
′ is a random number in the decryption key.Lemma 10 (collision with multiple decryption proxies).
SupposeA has issued q queries and there are m attributes dissatisfying W, where A makes l queries to each decryption proxy p
i
1
(
r
1
), p
i
2
(
r
2
)
,
…
,
p
i
m
(
r
m
). The probability that none of the queries returns a legal decryption key component of any q is 1
-
1
-
q
/
p
l
m.Proof.
The probability that one decryption proxy fails isP
r
[
r
≠
r
i
′
]
=
1
-
q
/
p
l. Thus, the probability that all m decryption proxies succeed is 1
-
1
-
q
/
p
l
m.In case ofZ
=
e
(
g
,
h
)
α
(
K
+
1
), we have 3 collusion scenarios as follows.0-Collusion. If no decryption proxy is used, then A has at least ϵ
/
2 advantage in breaking the proposed scheme. Thus, B has at least the following advantage in breaking K-BDHE problem: (20)
Pr
⁡
B
h
,
g
,
Y
g
,
α
,
K
,
Z
=
0
-
1
2
≥
ϵ
2
.1-Collusion. If one decryption proxy p
i
(
r
) is used, then we have P
r
[
r
≠
r
i
′
]
=
1
-
q
/
p
l. Thus, if A has at least ϵ advantage in breaking the proposed scheme, then B has at least 1
-
q
/
p
l
ϵ
/
2 advantage in breaking the K-BDHE problem.m-Collusion. If m decryption proxies p
i
1
(
r
1
)
,
…
,
p
i
m
(
r
m
) are used, then we have (21)
Pr
⁡
r
i
j
≠
r
i
j
′
,
∃
j
≤
m
=
1
-
1
-
q
p
l
m
.Thus, if A has at least ϵ advantage in breaking the proposed scheme, then B has at least the following advantage in breaking the K-BDHE problem: (22)
1
-
1
-
1
-
q
p
l
m
·
ϵ
2
.


### 7.2. Traceability

In this section, we prove the traceability of the proposed scheme based on thel-SDH assumption.Theorem 11.
Ifl-SDH assumption holds, then the proposed scheme is fully traceable provided that q
<
l.Proof.
Suppose that there is a PPT adversaryA who wins the traceability game with nonnegligible advantage ϵ after q key queries. Without loss of generality, assume that l
=
q
+
1. Then, we can construct a PPT simulator B that breaks l-SDH assumption with nonnegligible advantage.
B is given an instance of the l-SDH problem as follows. Let G
0 be a bilinear group of prime order p, let g
-
∈
G
0, let e
:
G
0
×
G
0
→
G
1 be a bilinear map, and let a
∈
Z
p. B is given I
N
SDH
=
(
p
,
G
0
,
G
1
,
e
,
g
-
,
g
-
a
,
…
,
g
-
a
l
) as in instance of the l-SDH problem. B’s goal is to output a pair (
c
r
,
w
r
)
∈
Z
p
∗
×
G
0 satisfying w
r
=
g
-
1
/
(
a
+
c
r
) for solving the l-SDH problem. B sets A
i
=
g
-
a
i for i
=
0,1
,
…
,
l and interacts with A in the traceability game as follows.
Setup. B randomly picks q distinct values c
1
,
…
,
c
q
∈
Z
p
∗. Let f
(
y
) be the polynomial f
(
y
)
=
∏
i
=
1
q
‍
(
y
+
c
i
). Expand f
(
y
) and write f
(
y
)
=
∑
i
=
0
q
‍
α
i
y
i, where α
0
,
α
1
,
…
,
α
q
∈
Z
p are the coefficients of the polynomial f
(
y
). B computes (23)
g
⟵
∏
i
=
0
q
A
i
α
i
=
g
-
f
a
,
g
a
⟵
∏
i
=
1
q
+
1
A
i
α
i
-
1
=
g
-
f
a
·
a
.
B randomly chooses α
,
γ
∈
Z
p and computes v
=
g
γ. For i
=
1,2
,
…
,
K, K
+
2
,
…
,
2
K, B sets g
i
=
g
(
α
i
), where K
=
3
k
=
l. B then gives A the public parameter (24)
P
K
=
g
,
g
1
,
…
,
g
K
,
g
K
+
2
,
…
,
g
2
K
,
v
∈
G
0
2
K
+
1
.
KeyQuery.
A submits (
i
d
x
,
L
) to B to request a decryption key. Assume that it is the xth query. For x
≤
q, let f
x
(
y
) be the polynomial f
x
(
y
)
=
f
(
y
)
/
(
y
+
c
x
)
=
∏
j
=
1
,
j
≠
x
q
‍
(
y
+
c
j
). Expand f
x
(
y
) and write f
x
(
y
)
=
∑
j
=
0
q
-
1
‍
β
j
y
j, where β
0
,
β
1
,
…
,
β
q
-
1
∈
Z
p. B computes (25)
σ
x
⟵
∏
j
=
0
q
-
1
A
j
β
j
=
g
-
f
x
a
=
g
-
f
a
/
a
+
c
x
=
g
1
/
a
+
c
x
.
B randomly chooses {
r
1
,
r
2
,
…
,
r
k
}
∈
Z
p. Then, it computes r
=
∑
i
=
1
k
‍
r
i
,
D
′
′
=
g
r, and D
=
σ
x
r
γ.
Finally,B computes the following: (i)
For everyi
∈
L
u
+, compute D
i
=
g
γ
c
x
α
i
σ
x
γ
r
i
′, where i
′
=
i.
(ii)
For everyi
∈
L
u
-, compute D
i
=
g
γ
c
x
α
i
σ
x
γ
r
i
′, where i
′
=
i
-
k.
(iii)
For everyi
∈
L
u
∗, compute D
i
=
g
γ
c
x
α
i
σ
x
γ
r
i
′, where i
′
=
i
-
2
k.
B responds to A with S
K
i
d
x
,
L
x as (26)
S
K
i
d
x
,
L
x
=
D
=
σ
x
r
γ
,
D
i
∣
i
∈
L
u
+
,
L
u
-
,
L
u
∗
,
D
′
=
c
x
,
D
′
′
=
g
r
.
B puts tuple (
c
x
,
i
d
x
) into T.
KeyForgery. A submits to B a decryption key S
K
∗.
Note that the distributions of PK and SK in the above game are the same as in the real game. LetΥ
A denote the event that A wins the game; that is, S
K
∗ is well-formed, and c
r
∉
{
c
1
,
c
2
,
…
,
c
q
}. The adversary’s advantage over the game is ϵ
/
2 since there is no decryption proxy used. If Υ
A does not happen, B chooses a random a random pair (
c
r
,
w
r
)
∈
Z
p
∗
×
G
0 as its solution for l-SDH problem. If Υ
A happens, B writes the polynomial f
(
y
)
=
γ
(
y
)
(
y
+
D
′
)
+
γ
-
1 for some polynomial γ
(
y
)
=
∑
i
=
0
q
-
1
‍
(
γ
i
y
i
) and some γ
-
1
∈
Z
p. Then, γ
-
1
≠
0 since f
(
y
)
=
∏
i
=
1
q
‍
(
y
+
c
i
), where c
i
∈
Z
p
∗ and D
′
∉
{
c
1
,
c
2
,
…
,
c
q
}. Thus y
+
D
′ does not divide f
(
y
). B computes the value of g
c
d
(
γ
-
1
,
p
).
Next, letΩ
SDH
(
c
r
,
w
r
) denote the event that (
c
r
,
w
r
) is a solution to the l-SDH problem. Note that when B chooses (
c
r
,
w
r
) randomly, Ω
SDH
(
c
r
,
w
r
) happens with negligible probability, say zero. B solves the l-SDH problem with probability(27)
P
r
Ω
SDH
c
r
,
w
r
=
Pr
⁡
Ω
SDH
c
r
,
w
r
∣
Υ
A
¯
·
Pr
⁡
Υ
A
¯
+
Pr
⁡
Ω
SDH
c
r
,
w
r
∣
Υ
A
∧
g
c
d
γ
-
1
,
p
≠
1
·
Pr
⁡
Υ
A
∧
g
c
d
γ
-
1
,
p
≠
1
+
Pr
⁡
Ω
SDH
c
r
,
w
r
∣
Υ
A
∧
g
c
d
γ
-
1
,
p
=
1
·
Pr
⁡
Υ
A
∧
g
c
d
γ
-
1
,
p
=
1
=
0
+
0
+
1
·
Pr
⁡
Υ
A
∧
g
c
d
γ
-
1
,
p
=
1
≤
ϵ
.Thus, B can break the l-SDH assumption with advantage ≤ ϵ.


### 7.3. Policy Privacy

When an encryptor uploads its ciphertext to the storage center, every attributej in the access policy is obfuscated as H
1
e
h
b
,
H
(
j
) with a random b using the one-way anonymous key agreement protocol [31] such that only users in possession of valid corresponding attributes are able to compute the same value. It is infeasible to guess j from H
1
e
h
b
,
H
(
j
) without having the corresponding attributes due to b which is chosen uniformly at random by the encryptor. Specifically, the storage center does not have D
′
′
′
=
H
(
j
)
β which is a secret key component owned by users whose attribute sets satisfy the access policy. Due to the secrecy property of the key agreement protocol [31], the storage center cannot compute e
(
g
b
,
H
(
j
)
β
).In token generation phase, a user computes indicesI
j
=
H
1
e
g
b
,
H
(
j
)
β for each (obfuscated) attribute j. Due to the secrecy property of the key agreement protocol, only the authorized users are able to construct indices corresponding to j. Thus, the storage center cannot generate correct indices for the attributes in the access policy. Also, even though the storage center conducts partial decryptions, the user learns nothing about the underlying access policy except that he can decrypt the ciphertext since he receives only the partially decrypted value and no more. Therefore, the proposed scheme guarantees the policy privacy against the storage center and authorized users.


## 7.1. Data Confidentiality

In this section, we reduce the chosen plaintext attack (CPA) security of the proposed scheme to a decisionalK-BDHE problem. Given an access policy W, a user with an attribute set L
⊭
W colludes with x
≤
k decryption proxies. Intuitively, this attack works successfully if L
∪
{
i
1
,
…
,
i
x
}
⊨
W. Based on the CPA security game in Section 4.2, we have the following.Theorem 7.
If a probabilistic polynomial time adversary wins the CPA security game with a nonnegligible advantage, then one can construct a simulator that distinguishes aK-DBHE tuple with a nonnegligible advantage.Proof.
Suppose that an adversaryA’s advantage for winning the game is ϵ. Then, we can construct a simulator B which solves the decisional K-BDHE problem with the advantage ϵ
/
2. The simulator B takes an input vector h
,
g
,
Y
g
,
α
,
K
,
Z, where Z is either e
(
g
,
h
)
α
K
+
1 or a random element in G
0. Then, B breaks the decisional K-BDHE problem with the advantage ϵ
/
2. Specifically, B takes a random decisional K-BDHE challenge h
,
g
,
Y
g
,
α
,
K
,
Z as input, where Z is either Z
=
e
(
g
,
h
)
α
K
+
1 or a random value.
Next,B runs the following CPA game with the role of challenger. (i)
Init. A sends an access policy W to B.
(ii)
Setup. B runs the Setup algorithm to obtain PK and chooses a random d
∈
Z
p. Then, B computes (15)
v
=
g
d
∏
j
∈
W
g
K
+
1
-
j
-
1
=
g
γ
.
B outputs the public key PK
=
g
,
Y
g
,
α
,
K
,
v
∈
G
0
2
K
+
1.
Phase 1. The adversary A submits L, where L
⊭
W. Then, there exists j
∈
L such that j
+
k
∈
W, where j
∈
{
1
,
…
,
k
}, or j
-
k
∈
W, where j
∈
{
k
+
1
,
…
,
2
k
}.
Fori
=
1
,
…
,
k, B picks k random r
i
∈
Z
p and sets r
=
r
1
+
⋯
+
r
k. Next, B randomly chooses a
,
c
∈
Z
p
∗ and computes (16)
D
=
g
d
∏
j
∈
W
g
K
+
1
-
j
-
1
r
/
a
+
c
=
g
γ
r
/
a
+
c
.Next, B computes (17)
D
i
=
g
i
d
∏
j
∈
W
g
K
+
1
-
j
+
i
-
c
·
∏
j
∈
W
g
K
+
1
-
j
-
r
i
′
/
a
+
c
,where i falls into one of the following conditions: (1) i
+
k
∈
W for all i
∈
L
+, (2) i
-
k
∈
W for all i
∈
L
-, and (3) i
∉
W for all i
∈
L
∗.
Then, eachD
i is valid such that (18)
D
i
=
g
d
∏
j
∈
W
g
K
+
1
-
j
-
1
c
α
i
+
r
i
′
/
a
+
c
=
g
γ
c
α
i
+
r
i
′
/
a
+
c
.
Challenge. B sets C
0
=
h and C
1
=
h
d and gives the challenge C
0
,
C
1
,
Z
k to A. Note that C
0
=
h
=
g
t for some t such that (19)
h
d
=
g
d
t
=
g
d
∏
j
∈
W
g
K
+
1
-
j
-
1
·
∏
j
∈
W
g
K
+
1
-
j
t
=
v
∏
j
∈
W
g
K
+
1
-
j
t
,and Z
k
=
Key if Z
=
e
(
g
,
h
)
α
(
K
+
1
).
Phase 2. Repeat Phase 1.
Guess. The adversary A outputs a guess b
′, where b
′
=
0 implies that Z
=
e
(
g
,
h
)
α
K
+
1. If b
′
=
1, then Z is a random element which indicates that P
r
B
(
h
,
g
,
Y
g
,
α
,
K
,
Z
)
=
0
=
1
/
2. Note that each decryption proxy p
i
(
r
) simulates a legal decryption key component with a random r. Specifically, the adversary A passes r as a guess of r
i
′ which is embedded in D
i, where i
∈
W. We further define a decryption proxy to model collusion attacks.Definition 8.
Given2
k decryption proxies in the security game, each decryption proxy p
i
(
r
)
=
g
γ
c
α
i
+
r
/
(
a
+
c
), where r
∈
Z
p and i
∈
{
1
,
…
,
2
k
}.Lemma 9 (collision with 1 decryption proxy).
Suppose thatA has issued q queries and there is only 1 attribute i
∉
W, where A makes l queries to p
i
(
r
). The probability that none of the queries returns a legal decryption key component of any q is 1
-
q
/
p
l.Proof.
The probability that at least one query returns an illegal decryption key component of anyq is 1
-
q
/
p. Thus, if none of the l queries succeeds, then Pr
⁡
r
≠
r
i
′
=
1
-
q
/
p
l, where r is a random number in the decryption proxy and r
i
′ is a random number in the decryption key.Lemma 10 (collision with multiple decryption proxies).
SupposeA has issued q queries and there are m attributes dissatisfying W, where A makes l queries to each decryption proxy p
i
1
(
r
1
), p
i
2
(
r
2
)
,
…
,
p
i
m
(
r
m
). The probability that none of the queries returns a legal decryption key component of any q is 1
-
1
-
q
/
p
l
m.Proof.
The probability that one decryption proxy fails isP
r
[
r
≠
r
i
′
]
=
1
-
q
/
p
l. Thus, the probability that all m decryption proxies succeed is 1
-
1
-
q
/
p
l
m.In case ofZ
=
e
(
g
,
h
)
α
(
K
+
1
), we have 3 collusion scenarios as follows.0-Collusion. If no decryption proxy is used, then A has at least ϵ
/
2 advantage in breaking the proposed scheme. Thus, B has at least the following advantage in breaking K-BDHE problem: (20)
Pr
⁡
B
h
,
g
,
Y
g
,
α
,
K
,
Z
=
0
-
1
2
≥
ϵ
2
.1-Collusion. If one decryption proxy p
i
(
r
) is used, then we have P
r
[
r
≠
r
i
′
]
=
1
-
q
/
p
l. Thus, if A has at least ϵ advantage in breaking the proposed scheme, then B has at least 1
-
q
/
p
l
ϵ
/
2 advantage in breaking the K-BDHE problem.m-Collusion. If m decryption proxies p
i
1
(
r
1
)
,
…
,
p
i
m
(
r
m
) are used, then we have (21)
Pr
⁡
r
i
j
≠
r
i
j
′
,
∃
j
≤
m
=
1
-
1
-
q
p
l
m
.Thus, if A has at least ϵ advantage in breaking the proposed scheme, then B has at least the following advantage in breaking the K-BDHE problem: (22)
1
-
1
-
1
-
q
p
l
m
·
ϵ
2
.


## 7.2. Traceability

In this section, we prove the traceability of the proposed scheme based on thel-SDH assumption.Theorem 11.
Ifl-SDH assumption holds, then the proposed scheme is fully traceable provided that q
<
l.Proof.
Suppose that there is a PPT adversaryA who wins the traceability game with nonnegligible advantage ϵ after q key queries. Without loss of generality, assume that l
=
q
+
1. Then, we can construct a PPT simulator B that breaks l-SDH assumption with nonnegligible advantage.
B is given an instance of the l-SDH problem as follows. Let G
0 be a bilinear group of prime order p, let g
-
∈
G
0, let e
:
G
0
×
G
0
→
G
1 be a bilinear map, and let a
∈
Z
p. B is given I
N
SDH
=
(
p
,
G
0
,
G
1
,
e
,
g
-
,
g
-
a
,
…
,
g
-
a
l
) as in instance of the l-SDH problem. B’s goal is to output a pair (
c
r
,
w
r
)
∈
Z
p
∗
×
G
0 satisfying w
r
=
g
-
1
/
(
a
+
c
r
) for solving the l-SDH problem. B sets A
i
=
g
-
a
i for i
=
0,1
,
…
,
l and interacts with A in the traceability game as follows.
Setup. B randomly picks q distinct values c
1
,
…
,
c
q
∈
Z
p
∗. Let f
(
y
) be the polynomial f
(
y
)
=
∏
i
=
1
q
‍
(
y
+
c
i
). Expand f
(
y
) and write f
(
y
)
=
∑
i
=
0
q
‍
α
i
y
i, where α
0
,
α
1
,
…
,
α
q
∈
Z
p are the coefficients of the polynomial f
(
y
). B computes (23)
g
⟵
∏
i
=
0
q
A
i
α
i
=
g
-
f
a
,
g
a
⟵
∏
i
=
1
q
+
1
A
i
α
i
-
1
=
g
-
f
a
·
a
.
B randomly chooses α
,
γ
∈
Z
p and computes v
=
g
γ. For i
=
1,2
,
…
,
K, K
+
2
,
…
,
2
K, B sets g
i
=
g
(
α
i
), where K
=
3
k
=
l. B then gives A the public parameter (24)
P
K
=
g
,
g
1
,
…
,
g
K
,
g
K
+
2
,
…
,
g
2
K
,
v
∈
G
0
2
K
+
1
.
KeyQuery.
A submits (
i
d
x
,
L
) to B to request a decryption key. Assume that it is the xth query. For x
≤
q, let f
x
(
y
) be the polynomial f
x
(
y
)
=
f
(
y
)
/
(
y
+
c
x
)
=
∏
j
=
1
,
j
≠
x
q
‍
(
y
+
c
j
). Expand f
x
(
y
) and write f
x
(
y
)
=
∑
j
=
0
q
-
1
‍
β
j
y
j, where β
0
,
β
1
,
…
,
β
q
-
1
∈
Z
p. B computes (25)
σ
x
⟵
∏
j
=
0
q
-
1
A
j
β
j
=
g
-
f
x
a
=
g
-
f
a
/
a
+
c
x
=
g
1
/
a
+
c
x
.
B randomly chooses {
r
1
,
r
2
,
…
,
r
k
}
∈
Z
p. Then, it computes r
=
∑
i
=
1
k
‍
r
i
,
D
′
′
=
g
r, and D
=
σ
x
r
γ.
Finally,B computes the following: (i)
For everyi
∈
L
u
+, compute D
i
=
g
γ
c
x
α
i
σ
x
γ
r
i
′, where i
′
=
i.
(ii)
For everyi
∈
L
u
-, compute D
i
=
g
γ
c
x
α
i
σ
x
γ
r
i
′, where i
′
=
i
-
k.
(iii)
For everyi
∈
L
u
∗, compute D
i
=
g
γ
c
x
α
i
σ
x
γ
r
i
′, where i
′
=
i
-
2
k.
B responds to A with S
K
i
d
x
,
L
x as (26)
S
K
i
d
x
,
L
x
=
D
=
σ
x
r
γ
,
D
i
∣
i
∈
L
u
+
,
L
u
-
,
L
u
∗
,
D
′
=
c
x
,
D
′
′
=
g
r
.
B puts tuple (
c
x
,
i
d
x
) into T.
KeyForgery. A submits to B a decryption key S
K
∗.
Note that the distributions of PK and SK in the above game are the same as in the real game. LetΥ
A denote the event that A wins the game; that is, S
K
∗ is well-formed, and c
r
∉
{
c
1
,
c
2
,
…
,
c
q
}. The adversary’s advantage over the game is ϵ
/
2 since there is no decryption proxy used. If Υ
A does not happen, B chooses a random a random pair (
c
r
,
w
r
)
∈
Z
p
∗
×
G
0 as its solution for l-SDH problem. If Υ
A happens, B writes the polynomial f
(
y
)
=
γ
(
y
)
(
y
+
D
′
)
+
γ
-
1 for some polynomial γ
(
y
)
=
∑
i
=
0
q
-
1
‍
(
γ
i
y
i
) and some γ
-
1
∈
Z
p. Then, γ
-
1
≠
0 since f
(
y
)
=
∏
i
=
1
q
‍
(
y
+
c
i
), where c
i
∈
Z
p
∗ and D
′
∉
{
c
1
,
c
2
,
…
,
c
q
}. Thus y
+
D
′ does not divide f
(
y
). B computes the value of g
c
d
(
γ
-
1
,
p
).
Next, letΩ
SDH
(
c
r
,
w
r
) denote the event that (
c
r
,
w
r
) is a solution to the l-SDH problem. Note that when B chooses (
c
r
,
w
r
) randomly, Ω
SDH
(
c
r
,
w
r
) happens with negligible probability, say zero. B solves the l-SDH problem with probability(27)
P
r
Ω
SDH
c
r
,
w
r
=
Pr
⁡
Ω
SDH
c
r
,
w
r
∣
Υ
A
¯
·
Pr
⁡
Υ
A
¯
+
Pr
⁡
Ω
SDH
c
r
,
w
r
∣
Υ
A
∧
g
c
d
γ
-
1
,
p
≠
1
·
Pr
⁡
Υ
A
∧
g
c
d
γ
-
1
,
p
≠
1
+
Pr
⁡
Ω
SDH
c
r
,
w
r
∣
Υ
A
∧
g
c
d
γ
-
1
,
p
=
1
·
Pr
⁡
Υ
A
∧
g
c
d
γ
-
1
,
p
=
1
=
0
+
0
+
1
·
Pr
⁡
Υ
A
∧
g
c
d
γ
-
1
,
p
=
1
≤
ϵ
.Thus, B can break the l-SDH assumption with advantage ≤ ϵ.


## 7.3. Policy Privacy

When an encryptor uploads its ciphertext to the storage center, every attributej in the access policy is obfuscated as H
1
e
h
b
,
H
(
j
) with a random b using the one-way anonymous key agreement protocol [31] such that only users in possession of valid corresponding attributes are able to compute the same value. It is infeasible to guess j from H
1
e
h
b
,
H
(
j
) without having the corresponding attributes due to b which is chosen uniformly at random by the encryptor. Specifically, the storage center does not have D
′
′
′
=
H
(
j
)
β which is a secret key component owned by users whose attribute sets satisfy the access policy. Due to the secrecy property of the key agreement protocol [31], the storage center cannot compute e
(
g
b
,
H
(
j
)
β
).In token generation phase, a user computes indicesI
j
=
H
1
e
g
b
,
H
(
j
)
β for each (obfuscated) attribute j. Due to the secrecy property of the key agreement protocol, only the authorized users are able to construct indices corresponding to j. Thus, the storage center cannot generate correct indices for the attributes in the access policy. Also, even though the storage center conducts partial decryptions, the user learns nothing about the underlying access policy except that he can decrypt the ciphertext since he receives only the partially decrypted value and no more. Therefore, the proposed scheme guarantees the policy privacy against the storage center and authorized users.


## 8. Conclusion

In this paper, we proposed an efficient attribute-based secure mHealth data sharing scheme with hidden policies and traceability. The proposed scheme significantly reduces storage and communication costs. The access policies are obfuscated such that not only data privacy but also policy privacy is preserved. The computational costs of users are reduced by delegating approximately 50% of the decryption operation to the more powerful storage systems. Lastly, the proposed scheme is able to trace malicious users who illegally leak their keys. Our security analysis shows that the proposed scheme is secure against chosen-ciphertext and key forgery attacks under the decisionalK-BDHE and l-SDE assumptions. We also prove that the policy privacy of the proposed scheme is preserved against the storage center and authorized users.



---

*Source: 6545873-2016-07-18.xml*