# An Efficient Solution for Hierarchical Access Control Problem in Cloud Environment

Authors: Bing-Zhe He; Chien-Ming Chen; Tsu-Yang Wu; Hung-Min Sun
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The time-bound hierarchical key assignment scheme provides a cryptographic solution for the access control problem in distributed systems (e.g., Pay-TV and cloud computing applications). Most time-bound hierarchical key assignment schemes can be divided into two types: adopting tamper-resistant devices and utilizing public values. Despite the fact that adopting tamper-resistant devices can easily resist to collusion attacks, utilizing public values is much cheaper and more suitable for cloud environment. In this paper, we proposed a new time-bound hierarchical key assignment scheme, which can effectively defeat the collusion attack. Besides, the proposed scheme utilizes public values instead of tamper-resistant devices, which will restrict user’s convenience. Compared with the previous works, our scheme requires fewer public values and has better performance.


---

## Body

## 1. Introduction

The access control problem refers to control who can access the resources in a system. Members in an organization are divided into several classes and each class has different limitations on these resources. For example, in a computer system, an administrator has the right to access all files, including the sensitive files, but a normal user just can access some common files. Nowadays the access control problem is a widespread problem in our world, especially in the distributed environment.A hierarchical key assignment scheme can provide a cryptographic solution ([1–5]) for the access control problem. In a hierarchical key assignment scheme, resources are encrypted by encrypting keys. Only the user who holds the corresponding encrypting key can access the resources. In addition, the classes will form hierarchical relations between themselves. If two classes have a relation, the user in the higher class can also access the resources in the lower class, but not vice versa. This relation is called partial-order hierarchy. In the previous example, suppose that the administrator belongs to the manager class and normal users belong to the user class. Obviously, these two classes form a hierarchical relation and the manager class has higher right than the user class. The members in the manager class can access the resources in the user class, but normal user cannot access the resources of manager class. However, in some applications such as Pay-TV systems, a user may subscribe to news and sport channels for a week or a month. When the time expires, the user cannot access the channels anymore. Hence, the key assignment scheme needs to consider not only the partial-order hierarchy but also the key update problem when a user leaves the class.The time-bound hierarchical key assignment protocol is proposed for the above problem. In the time-bound hierarchical key assignment system, the encrypting key for a class is changed as time goes by. According to the user’s subscription, the vendor generates his key information that can be used to compute the encrypting key and assigns it to the user. The key information only works in the duration of user’s subscription. On the other hand, the user cannot derive the encrypting key except in the duration of his subscription. Since the encrypting key has the time-bound property, we do not need to consider the key update problem when a user leaves the class. As the previous example, suppose that a user subscribes to the news channels in first time slot and then changes his subscription to the sport channels in fifth time slot. The key information can be used to compute the encrypting key of news channels only between first and fifth time slots. Afterwards, this key information can only be used to compute the encrypting key of sport channels.The time-bound key assignment protocols can be divided into two types: one is based on tamper-resistant devices ([6, 7]) and the other is based on public values. Tamper-resistant devices can protect the secret information and prevent the secrets from revealing. If the encrypting key is stored in the device, the user is hard to reveal the encrypting key to other users. Despite the fact that the tamper-resistant devices can defeat collusion attacks, applying the tamper-resistant devices requires higher costs and is not suitable for the cloud networks. For this reason, some researches ([8–11]) apply public values instead of tamper-resistant devices. Users can download the public values and derive the encrypting key by his key information and these values.In this paper, we propose a time-bound hierarchical key assignment scheme which is based on a bilinear pairing function. Due to the time-bound property, the user can subscribe to some classes in a certain period of time. Besides, our scheme utilizes public values instead of tamper-resistant devices. Utilizing public values is more suitable for cloud computing since cloud computing emphasizes that users can access resources anywhere through the Internet. If a cloud service requires tamper-resistant devices, this will restrict users’ convenience. On the other hand, the public values can be downloaded anywhere from the cloud. A user can download and use these public values to derive the encrypting key anywhere. Moreover, the number of public values in our scheme is independent of the length of system life time or the number of classes. Compared to the previous works, the proposed scheme has few numbers of the public values and does not need the special requirement for constructing partial-order hierarchy.The rest of the paper is organized as follows. In Sections2 and 3, we introduce previous works and present the necessary preliminaries. The proposed scheme is described in Section 4. Then we provide the performance and security analysis of the proposed scheme in Section 5. Finally, we summarize our results.


## 2. Related Work

With the rapid growth of network technology, security issues have been a matter of concern in various network environments ([12–17]) such as wireless sensor networks, social networks, and Internet of things. In this paper, we put emphasis on access control problems in cloud environment.In 1983, Akl and Taylor [1] first studied the access control problem in a hierarchy and proposed a cryptographic solution for this problem. Then, many researchers also studied this problem and proposed their solutions ([2–5]). However, these schemes do not consider that a user may belong to some classes only in a certain period of time. To solve this problem, Tzeng [8] proposed a time-bound hierarchical key assignment scheme based on Lucas function and RSA problem in 2002. Afterwards, many researchers have concentrated on proposing the time-bound key assignment schemes that either have better performance or can resist collusion attacks. These schemes can be divided into tamper-resistant devices based and public values based schemes. As the tamper-resistant device based schemes, Chien [6] presented his time-bound protocol in 2004 and his scheme is insecure against collusion attacks [18, 19]. Then Bertino et al. [7] also proposed an efficient time-bound hierarchy key management scheme which is based on elliptic curve. However, Sun et al. [20] also show that Bertino et al.’s scheme [7] is insecure against collusion attack and provided the improved scheme. As the public value based scheme, Yeh [11] proposed their public value based protocol in 2005. In 2006, Ateniese et al. [9] not only showed that Yeh’s scheme is vulnerable to collusion attacks, but also introduced two different constructions of time-bound key assignment scheme in a hierarchy. Additionally, they also proved that these schemes are practical and provable-secure. Furthermore, de Santis et al. [10] showed how to construct a provable-secure time-bound hierarchy key assignment protocol and compared their protocol with other pervious works.


## 3. Preliminaries

In this section, we introduce some preliminaries about the proposed scheme, before describing our protocol.


### 3.1. Bilinear Mapping

Suppose thatG
1 and G
2 are two cyclic groups with a prime order q, where G
1 is an additive cyclic group and G
2 is a multiplicative cyclic group. A bilinear mapping is a mapping e
^
:
G
1
×
G
1
→
G
2 with the following properties:(1)
bilinear:e
^
(
a
P
,
b
Q
)
=
e
^
(
P
,
Q
)
a
b, for all P
,
Q
∈
G
1 and all a
,
b
∈
F
q
*;
(2)
nondegenerative:e
^
(
P
,
Q
)
=
1, ∀
Q
∈
G
1
⇔
P
=
∞;
(3)
computable: there exists an efficient algorithm to computee
^
(
P
,
Q
), ∀
P
,
Q
∈
G
1.


### 3.2. Partial-Order Hierarchy

In a partial-order hierarchy, a classC
i represents a collection of some resources. Besides, there exists a binary relation “≺” which partially orders these classes. For any two classes C
i and C
j, “C
j
≺
C
i” means that C
i dominates C
j and the security level of C
i is higher than of C
j. In other words, the users of C
i can access the resources in C
j but not vice versa. For example, assume that C
1
≺
C
3
≺
C
4 and C
2 is an independent class. If a user belongs to C
4, this means that the user can access all of the resources in C
1, C
3, and C
4, but he does not have the access right of C
2. In other words, the user only holds the encrypting keys for C
1, C
3, and C
4. Moreover, we usually use a directed acyclic graph G
=
(
V
,
E
) to represent a partial-order hierarchy, where V denotes the set of classes and E denotes the set of partial-order relations.


### 3.3. Time-Bound Property

A key assignment system with the time-bound property means that the encrypting keys in a class are different as time goes by. The user can only derive the encrypting keys that are within the duration of his subscription. Assume that a user belongs toC
i from t
1 to t
2 and C
j
≺
C
i. The user can just derive the encrypting key K
i and K
j at t if and only if t
1
<
t
<
t
2. Nevertheless, he cannot derive the encrypting key at t
3 when t
3
∉
[
t
1
,
t
2
].


## 3.1. Bilinear Mapping

Suppose thatG
1 and G
2 are two cyclic groups with a prime order q, where G
1 is an additive cyclic group and G
2 is a multiplicative cyclic group. A bilinear mapping is a mapping e
^
:
G
1
×
G
1
→
G
2 with the following properties:(1)
bilinear:e
^
(
a
P
,
b
Q
)
=
e
^
(
P
,
Q
)
a
b, for all P
,
Q
∈
G
1 and all a
,
b
∈
F
q
*;
(2)
nondegenerative:e
^
(
P
,
Q
)
=
1, ∀
Q
∈
G
1
⇔
P
=
∞;
(3)
computable: there exists an efficient algorithm to computee
^
(
P
,
Q
), ∀
P
,
Q
∈
G
1.


## 3.2. Partial-Order Hierarchy

In a partial-order hierarchy, a classC
i represents a collection of some resources. Besides, there exists a binary relation “≺” which partially orders these classes. For any two classes C
i and C
j, “C
j
≺
C
i” means that C
i dominates C
j and the security level of C
i is higher than of C
j. In other words, the users of C
i can access the resources in C
j but not vice versa. For example, assume that C
1
≺
C
3
≺
C
4 and C
2 is an independent class. If a user belongs to C
4, this means that the user can access all of the resources in C
1, C
3, and C
4, but he does not have the access right of C
2. In other words, the user only holds the encrypting keys for C
1, C
3, and C
4. Moreover, we usually use a directed acyclic graph G
=
(
V
,
E
) to represent a partial-order hierarchy, where V denotes the set of classes and E denotes the set of partial-order relations.


## 3.3. Time-Bound Property

A key assignment system with the time-bound property means that the encrypting keys in a class are different as time goes by. The user can only derive the encrypting keys that are within the duration of his subscription. Assume that a user belongs toC
i from t
1 to t
2 and C
j
≺
C
i. The user can just derive the encrypting key K
i and K
j at t if and only if t
1
<
t
<
t
2. Nevertheless, he cannot derive the encrypting key at t
3 when t
3
∉
[
t
1
,
t
2
].


## 4. The Proposed Scheme

The detail of the proposed scheme is introduced in this section. The proposed scheme consists of three phases: initialization, user subscription, and encrypting key derivation. Each phase is described in the following. Then, we use a concrete example to explain our scheme. Finally, the notation is shown in the notation section.


### 4.1. Initialization

In this phase, we suppose that the vendor has already constructed a partial-order hierarchy. The system parameters are initialized as following steps.(1)
The vendor chooses an elliptic curveE over a finite field F
q and then selects a generating point P
∈
E
(
F
q
), where the order of P is n.
(2)
Afterwards, the vendor constructs a bilinear mape
^
:
G
1
×
G
1
→
G
2.
(3)
Suppose that the maximum duration of each subscription for a user isl and the system lifetime is z, where l
<
z. The system selects two random values a and b from Z
q
* and generates B
x
,
y
=
a
x
b
y
P, where x
∈
[
1
,
l
] and y
∈
[
0
,
x
].
(4)
For every classi, the vendor randomly generates g
i and h
i, where g
i
h
i
≡
1
mod
⁡
n. Then, the vendor computes the public values r
i
,
j
=
h
i
g
j
mod
⁡
n if and only if C
j
≺
C
i.
(5)
Finally, the public system parameters are{
E
,
G
1
,
G
2
,
P
,
e
^
,
H
} and the vendor keeps {
a
,
b
,
g
i
,
h
i
} in secret. Besides, the encrypting key is computed by K
i
,
t
=
e
^
(
P
,
P
)
g
i
a
t
b
z
-
t.When completing these steps, the vendor publishesr
i
,
j and B
x
,
y on an authenticated board. These public values can be downloaded through the Internet and used to compute the encrypting key.


### 4.2. User Subscription

In this phase, the system generates the key information for a user according to his subscription request. Then this key information is issued to the user through a secure channel. If a user subscribes classC
i from t
1 to t
2, the key information K
i
,
t
1
,
t
2 can be computed by K
i
,
t
1
,
t
2
=
g
1
a
t
1
b
z
-
t
2
P.Afterwards, the user usesK
i
,
t
1
,
t
2 and B
x
,
y to compute the encrypting key K
i
,
t at time slot t if t
∈
[
t
1
,
t
2
]. Moreover, if C
j and C
k are dominated by C
i (C
j
,
C
k
≺
C
i), the user can use K
i
,
t
1
,
t
2, B
x
,
y, and r
i
,
j (or r
i
,
k) to compute the encrypting key of class C
j (or C
k) from t
1 to t
2. Otherwise, the system has to issue K
j
,
t
1
,
t
2 and K
k
,
t
1
,
t
2 to the user.


### 4.3. Encrypting Key Derivation

In this phase, we show how a user derives an encrypting key. This phase can be divided into two cases: the class which is not dominated by any other classes and the class which is dominated by some other classes.Case 1.
Suppose that a user subscribes to classC
i which is not dominated by other classes. The user can use K
i
,
t
1
,
t
2 and B
x
,
y to compute K
i
,
t, where t
∈
[
t
1
,
t
2
] and t
1
+
x
=
t
=
t
2
-
y. The encrypting key for the class C
i at t can be computed as follows:
(1)
K
i
,
t
=
e
(
K
i
,
t
1
,
t
2
,
B
x
,
y
)
.Case 2.
Suppose that the user subscribes toC
i and C
j is dominated by C
i (C
j
≺
C
i). In order to derive the encrypting key for C
j, the user first computes Q
=
K
i
,
t
1
,
t
2
×
r
i
,
j. Then, the encrypting key for C
j can be computed as follows:
(2)
K
j
,
t
=
e
^
(
Q
,
B
x
,
y
)
.Now, we show the correctness of equations in both cases. The temporal encrypting key for classC
i in time slot t is K
i
,
t
=
g
i
a
t
b
z
-
t, where t
1
+
x
=
t
=
t
2
-
y.The following is the correctness of Case1:
(3)
K
i
,
t
=
e
^
(
K
i
,
t
1
,
t
2
,
B
x
,
y
)
=
e
^
(
g
i
a
t
1
b
z
-
t
2
P
,
a
x
b
y
P
)
=
e
^
(
P
,
P
)
g
i
a
t
1
+
x
b
z
-
t
2
+
y
=
e
^
(
P
,
P
)
g
i
a
t
b
z
-
t
.The correctness of Case2 is shown as follows:
(4)
K
j
,
t
=
e
^
(
K
i
,
t
1
,
t
2
×
r
i
,
j
,
B
x
,
y
)
=
e
^
(
g
i
a
t
1
b
z
-
t
2
P
×
h
i
g
j
,
a
x
b
y
P
)
=
e
^
(
g
j
a
t
1
b
z
-
t
2
P
,
a
x
b
y
P
)
=
e
^
(
P
,
P
)
g
j
a
t
1
+
x
b
z
-
t
2
+
y
=
e
^
(
P
,
P
)
g
j
a
t
b
z
-
t
.


### 4.4. Example

Here, we use an example to describe the proposed scheme. Suppose that system lifetime is 70 and the maximum duration of each subscription is 5. Therefore, we setz to be 70 and l to be 5 here. As shown in Figure 1, the partial-order hierarchy has five classes C
1 to C
5. Besides, C
1 dominates C
2, C
3, and C
4. The vendor generates random values g
i for each class and computes r
i
,
j
=
h
i
g
j
mod
⁡
n if C
i dominates C
j. In this example, the public values r
i
,
j are r
1,2, r
1,3, r
1,4, r
2,4, and r
3,4. Then, the vendor publishes {
E
,
G
1
,
G
2
,
P
,
e
^
,
H
} and keeps {
a
,
b
,
h
i
,
g
i
} in secret, where E is over F
q, a
,
b
∈
Z
p
*, e
^
:
G
1
×
G
1
→
G
2 and P is a generating point with order n. Moreover, the public value B
x
,
y is shown as follows:
(5)
B
x
,
y
=
{
B
1,0
,
B
1,1
,
0000
B
2,0
,
B
2,1
,
B
2,2
,
0000
B
3,0
,
B
3,1
,
B
3,2
,
B
3,3
,
0000
B
4,0
,
B
4,1
,
B
4,2
,
B
4,3
,
B
4,4
,
0000
B
5,0
,
B
5,1
,
B
5,2
,
B
5,3
,
B
5,4
,
B
5,5
}
,
where B
x
,
y
=
a
x
b
y
P, x
∈
[
1,5
] and y
∈
[
0
,
x
].Figure 1
An example for the proposed scheme.If a user subscribes toC
2 and C
5 from t
1 to t
2, then he will hold the public parameters {
E
,
P
,
G
1
,
G
2
,
e
^
,
H
}, K
2
,
t
1
,
t
2, and K
5
,
t
1
,
t
2. Now suppose the user desires to access the resources in C
2 at time slot t and t
1
+
2
=
t
=
t
2
-
3. The encrypting key K
2
,
t can be computed as follows:
(6)
K
2
,
t
=
e
^
(
g
2
a
t
1
b
z
-
t
2
P
,
B
2,3
)
=
e
^
(
g
2
a
t
1
b
z
-
t
2
P
,
a
2
b
3
P
)
=
e
^
(
P
,
P
)
g
2
a
t
1
+
2
b
z
-
t
2
+
3
=
e
^
(
P
,
P
)
g
2
a
t
b
z
-
t
=
K
2
,
t
.In a similar way, the temporal key ofC
5 at t can be computed by K
5
,
t
=
e
^
(
g
5
a
t
1
b
z
-
t
2
P
,
B
2,3
).Now assume that the user desires to computeK
4
,
t and t
1
+
4
=
t
=
t
2
-
1. The encrypting key K
4
,
t can be computed by the following:
(7)
K
4
,
t
=
e
^
(
g
2
a
t
1
b
z
-
t
2
P
×
h
2
g
4
,
B
4,1
)
=
e
^
(
g
4
a
t
1
b
z
-
t
2
P
,
a
4
b
1
P
)
=
e
^
(
P
,
P
)
g
4
a
t
1
+
4
b
z
-
t
2
+
1
=
e
^
(
P
,
P
)
g
4
a
t
b
z
-
t
=
K
4
,
t
.


## 4.1. Initialization

In this phase, we suppose that the vendor has already constructed a partial-order hierarchy. The system parameters are initialized as following steps.(1)
The vendor chooses an elliptic curveE over a finite field F
q and then selects a generating point P
∈
E
(
F
q
), where the order of P is n.
(2)
Afterwards, the vendor constructs a bilinear mape
^
:
G
1
×
G
1
→
G
2.
(3)
Suppose that the maximum duration of each subscription for a user isl and the system lifetime is z, where l
<
z. The system selects two random values a and b from Z
q
* and generates B
x
,
y
=
a
x
b
y
P, where x
∈
[
1
,
l
] and y
∈
[
0
,
x
].
(4)
For every classi, the vendor randomly generates g
i and h
i, where g
i
h
i
≡
1
mod
⁡
n. Then, the vendor computes the public values r
i
,
j
=
h
i
g
j
mod
⁡
n if and only if C
j
≺
C
i.
(5)
Finally, the public system parameters are{
E
,
G
1
,
G
2
,
P
,
e
^
,
H
} and the vendor keeps {
a
,
b
,
g
i
,
h
i
} in secret. Besides, the encrypting key is computed by K
i
,
t
=
e
^
(
P
,
P
)
g
i
a
t
b
z
-
t.When completing these steps, the vendor publishesr
i
,
j and B
x
,
y on an authenticated board. These public values can be downloaded through the Internet and used to compute the encrypting key.


## 4.2. User Subscription

In this phase, the system generates the key information for a user according to his subscription request. Then this key information is issued to the user through a secure channel. If a user subscribes classC
i from t
1 to t
2, the key information K
i
,
t
1
,
t
2 can be computed by K
i
,
t
1
,
t
2
=
g
1
a
t
1
b
z
-
t
2
P.Afterwards, the user usesK
i
,
t
1
,
t
2 and B
x
,
y to compute the encrypting key K
i
,
t at time slot t if t
∈
[
t
1
,
t
2
]. Moreover, if C
j and C
k are dominated by C
i (C
j
,
C
k
≺
C
i), the user can use K
i
,
t
1
,
t
2, B
x
,
y, and r
i
,
j (or r
i
,
k) to compute the encrypting key of class C
j (or C
k) from t
1 to t
2. Otherwise, the system has to issue K
j
,
t
1
,
t
2 and K
k
,
t
1
,
t
2 to the user.


## 4.3. Encrypting Key Derivation

In this phase, we show how a user derives an encrypting key. This phase can be divided into two cases: the class which is not dominated by any other classes and the class which is dominated by some other classes.Case 1.
Suppose that a user subscribes to classC
i which is not dominated by other classes. The user can use K
i
,
t
1
,
t
2 and B
x
,
y to compute K
i
,
t, where t
∈
[
t
1
,
t
2
] and t
1
+
x
=
t
=
t
2
-
y. The encrypting key for the class C
i at t can be computed as follows:
(1)
K
i
,
t
=
e
(
K
i
,
t
1
,
t
2
,
B
x
,
y
)
.Case 2.
Suppose that the user subscribes toC
i and C
j is dominated by C
i (C
j
≺
C
i). In order to derive the encrypting key for C
j, the user first computes Q
=
K
i
,
t
1
,
t
2
×
r
i
,
j. Then, the encrypting key for C
j can be computed as follows:
(2)
K
j
,
t
=
e
^
(
Q
,
B
x
,
y
)
.Now, we show the correctness of equations in both cases. The temporal encrypting key for classC
i in time slot t is K
i
,
t
=
g
i
a
t
b
z
-
t, where t
1
+
x
=
t
=
t
2
-
y.The following is the correctness of Case1:
(3)
K
i
,
t
=
e
^
(
K
i
,
t
1
,
t
2
,
B
x
,
y
)
=
e
^
(
g
i
a
t
1
b
z
-
t
2
P
,
a
x
b
y
P
)
=
e
^
(
P
,
P
)
g
i
a
t
1
+
x
b
z
-
t
2
+
y
=
e
^
(
P
,
P
)
g
i
a
t
b
z
-
t
.The correctness of Case2 is shown as follows:
(4)
K
j
,
t
=
e
^
(
K
i
,
t
1
,
t
2
×
r
i
,
j
,
B
x
,
y
)
=
e
^
(
g
i
a
t
1
b
z
-
t
2
P
×
h
i
g
j
,
a
x
b
y
P
)
=
e
^
(
g
j
a
t
1
b
z
-
t
2
P
,
a
x
b
y
P
)
=
e
^
(
P
,
P
)
g
j
a
t
1
+
x
b
z
-
t
2
+
y
=
e
^
(
P
,
P
)
g
j
a
t
b
z
-
t
.


## 4.4. Example

Here, we use an example to describe the proposed scheme. Suppose that system lifetime is 70 and the maximum duration of each subscription is 5. Therefore, we setz to be 70 and l to be 5 here. As shown in Figure 1, the partial-order hierarchy has five classes C
1 to C
5. Besides, C
1 dominates C
2, C
3, and C
4. The vendor generates random values g
i for each class and computes r
i
,
j
=
h
i
g
j
mod
⁡
n if C
i dominates C
j. In this example, the public values r
i
,
j are r
1,2, r
1,3, r
1,4, r
2,4, and r
3,4. Then, the vendor publishes {
E
,
G
1
,
G
2
,
P
,
e
^
,
H
} and keeps {
a
,
b
,
h
i
,
g
i
} in secret, where E is over F
q, a
,
b
∈
Z
p
*, e
^
:
G
1
×
G
1
→
G
2 and P is a generating point with order n. Moreover, the public value B
x
,
y is shown as follows:
(5)
B
x
,
y
=
{
B
1,0
,
B
1,1
,
0000
B
2,0
,
B
2,1
,
B
2,2
,
0000
B
3,0
,
B
3,1
,
B
3,2
,
B
3,3
,
0000
B
4,0
,
B
4,1
,
B
4,2
,
B
4,3
,
B
4,4
,
0000
B
5,0
,
B
5,1
,
B
5,2
,
B
5,3
,
B
5,4
,
B
5,5
}
,
where B
x
,
y
=
a
x
b
y
P, x
∈
[
1,5
] and y
∈
[
0
,
x
].Figure 1
An example for the proposed scheme.If a user subscribes toC
2 and C
5 from t
1 to t
2, then he will hold the public parameters {
E
,
P
,
G
1
,
G
2
,
e
^
,
H
}, K
2
,
t
1
,
t
2, and K
5
,
t
1
,
t
2. Now suppose the user desires to access the resources in C
2 at time slot t and t
1
+
2
=
t
=
t
2
-
3. The encrypting key K
2
,
t can be computed as follows:
(6)
K
2
,
t
=
e
^
(
g
2
a
t
1
b
z
-
t
2
P
,
B
2,3
)
=
e
^
(
g
2
a
t
1
b
z
-
t
2
P
,
a
2
b
3
P
)
=
e
^
(
P
,
P
)
g
2
a
t
1
+
2
b
z
-
t
2
+
3
=
e
^
(
P
,
P
)
g
2
a
t
b
z
-
t
=
K
2
,
t
.In a similar way, the temporal key ofC
5 at t can be computed by K
5
,
t
=
e
^
(
g
5
a
t
1
b
z
-
t
2
P
,
B
2,3
).Now assume that the user desires to computeK
4
,
t and t
1
+
4
=
t
=
t
2
-
1. The encrypting key K
4
,
t can be computed by the following:
(7)
K
4
,
t
=
e
^
(
g
2
a
t
1
b
z
-
t
2
P
×
h
2
g
4
,
B
4,1
)
=
e
^
(
g
4
a
t
1
b
z
-
t
2
P
,
a
4
b
1
P
)
=
e
^
(
P
,
P
)
g
4
a
t
1
+
4
b
z
-
t
2
+
1
=
e
^
(
P
,
P
)
g
4
a
t
b
z
-
t
=
K
4
,
t
.


## 5. Analysis

In this section, we not only analyze the security and performance of the proposed scheme but also discuss the applications for the time-bound key assignment scheme in a hierarchy. Compared with previous works, users do not need large storage capacity and perform many times of decryption, and our scheme has fewer broadcasting messages over the network.


### 5.1. Security against Possible Attacks

In the following, the security analysis will be divided into two parts: the security of key information and the security of encrypting key. For convenience, we first define two mathematical assumptions as follows.(i)
Discrete logarithm assumption: givenP
,
a
P
∈
G
1 for a
∈
F
q
*, no probabilistic polynomial-time algorithm can compute the value a.
(ii)
Computational Diffie-Hellman (CDH) assumption: givenP
,
a
P
,
b
P
∈
G
1 for a
,
b
∈
F
q
*, no probabilistic polynomial-time algorithm can compute a
b
P
∈
G
1.


#### 5.1.1. Security of Key Information

Now, we consider the two types of attackers: outside and inside attackers.Lemma 1.
Under the computational Diffie-Hellman (CDH) assumption, any outside attackerA cannot compute the key information of some classes in the proposed scheme even if A has obtained all public information r
i
,
j
=
h
i
g
j and B
x
,
y
=
a
x
b
y
P.Proof.
Without loss of generality, we assume thatA wants to compute the key information K
i
,
t
1
,
t
2
=
g
i
a
t
1
b
z
-
t
2
P of class C
i from t
1 to t
2. Since g
i and h
j are secret values held by vendor, A cannot obtain the individual values g
i and h
j from r
i
,
j. Meanwhile, attacker A cannot obtain the values a
x and b
y under the CDH assumption. Hence, any outside attacker is infeasible to compute key information of some classes in the proposed scheme.Lemma 2.
In the proposed scheme, any inside attackers (malicious subscribers) cannot compute unauthorized key information of some class.Proof.
Without loss of generality, we consider the following two cases to prove this lemma.
Case I. We assume that a subscriber A in class C
j from t
1 to t
2 tries to compute unauthorized key information K
i
,
t
1
,
t
2of class C
i for some index i and C
j
⊀
C
i. If A wants to compute K
i
,
t
1
,
t
2, he must find a value r
′
=
g
i
h
j such that r
′
·
K
j
,
t
1
,
t
2
=
(
g
i
·
h
j
)
·
g
j
a
t
1
b
z
-
t
2
P
=
K
i
,
t
1
,
t
2. Since g
i and h
j are secret values held by vendor, A cannot compute the value r
′
=
g
i
h
j. Thus, it is infeasible to compute unauthorized key information K
i
,
t
1
,
t
2 from K
j
,
t
1
,
t
2 for the case C
j
⊀
C
i.
Case II. We assume that a subscriber A in class C
j from t
1 to t
2 tries to compute unauthorized key information K
i
,
t
1
,
t
2of class C
i, where C
j
≺
C
i. By similar way to Case I, A must find a value r
′ such that r
′
·
K
j
,
t
1
,
t
2
=
K
i
,
t
1
,
t
2. Although A owns the value r
i
,
j
=
h
i
g
j, he still cannot compute r
′
=
g
i
h
j by the same reason in Case I. Thus, it is infeasible to compute K
i
,
t
1
,
t
2 from K
j
,
t
1
,
t
2 for the case C
j
≺
C
i.Lemma 3.
In the proposed scheme, any inside attackers (malicious subscribers) cannot collude to compute unauthorized key information in some class.Proof.
Without loss of generality, we consider the following two cases to prove this lemma.
Case I. We assume that two subscribers A and B collude to compute the unauthorized key information K
i
,
t
1
,
t
2in class C
i from t
1 to t
2, where A subscribes to C
j from t
1 to t
2 and B subscribes to C
k from t
1 to t
2 with C
j
≺
C
i, C
k
≺
C
i, and C
j
⊀
C
k. As mentioned in Lemma 2, two malicious subscribers must find a value r
′
=
g
i
h
j such that r
′
·
K
j
,
t
1
,
t
2
=
K
i
,
t
1
,
t
2 or a value r
′′
=
g
i
h
k such that r
′′
·
K
k
,
t
1
,
t
2
=
K
i
,
t
1
,
t
2. Even if they have r
i
,
j
=
h
i
g
j and r
i
,
k
=
h
i
g
k, they still cannot compute r
′ and r
′′. Since g
i and h
j are secret values held by vendor, they cannot obtain the individual values g
i and h
j. Thus, it is infeasible to compute K
i
,
t
1
,
t
2 from t
1 to t
2 with C
j
≺
C
i, C
k
≺
C
i, and C
j
⊀
C
k.
Case II. We assume that three subscribers A, B, and C collude to compute the unauthorized key information K
j
,
t
2
,
t
3in class C
j from t
2 to t
3, where A subscribes to C
i from t
1 to t
2, B subscribes to C
j from t
3 to t
4, and C subscribes to C
k from t
5 to t
6 with C
k
≺
C
j
≺
C
i and t
5
≤
t
2
<
t
3
≤
t
6. If they want to compute K
j
,
t
2
,
t
3
=
g
j
a
t
2
b
z
-
t
3
P, they must find the two values a
t
2
-
t
3 and b
t
3
-
t
4 such that a
t
2
-
t
3
·
b
t
3
-
t
4
·
K
j
,
t
3
,
t
4
=
g
j
a
t
2
b
z
-
t
3
P. However, it is infeasible to find a
t
2
-
t
3 and b
t
3
-
t
4 from K
i
,
t
1
,
t
2, K
j
,
t
3
,
t
4, and K
i
,
t
5
,
t
6under the discrete logarithm and the computational Diffie-Hellman assumptions.By Lemmas1–3, we can obtain Theorem 4.Theorem 4.
Under the discrete logarithm and the computational Diffie-Hellman assumptions, any attackers (including inside and outside) cannot compute the unauthorized key information of some classC
i in the proposed scheme.


#### 5.1.2. Security of Temporal Encryption Key

The security of temporal encryption key is relying on the security of key information. Hence, we have the following result.Theorem 5.
Under the discrete logarithm and the computational Diffie-Hellman assumptions, any attacker (including inside and outside) cannot compute the unauthorized temporal encryption key to access some classC
i in the proposed scheme.


### 5.2. Performance Evaluation

The performance of our scheme is evaluated in terms of storage requirements and computation costs. The storage requirements consist of three parts: private parameters, public values, and key information. These public values, includingB
x
,
y, r
i
,
j, and {
E
,
P
,
G
1
,
G
2
,
e
^
,
H
}, are published on an authentic board. Since {
E
,
P
,
G
1
,
G
2
,
e
^
,
H
} does not affect the storage complexity, we only discuss B
x
,
y and r
i
,
j. All users can download and store these public values. Then, a user can use his key information and these public values to compute the encrypting key for accessing the resources. The private parameters are security parameters in the proposed scheme and are kept secret in the server. The vendor uses these private parameters to generate all key information and encrypting keys. The private parameters include g
i, a, and b. Finally, the key information is generated according to a user’s subscription.Table1 shows the comparison of storage requirements between our scheme and other previous works. In the table, |
T
| means the system lifetime and the maximum duration of each subscription for a user is |
T
^
|. We also denote the number of edges and classes in G by |
E
| and |
V
|.Table 1
The space complexity.
Scheme
Public value
Private parameters
Key information
Ateniese et al. [9] (symmetric)
O
(
|
V
|
2
|
T
|
3
)
O
(
|
V
|
|
T
|
)
O
(
C
)
Ateniese et al. [9] (pairing)
O
(
|
V
|
2
)
O
(
|
V
|
|
T
|
)
O
(
|
T
^
|
)
Tzeng [8]
O
(
|
V
|
)
O
(
|
V
|
+
|
T
|
)
O
(
C
)
Bertino et al. [7]
O
(
|
E
|
)
O
(
|
V
|
)
O
(
C
)
Our scheme
O
(
|
T
^
|
2
+
|
E
|
)
O
(
|
E
|
+
|
V
|
)
O
(
C
)In the proposed scheme, the vendor randomly selects secret valuesg
i for each class in the partial-order hierarchy, where g
i can be used to generate K
i and K
i
,
t
1
,
t
2. Therefore, the space complexity of the private parameters in the server side is O
(
|
V
|
). Now, we consider the space complexity of the public values in the client side. The public values in our scheme are B
x
,
y and r
i
,
j. Since the maximum duration of each subscription for a user is |
T
^
|, the number of B
x
,
y is equal to (
|
T
^
|
(
|
T
^
|
+
3
)
)
/
2 and the number of r
i
,
j is |
E
|. Consequently, the space complexity of public values is O
(
|
T
^
|
2
+
|
E
|
). In fact, the storage requirements in our protocol are irrelevant to |
T
|. Otherwise, if the storage requirements are related to |
T
|, the space complexity will rise dramatically when |
T
| is very large. Compared to other schemes (as shown in Table 1), our scheme has better performance on the space complexity and the space complexity is irrelevant to |
T
|. Although the number of public values in Bertino et al.’s scheme [7] is fewer than in our scheme, Bertino et al.’s protocol requires tamper-resistant devices, which require extra costs in the deployment phase and are not suitable for cloud computing.The number of key information in our scheme depends on partial-order hierarchy and the number of classes which a user subscribes to. After a user registers to the system, the server will issue some key information to the user. Unlike some works ([9, 21]) which require that a user only belongs to one class, our scheme allows that a user can subscribe to many classes. The worst case is that every class is irrelevant to the other classes. In this case, the space complexity of the key information for a user is O
(
|
V
|
). However, generally, the number of key information for a user is equal to a constant number.We use a concrete example to show the space requirements for the proposed scheme. First, we suppose that each time slot is one day. Then, we set the system lifetime to be 10 years (z
=
1
×
365
×
10
=
3650) and the maximum duration of each subscription for a user is one month (l
=
1
×
30
=
30). Finally, we assume that there are 250 channels in the system. To put it simply, we set |
V
| and |
E
| to be both equal to 300 in the partial-order hierarchy. According to the previous analysis, the space requirements for the public values are related to the number of B
x
,
y and r
i
,
j. Since the number of B
x
,
y is equal to 495 and the number of r
i
,
j is 300, we can compute that the space requirements for the public values are (
495
+
300
)
×
160
bits
≅
16 KB. The space requirement for the private parameters depends on the number of g
i. Hence the space complexity for the private parameters is equal to 300
×
160
bits
≅
6 KB. Finally, the size of each key information is 160 bits.Now, we consider the computation cost of encrypting key derivation. In our scheme, a user only computes two pairing operations at most when he derives the encrypting key. In [22], the results show that the computation cost of pairing operation for a smartphone (HTC Desire HD A9191, Android 2.2) is affordable. Therefore, it is feasible that our scheme can be executed on low-power devices such as phone and set-top box.


### 5.3. Application

Cloud computing means that applications migrate from local PCs to Internet and sometimes is referred to as Software as a Service (SaaS) [23, 24]. Users can obtain the computing and storage capacities through Internet. Users pay for the network traffic or CPU utilization time instead of paying for software. When a cloud is only made available to some specific members in an organization, this cloud is called private cloud and only authorized users can access the cloud. For example, enterprises usually construct private data storage service for the employees.Since security threats can influence the development of cloud computing, many security issues are discussed [25], especially the access control problem. In this section, we introduce two examples, data storage service and video-on-demand (VoD) service, and explain the access control problem in both examples. First application, cloud storage service, allows users to store their files on the remote servers and share their files with other users. Obviously, enterprises can gain great benefits from cloud storage services. However, enterprises always construct their own private cloud services instead of public cloud services because of the privacy and security consideration. In an enterprise or a government, data are always classified into several classes, for example, C
1 to C
4, and members are also categorized into these classes. Assume that C
1
≺
C
2
≺
C
3
≺
C
4, where C
1
≺
C
2 means that a user which belongs to C
2 can access the data in C
1 and C
2. In this case, a user which belongs to C
1 cannot access the data in the C
2, C
3, and C
4. Therefore, we can apply a key assignment scheme to solve the access control problem. A key assignment scheme can distribute encrypting keys to each member according to their access rights in the organization. Unfortunately, a user may only subscribe to some classes for a certain period of time. Traditional key assignment protocol cannot satisfy the time-bound requirement, but the proposed scheme can solve this problem easily. Besides, utilizing public values is more suitable for cloud computing than adopting tamper-resistant devices. Cloud computing claims that users can access the resources anywhere without any limitations, but adopting tamper-resistant devices in cloud services will restrict users’ convenience. We use an example to explain how to apply the proposed scheme to enhance the cloud service. For example, an employee may become an agent of his manager when his manager takes a vacation. Suppose that the manager belongs to C
3 and the employee belongs to C
1. In addition, we also assume that the manger is on vacation from t
5 to t
8. Hence, the manager only needs to escalate the privilege of his agent into C
3 when he is on a vacation (t
5 to t
8) and our time-bound protocol can easily achieve this requirement. The manager just gives the agent the key information, K
3
,
t
5
,
t
8. This means that the agent can only access the data which belong to C
3 from t
5 to t
8. On the other hand, the agent cannot derivate the encrypting key of C
3 except for the specific periods of time (t
5 to t
8).The second application is the video-on-demand (VoD) system. Recently, many researchers discuss how to utilize cloud services to support large-scale Internet-based applications such as video-on-demand (VoD) [26, 27]. In VoD systems, users can watch video content on demand. Video content can be either streamed or downloaded through a set-top box, a computer, or a mobile device. Users can subscribe to the content that they like and access the content in the duration of subscription. Video content is always encrypted in VoD systems and users must use his encrypting key to access the content. In addition, a user usually subscribes to a program only for a limited period such as a week or a month. Beyond the duration of subscription, users are not allowed to access the content. The proposed time-bound protocol can be easily deployed into VoD systems to manage the users’ subscription. In the initial phase, the vender organizes all contents into several classes and constructs a partial-order hierarchy. For every class, the encrypting key will be used to protect the content and be changed as time goes by. A user in the system will obtain some key information according to his subscription. Finally, the user can compute the correct encrypting key through his key information and public values to access the encrypted contents.


## 5.1. Security against Possible Attacks

In the following, the security analysis will be divided into two parts: the security of key information and the security of encrypting key. For convenience, we first define two mathematical assumptions as follows.(i)
Discrete logarithm assumption: givenP
,
a
P
∈
G
1 for a
∈
F
q
*, no probabilistic polynomial-time algorithm can compute the value a.
(ii)
Computational Diffie-Hellman (CDH) assumption: givenP
,
a
P
,
b
P
∈
G
1 for a
,
b
∈
F
q
*, no probabilistic polynomial-time algorithm can compute a
b
P
∈
G
1.


### 5.1.1. Security of Key Information

Now, we consider the two types of attackers: outside and inside attackers.Lemma 1.
Under the computational Diffie-Hellman (CDH) assumption, any outside attackerA cannot compute the key information of some classes in the proposed scheme even if A has obtained all public information r
i
,
j
=
h
i
g
j and B
x
,
y
=
a
x
b
y
P.Proof.
Without loss of generality, we assume thatA wants to compute the key information K
i
,
t
1
,
t
2
=
g
i
a
t
1
b
z
-
t
2
P of class C
i from t
1 to t
2. Since g
i and h
j are secret values held by vendor, A cannot obtain the individual values g
i and h
j from r
i
,
j. Meanwhile, attacker A cannot obtain the values a
x and b
y under the CDH assumption. Hence, any outside attacker is infeasible to compute key information of some classes in the proposed scheme.Lemma 2.
In the proposed scheme, any inside attackers (malicious subscribers) cannot compute unauthorized key information of some class.Proof.
Without loss of generality, we consider the following two cases to prove this lemma.
Case I. We assume that a subscriber A in class C
j from t
1 to t
2 tries to compute unauthorized key information K
i
,
t
1
,
t
2of class C
i for some index i and C
j
⊀
C
i. If A wants to compute K
i
,
t
1
,
t
2, he must find a value r
′
=
g
i
h
j such that r
′
·
K
j
,
t
1
,
t
2
=
(
g
i
·
h
j
)
·
g
j
a
t
1
b
z
-
t
2
P
=
K
i
,
t
1
,
t
2. Since g
i and h
j are secret values held by vendor, A cannot compute the value r
′
=
g
i
h
j. Thus, it is infeasible to compute unauthorized key information K
i
,
t
1
,
t
2 from K
j
,
t
1
,
t
2 for the case C
j
⊀
C
i.
Case II. We assume that a subscriber A in class C
j from t
1 to t
2 tries to compute unauthorized key information K
i
,
t
1
,
t
2of class C
i, where C
j
≺
C
i. By similar way to Case I, A must find a value r
′ such that r
′
·
K
j
,
t
1
,
t
2
=
K
i
,
t
1
,
t
2. Although A owns the value r
i
,
j
=
h
i
g
j, he still cannot compute r
′
=
g
i
h
j by the same reason in Case I. Thus, it is infeasible to compute K
i
,
t
1
,
t
2 from K
j
,
t
1
,
t
2 for the case C
j
≺
C
i.Lemma 3.
In the proposed scheme, any inside attackers (malicious subscribers) cannot collude to compute unauthorized key information in some class.Proof.
Without loss of generality, we consider the following two cases to prove this lemma.
Case I. We assume that two subscribers A and B collude to compute the unauthorized key information K
i
,
t
1
,
t
2in class C
i from t
1 to t
2, where A subscribes to C
j from t
1 to t
2 and B subscribes to C
k from t
1 to t
2 with C
j
≺
C
i, C
k
≺
C
i, and C
j
⊀
C
k. As mentioned in Lemma 2, two malicious subscribers must find a value r
′
=
g
i
h
j such that r
′
·
K
j
,
t
1
,
t
2
=
K
i
,
t
1
,
t
2 or a value r
′′
=
g
i
h
k such that r
′′
·
K
k
,
t
1
,
t
2
=
K
i
,
t
1
,
t
2. Even if they have r
i
,
j
=
h
i
g
j and r
i
,
k
=
h
i
g
k, they still cannot compute r
′ and r
′′. Since g
i and h
j are secret values held by vendor, they cannot obtain the individual values g
i and h
j. Thus, it is infeasible to compute K
i
,
t
1
,
t
2 from t
1 to t
2 with C
j
≺
C
i, C
k
≺
C
i, and C
j
⊀
C
k.
Case II. We assume that three subscribers A, B, and C collude to compute the unauthorized key information K
j
,
t
2
,
t
3in class C
j from t
2 to t
3, where A subscribes to C
i from t
1 to t
2, B subscribes to C
j from t
3 to t
4, and C subscribes to C
k from t
5 to t
6 with C
k
≺
C
j
≺
C
i and t
5
≤
t
2
<
t
3
≤
t
6. If they want to compute K
j
,
t
2
,
t
3
=
g
j
a
t
2
b
z
-
t
3
P, they must find the two values a
t
2
-
t
3 and b
t
3
-
t
4 such that a
t
2
-
t
3
·
b
t
3
-
t
4
·
K
j
,
t
3
,
t
4
=
g
j
a
t
2
b
z
-
t
3
P. However, it is infeasible to find a
t
2
-
t
3 and b
t
3
-
t
4 from K
i
,
t
1
,
t
2, K
j
,
t
3
,
t
4, and K
i
,
t
5
,
t
6under the discrete logarithm and the computational Diffie-Hellman assumptions.By Lemmas1–3, we can obtain Theorem 4.Theorem 4.
Under the discrete logarithm and the computational Diffie-Hellman assumptions, any attackers (including inside and outside) cannot compute the unauthorized key information of some classC
i in the proposed scheme.


### 5.1.2. Security of Temporal Encryption Key

The security of temporal encryption key is relying on the security of key information. Hence, we have the following result.Theorem 5.
Under the discrete logarithm and the computational Diffie-Hellman assumptions, any attacker (including inside and outside) cannot compute the unauthorized temporal encryption key to access some classC
i in the proposed scheme.


## 5.1.1. Security of Key Information

Now, we consider the two types of attackers: outside and inside attackers.Lemma 1.
Under the computational Diffie-Hellman (CDH) assumption, any outside attackerA cannot compute the key information of some classes in the proposed scheme even if A has obtained all public information r
i
,
j
=
h
i
g
j and B
x
,
y
=
a
x
b
y
P.Proof.
Without loss of generality, we assume thatA wants to compute the key information K
i
,
t
1
,
t
2
=
g
i
a
t
1
b
z
-
t
2
P of class C
i from t
1 to t
2. Since g
i and h
j are secret values held by vendor, A cannot obtain the individual values g
i and h
j from r
i
,
j. Meanwhile, attacker A cannot obtain the values a
x and b
y under the CDH assumption. Hence, any outside attacker is infeasible to compute key information of some classes in the proposed scheme.Lemma 2.
In the proposed scheme, any inside attackers (malicious subscribers) cannot compute unauthorized key information of some class.Proof.
Without loss of generality, we consider the following two cases to prove this lemma.
Case I. We assume that a subscriber A in class C
j from t
1 to t
2 tries to compute unauthorized key information K
i
,
t
1
,
t
2of class C
i for some index i and C
j
⊀
C
i. If A wants to compute K
i
,
t
1
,
t
2, he must find a value r
′
=
g
i
h
j such that r
′
·
K
j
,
t
1
,
t
2
=
(
g
i
·
h
j
)
·
g
j
a
t
1
b
z
-
t
2
P
=
K
i
,
t
1
,
t
2. Since g
i and h
j are secret values held by vendor, A cannot compute the value r
′
=
g
i
h
j. Thus, it is infeasible to compute unauthorized key information K
i
,
t
1
,
t
2 from K
j
,
t
1
,
t
2 for the case C
j
⊀
C
i.
Case II. We assume that a subscriber A in class C
j from t
1 to t
2 tries to compute unauthorized key information K
i
,
t
1
,
t
2of class C
i, where C
j
≺
C
i. By similar way to Case I, A must find a value r
′ such that r
′
·
K
j
,
t
1
,
t
2
=
K
i
,
t
1
,
t
2. Although A owns the value r
i
,
j
=
h
i
g
j, he still cannot compute r
′
=
g
i
h
j by the same reason in Case I. Thus, it is infeasible to compute K
i
,
t
1
,
t
2 from K
j
,
t
1
,
t
2 for the case C
j
≺
C
i.Lemma 3.
In the proposed scheme, any inside attackers (malicious subscribers) cannot collude to compute unauthorized key information in some class.Proof.
Without loss of generality, we consider the following two cases to prove this lemma.
Case I. We assume that two subscribers A and B collude to compute the unauthorized key information K
i
,
t
1
,
t
2in class C
i from t
1 to t
2, where A subscribes to C
j from t
1 to t
2 and B subscribes to C
k from t
1 to t
2 with C
j
≺
C
i, C
k
≺
C
i, and C
j
⊀
C
k. As mentioned in Lemma 2, two malicious subscribers must find a value r
′
=
g
i
h
j such that r
′
·
K
j
,
t
1
,
t
2
=
K
i
,
t
1
,
t
2 or a value r
′′
=
g
i
h
k such that r
′′
·
K
k
,
t
1
,
t
2
=
K
i
,
t
1
,
t
2. Even if they have r
i
,
j
=
h
i
g
j and r
i
,
k
=
h
i
g
k, they still cannot compute r
′ and r
′′. Since g
i and h
j are secret values held by vendor, they cannot obtain the individual values g
i and h
j. Thus, it is infeasible to compute K
i
,
t
1
,
t
2 from t
1 to t
2 with C
j
≺
C
i, C
k
≺
C
i, and C
j
⊀
C
k.
Case II. We assume that three subscribers A, B, and C collude to compute the unauthorized key information K
j
,
t
2
,
t
3in class C
j from t
2 to t
3, where A subscribes to C
i from t
1 to t
2, B subscribes to C
j from t
3 to t
4, and C subscribes to C
k from t
5 to t
6 with C
k
≺
C
j
≺
C
i and t
5
≤
t
2
<
t
3
≤
t
6. If they want to compute K
j
,
t
2
,
t
3
=
g
j
a
t
2
b
z
-
t
3
P, they must find the two values a
t
2
-
t
3 and b
t
3
-
t
4 such that a
t
2
-
t
3
·
b
t
3
-
t
4
·
K
j
,
t
3
,
t
4
=
g
j
a
t
2
b
z
-
t
3
P. However, it is infeasible to find a
t
2
-
t
3 and b
t
3
-
t
4 from K
i
,
t
1
,
t
2, K
j
,
t
3
,
t
4, and K
i
,
t
5
,
t
6under the discrete logarithm and the computational Diffie-Hellman assumptions.By Lemmas1–3, we can obtain Theorem 4.Theorem 4.
Under the discrete logarithm and the computational Diffie-Hellman assumptions, any attackers (including inside and outside) cannot compute the unauthorized key information of some classC
i in the proposed scheme.


## 5.1.2. Security of Temporal Encryption Key

The security of temporal encryption key is relying on the security of key information. Hence, we have the following result.Theorem 5.
Under the discrete logarithm and the computational Diffie-Hellman assumptions, any attacker (including inside and outside) cannot compute the unauthorized temporal encryption key to access some classC
i in the proposed scheme.


## 5.2. Performance Evaluation

The performance of our scheme is evaluated in terms of storage requirements and computation costs. The storage requirements consist of three parts: private parameters, public values, and key information. These public values, includingB
x
,
y, r
i
,
j, and {
E
,
P
,
G
1
,
G
2
,
e
^
,
H
}, are published on an authentic board. Since {
E
,
P
,
G
1
,
G
2
,
e
^
,
H
} does not affect the storage complexity, we only discuss B
x
,
y and r
i
,
j. All users can download and store these public values. Then, a user can use his key information and these public values to compute the encrypting key for accessing the resources. The private parameters are security parameters in the proposed scheme and are kept secret in the server. The vendor uses these private parameters to generate all key information and encrypting keys. The private parameters include g
i, a, and b. Finally, the key information is generated according to a user’s subscription.Table1 shows the comparison of storage requirements between our scheme and other previous works. In the table, |
T
| means the system lifetime and the maximum duration of each subscription for a user is |
T
^
|. We also denote the number of edges and classes in G by |
E
| and |
V
|.Table 1
The space complexity.
Scheme
Public value
Private parameters
Key information
Ateniese et al. [9] (symmetric)
O
(
|
V
|
2
|
T
|
3
)
O
(
|
V
|
|
T
|
)
O
(
C
)
Ateniese et al. [9] (pairing)
O
(
|
V
|
2
)
O
(
|
V
|
|
T
|
)
O
(
|
T
^
|
)
Tzeng [8]
O
(
|
V
|
)
O
(
|
V
|
+
|
T
|
)
O
(
C
)
Bertino et al. [7]
O
(
|
E
|
)
O
(
|
V
|
)
O
(
C
)
Our scheme
O
(
|
T
^
|
2
+
|
E
|
)
O
(
|
E
|
+
|
V
|
)
O
(
C
)In the proposed scheme, the vendor randomly selects secret valuesg
i for each class in the partial-order hierarchy, where g
i can be used to generate K
i and K
i
,
t
1
,
t
2. Therefore, the space complexity of the private parameters in the server side is O
(
|
V
|
). Now, we consider the space complexity of the public values in the client side. The public values in our scheme are B
x
,
y and r
i
,
j. Since the maximum duration of each subscription for a user is |
T
^
|, the number of B
x
,
y is equal to (
|
T
^
|
(
|
T
^
|
+
3
)
)
/
2 and the number of r
i
,
j is |
E
|. Consequently, the space complexity of public values is O
(
|
T
^
|
2
+
|
E
|
). In fact, the storage requirements in our protocol are irrelevant to |
T
|. Otherwise, if the storage requirements are related to |
T
|, the space complexity will rise dramatically when |
T
| is very large. Compared to other schemes (as shown in Table 1), our scheme has better performance on the space complexity and the space complexity is irrelevant to |
T
|. Although the number of public values in Bertino et al.’s scheme [7] is fewer than in our scheme, Bertino et al.’s protocol requires tamper-resistant devices, which require extra costs in the deployment phase and are not suitable for cloud computing.The number of key information in our scheme depends on partial-order hierarchy and the number of classes which a user subscribes to. After a user registers to the system, the server will issue some key information to the user. Unlike some works ([9, 21]) which require that a user only belongs to one class, our scheme allows that a user can subscribe to many classes. The worst case is that every class is irrelevant to the other classes. In this case, the space complexity of the key information for a user is O
(
|
V
|
). However, generally, the number of key information for a user is equal to a constant number.We use a concrete example to show the space requirements for the proposed scheme. First, we suppose that each time slot is one day. Then, we set the system lifetime to be 10 years (z
=
1
×
365
×
10
=
3650) and the maximum duration of each subscription for a user is one month (l
=
1
×
30
=
30). Finally, we assume that there are 250 channels in the system. To put it simply, we set |
V
| and |
E
| to be both equal to 300 in the partial-order hierarchy. According to the previous analysis, the space requirements for the public values are related to the number of B
x
,
y and r
i
,
j. Since the number of B
x
,
y is equal to 495 and the number of r
i
,
j is 300, we can compute that the space requirements for the public values are (
495
+
300
)
×
160
bits
≅
16 KB. The space requirement for the private parameters depends on the number of g
i. Hence the space complexity for the private parameters is equal to 300
×
160
bits
≅
6 KB. Finally, the size of each key information is 160 bits.Now, we consider the computation cost of encrypting key derivation. In our scheme, a user only computes two pairing operations at most when he derives the encrypting key. In [22], the results show that the computation cost of pairing operation for a smartphone (HTC Desire HD A9191, Android 2.2) is affordable. Therefore, it is feasible that our scheme can be executed on low-power devices such as phone and set-top box.


## 5.3. Application

Cloud computing means that applications migrate from local PCs to Internet and sometimes is referred to as Software as a Service (SaaS) [23, 24]. Users can obtain the computing and storage capacities through Internet. Users pay for the network traffic or CPU utilization time instead of paying for software. When a cloud is only made available to some specific members in an organization, this cloud is called private cloud and only authorized users can access the cloud. For example, enterprises usually construct private data storage service for the employees.Since security threats can influence the development of cloud computing, many security issues are discussed [25], especially the access control problem. In this section, we introduce two examples, data storage service and video-on-demand (VoD) service, and explain the access control problem in both examples. First application, cloud storage service, allows users to store their files on the remote servers and share their files with other users. Obviously, enterprises can gain great benefits from cloud storage services. However, enterprises always construct their own private cloud services instead of public cloud services because of the privacy and security consideration. In an enterprise or a government, data are always classified into several classes, for example, C
1 to C
4, and members are also categorized into these classes. Assume that C
1
≺
C
2
≺
C
3
≺
C
4, where C
1
≺
C
2 means that a user which belongs to C
2 can access the data in C
1 and C
2. In this case, a user which belongs to C
1 cannot access the data in the C
2, C
3, and C
4. Therefore, we can apply a key assignment scheme to solve the access control problem. A key assignment scheme can distribute encrypting keys to each member according to their access rights in the organization. Unfortunately, a user may only subscribe to some classes for a certain period of time. Traditional key assignment protocol cannot satisfy the time-bound requirement, but the proposed scheme can solve this problem easily. Besides, utilizing public values is more suitable for cloud computing than adopting tamper-resistant devices. Cloud computing claims that users can access the resources anywhere without any limitations, but adopting tamper-resistant devices in cloud services will restrict users’ convenience. We use an example to explain how to apply the proposed scheme to enhance the cloud service. For example, an employee may become an agent of his manager when his manager takes a vacation. Suppose that the manager belongs to C
3 and the employee belongs to C
1. In addition, we also assume that the manger is on vacation from t
5 to t
8. Hence, the manager only needs to escalate the privilege of his agent into C
3 when he is on a vacation (t
5 to t
8) and our time-bound protocol can easily achieve this requirement. The manager just gives the agent the key information, K
3
,
t
5
,
t
8. This means that the agent can only access the data which belong to C
3 from t
5 to t
8. On the other hand, the agent cannot derivate the encrypting key of C
3 except for the specific periods of time (t
5 to t
8).The second application is the video-on-demand (VoD) system. Recently, many researchers discuss how to utilize cloud services to support large-scale Internet-based applications such as video-on-demand (VoD) [26, 27]. In VoD systems, users can watch video content on demand. Video content can be either streamed or downloaded through a set-top box, a computer, or a mobile device. Users can subscribe to the content that they like and access the content in the duration of subscription. Video content is always encrypted in VoD systems and users must use his encrypting key to access the content. In addition, a user usually subscribes to a program only for a limited period such as a week or a month. Beyond the duration of subscription, users are not allowed to access the content. The proposed time-bound protocol can be easily deployed into VoD systems to manage the users’ subscription. In the initial phase, the vender organizes all contents into several classes and constructs a partial-order hierarchy. For every class, the encrypting key will be used to protect the content and be changed as time goes by. A user in the system will obtain some key information according to his subscription. Finally, the user can compute the correct encrypting key through his key information and public values to access the encrypted contents.


## 6. Conclusion

We have presented a time-bound key assignment scheme for a partial-order hierarchy. Since our scheme has the time-bound property, the vendor can offer great flexibility in the user subscription. Each user can only use his key information to compute the corresponding encrypting key in the duration of his subscription. Therefore our scheme can easily solve the key update problem without higher costs. In addition, our scheme applies public values instead of tamper-resistant devices, which is more suitable for cloud computing. Unlike previous schemes, the number of public values or key information does not depend on the length of system time. As a result, our scheme has lower space complexity and acceptable performance compared with previous works. Moreover, we also present that our scheme can defeat the collusion attacks.



---

*Source: 569397-2014-10-28.xml*