# A Novel Hierarchical Key Assignment Scheme for Data Access Control in IoT

Authors: Xiaoyu Li; Min Ye; Jiahui Chen; Jianhui Chen; Yeh-Cheng Chen
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Hierarchical key assignment scheme is an efficient cryptographic method for hierarchical access control, in which the encryption keys of lower classes can be derived by the higher classes. Such a property is an effective way to ensure the access control security of Internet of Things data markets. However, many researchers on this field cannot avoid potential single point of failure in key distribution, and some key assignment schemes are insecure against collusive attack or sibling attack or collaborative attack. In this paper, we propose a hierarchical key assignment scheme based on multilinear map to solve the multigroup access control in Internet of Things data markets. Compared with previous hierarchical key assignment schemes, our scheme can avoid potential single point of failure in key distribution. Also the central authority of our scheme (corresponding to the data owner in IoT data markets) does not need to assign the corresponding encryption keys to each user directly, and users in each class can obtain the encryption key via only a one-round key agreement protocol. We then show that our scheme satisfies the security of key indistinguishability under decisional multilinear Diffie-Hellman assumption. Finally, comparisons show the efficiency of our scheme and indicates that our proposed scheme can not only resist the potential attacks, but also guarantee the forward and backward security.


---

## Body

## 1. Introduction

Internet of Things (IoT) is the internetworking of smart sensing devices with network connectivity which enable these devices to collect and exchange data. To a certain extent, IoT can be viewed as a physical and logical extension of the current Internet. In the coming years, it is expected that the IoT can bridge many diverse technologies to enable new application services by connecting sensing devices together in support of intelligent decision making [1].Since sensor data has the huge potential value, many IoT commercial corporations, called IoT data owners, provide pay-on-demand access services on original IoT data. That is, IoT data are made available to users as they pay for what they need. Thus, data confidentiality is at the top of the list of concerns for IoT data owners. Although encryption can provide data confidentiality, classic encryption methods cannot meet the requirement of flexible and fine-grained access control for IoT data markets. This is because the users’ access rights in real applications are often organized in a hierarchy. Take the vehicle-to-everything (V2X) network as an example; it is based on lots of sensing devices that create and transmit data from these surroundings through various links, such as vehicle-to-person (V2P), vehicle-to-infrastructure (V2I), vehicle-to-vehicle (V2V), vehicle-to-building (V2B), and so on. As shown in Figure1, the access rights of these three subscribed users have a hierarchical structure on V2X data. The automaker has the supreme seniority and can access all V2X data, while the logistics company only accesses V2V data and V2I data. The self-driving service company can access more data than the logistics company, but less data than the automaker.Figure 1
Hierarchical data access in V2X scenario.From the perspective of function realization, access control is an alternative form of data sharing. And there is an extensive research carried out in proposing the ciphertext-policy attribute-based encryption (CP-ABE) [2] in the fields of secure and flexible IoT data sharing [3, 4]. However, existing CP-ABE schemes have a high overhead since the implementation of access structure is complicated. Moreover, attribute revocation is also an intractable problem in CP-ABE and requires extra computation and communication costs to deal with. With this in mind, many researchers study the issue of data sharing in IoT with a different primitive: group key management [5, 6]. However, traditional group key management shows poor flexibility and scalability for multigroup access control.Our contributions: in this paper, we propose a novel hierarchical key assignment scheme (HKAS) for secure and flexible access control in IoT data markets. Some significant features of our proposed scheme are as follows:(i)
The proposed scheme can avoid potential single point of failure of IoT data owner in key distribution. In our scheme, IoT data owner only focuses on the maintenance of the hierarchical structure, and users obtain the encryption keys via a one-round key agreement protocol.(ii)
Different from many dependent key schemes, the encryption key and private information of each class in our proposed HKAS are independent. This protects the encryption key being derived from the private information and improves the security of IoT data service system.(iii)
Our proposed scheme supplies efficient dynamical updates. When the hierarchical structure or user dynamically changes, IoT data owner updates the public information by using only one broadcast message.(iv)
We prove that our scheme can reach the security of key indistinguishability under decisional multilinear Diffie-Hellman assumption. Furthermore, our proposed scheme can avoid potential attacks such as collusive attack, sibling attack, and collaborative attack.


### 1.1. Related Works

In the IoT systems, a large number of sensor data is generated and transmitted. Without any doubt, data is an extremely important asset for all organizations. Thus, secure access control (or data sharing) which refers to the access rights of sensor data, is a paramount concern in IoT [7]. As we recalled above, many studies make use of CP-ABE to achieve the fine-grained access control in various IoT applications [8, 9]. However, CP-ABE is a cumbersome cryptographic mechanism, which is not suitable for resource-constrained IoT networks. In [10], Seo et al. proposed a certificateless-effective key management protocol for secure data access control in dynamic wireless sensor networks. All of the above solutions aim at establishing the secure system deployment for IoT. In terms of business operation, the IoT applications and services have the requirement of data sharing on sensor data. A key management scheme for publish-subscribe system that is compliant with the data access control requirements of smart grid and IoT protocols is proposed in [11]. As we know, the key management schemes based on the preshared key framework and key pool framework are not scalable for large numbers of entities and dynamic changes in relationships [12].Firstly proposed by Akl and Taylor [13], HKAS is an efficient cryptographic method for solving the hierarchical multigroup access control problem by allowing authorized users to have different access privileges. Since then, Hassen et al. [14] classified HKAS into two major approaches: dependent key approach and independent key approach. In the dependent key approach, users are organized in a hierarchy and allocated with a certain amount of security classes, where a security class can represent an individual user or a group of users. In the hierarchical structure, a central authority (CA) is used to assign an encryption key and some private information to each security class. More precisely, the encryption key is used to protect the data by constructing a symmetric cryptosystem, while the private information is devoted to deriving the encryption keys of all classes in the lower-down hierarchy. On the other side, there are also two ways in deriving the encryption keys: direct one and indirect one. The direct key derivation does not need to compute all the intermediate keys on the path from the higher class to the lower class, while the indirect key derivation needs to do so. Contrary to the dependent key approach, HKAS based on independent key approach considers the hierarchical relations between user groups and resource groups and each user needs to maintain the encryption keys of all resources which he/she can access. However, the composition of the user group in an independent key scheme is a little different from that in the dependent key scheme. More precisely, the number of user groups in the independent key scheme is usually larger than that in the dependent key scheme for solving the same hierarchical access control problem.Thereafter, many researchers proposed numerous dependent key schemes [15–19]. One of the main approaches to construct a dependent key scheme is to use a prime number’s fundamental properties [13, 20, 21], which brings in some additional drawbacks, such as large public information, vulnerable to GCD operation and collusive attack [22, 23]. Thanks to the lower computation overhead and smaller key size, elliptic curve cryptosystem (ECC) was devoted to constructing the dependent key schemes in [24, 25]. However, these two schemes cannot resist the collaborative attack [26] and sibling attack [27], respectively. In addition to the security issues, another drawback of HKASs based on ECC is the huge amounts of public information [28], which leads to collusive attack [22]. A more general scenario has been considered for HKAS, where the access control is not only hierarchical, but also shared with other classes [29].The abovementioned dependent HKASs solve only the hierarchical access control problems for classes rather than users. This means that the CA needs to assign the corresponding encryption key (or private information) to each user in a point to point manner. Thus if there are many users in the classes, the efficiency will decrease dramatically. Moreover, the rekeying mechanism also needs to be guaranteed due to the confidentiality requirement in dynamic key management.On the other side, the independent key approach which uses key trees and graphs techniques is user-oriented [30], such as the integrated multigroup key management scheme for the contributory environment proposed in [31]. Although independent key scheme is quite simple to deploy, it does not offer efficient support for the hierarchy changes, especially in dynamic access situation. The reason is that such a scheme needs to update lots of keys. Based on multilinear map, Zhou et al. proposed a decentralized multigroup key management scheme for hierarchical access control in [32]. In their independent key scheme, the rekeying mechanism is to negotiate among the involved user groups. Specifically, each involved user group’s server reselects a new public parameter and carries out one-round group key agreement protocol based on multilinear map. However, the number of involved user groups will be large in the case of massive user groups. And the parameter size of multilinear map is linear in the number of involved user groups. Due to the implementation of multilinear map, Zhou et al.’s scheme is inefficient when the number of user groups is very large.


### 1.2. Organization

The rest of this paper is arranged as follows. Definitions and background information are given in Section2. In Section 3, we propose our HKAS based on multilinear map and discuss the dynamic key management. The security and performance analysis of our proposed scheme are presented in Section 4 and Section 5, respectively. Finally, we conclude this paper in Section 6.


## 1.1. Related Works

In the IoT systems, a large number of sensor data is generated and transmitted. Without any doubt, data is an extremely important asset for all organizations. Thus, secure access control (or data sharing) which refers to the access rights of sensor data, is a paramount concern in IoT [7]. As we recalled above, many studies make use of CP-ABE to achieve the fine-grained access control in various IoT applications [8, 9]. However, CP-ABE is a cumbersome cryptographic mechanism, which is not suitable for resource-constrained IoT networks. In [10], Seo et al. proposed a certificateless-effective key management protocol for secure data access control in dynamic wireless sensor networks. All of the above solutions aim at establishing the secure system deployment for IoT. In terms of business operation, the IoT applications and services have the requirement of data sharing on sensor data. A key management scheme for publish-subscribe system that is compliant with the data access control requirements of smart grid and IoT protocols is proposed in [11]. As we know, the key management schemes based on the preshared key framework and key pool framework are not scalable for large numbers of entities and dynamic changes in relationships [12].Firstly proposed by Akl and Taylor [13], HKAS is an efficient cryptographic method for solving the hierarchical multigroup access control problem by allowing authorized users to have different access privileges. Since then, Hassen et al. [14] classified HKAS into two major approaches: dependent key approach and independent key approach. In the dependent key approach, users are organized in a hierarchy and allocated with a certain amount of security classes, where a security class can represent an individual user or a group of users. In the hierarchical structure, a central authority (CA) is used to assign an encryption key and some private information to each security class. More precisely, the encryption key is used to protect the data by constructing a symmetric cryptosystem, while the private information is devoted to deriving the encryption keys of all classes in the lower-down hierarchy. On the other side, there are also two ways in deriving the encryption keys: direct one and indirect one. The direct key derivation does not need to compute all the intermediate keys on the path from the higher class to the lower class, while the indirect key derivation needs to do so. Contrary to the dependent key approach, HKAS based on independent key approach considers the hierarchical relations between user groups and resource groups and each user needs to maintain the encryption keys of all resources which he/she can access. However, the composition of the user group in an independent key scheme is a little different from that in the dependent key scheme. More precisely, the number of user groups in the independent key scheme is usually larger than that in the dependent key scheme for solving the same hierarchical access control problem.Thereafter, many researchers proposed numerous dependent key schemes [15–19]. One of the main approaches to construct a dependent key scheme is to use a prime number’s fundamental properties [13, 20, 21], which brings in some additional drawbacks, such as large public information, vulnerable to GCD operation and collusive attack [22, 23]. Thanks to the lower computation overhead and smaller key size, elliptic curve cryptosystem (ECC) was devoted to constructing the dependent key schemes in [24, 25]. However, these two schemes cannot resist the collaborative attack [26] and sibling attack [27], respectively. In addition to the security issues, another drawback of HKASs based on ECC is the huge amounts of public information [28], which leads to collusive attack [22]. A more general scenario has been considered for HKAS, where the access control is not only hierarchical, but also shared with other classes [29].The abovementioned dependent HKASs solve only the hierarchical access control problems for classes rather than users. This means that the CA needs to assign the corresponding encryption key (or private information) to each user in a point to point manner. Thus if there are many users in the classes, the efficiency will decrease dramatically. Moreover, the rekeying mechanism also needs to be guaranteed due to the confidentiality requirement in dynamic key management.On the other side, the independent key approach which uses key trees and graphs techniques is user-oriented [30], such as the integrated multigroup key management scheme for the contributory environment proposed in [31]. Although independent key scheme is quite simple to deploy, it does not offer efficient support for the hierarchy changes, especially in dynamic access situation. The reason is that such a scheme needs to update lots of keys. Based on multilinear map, Zhou et al. proposed a decentralized multigroup key management scheme for hierarchical access control in [32]. In their independent key scheme, the rekeying mechanism is to negotiate among the involved user groups. Specifically, each involved user group’s server reselects a new public parameter and carries out one-round group key agreement protocol based on multilinear map. However, the number of involved user groups will be large in the case of massive user groups. And the parameter size of multilinear map is linear in the number of involved user groups. Due to the implementation of multilinear map, Zhou et al.’s scheme is inefficient when the number of user groups is very large.


## 1.2. Organization

The rest of this paper is arranged as follows. Definitions and background information are given in Section2. In Section 3, we propose our HKAS based on multilinear map and discuss the dynamic key management. The security and performance analysis of our proposed scheme are presented in Section 4 and Section 5, respectively. Finally, we conclude this paper in Section 6.


## 2. Preliminaries

This section gives some background knowledge that will be used in this paper. Firstly, we give a brief description of hierarchical key assignment. Then, we present the security model of HKAS. Finally, we introduce the definition of multilinear map and two intractable problems on multilinear map.


### 2.1. Hierarchical Key Assignment

The hierarchical structure of a system is represented by a partially ordered set as poset. It is defined as a set of classesV=V1,V2,…,Vn with respect to a binary relation “≤”. The notation Vi≤Vj means that the users in class Vj can access the data of users in class Vi; i.e., the access right of class Vj is higher than or equal to that of class Vi. If Vi≤Vj and there is no class Vk∈V such that Vi≤Vk≤Vj, we say that class Vj is an immediate predecessor of class Vi, which is denoted by Vi≤Vj. Here, class Vi is also considered as the immediate successor of class Vj.Formally, the above mentioned posetV,≤ can be represented as a directed graph G=V,E, and we say that the vertices V in G coincide with the classes and an edge Vi,Vj∈E if and only if Vj≤Vi. Without loss of generation, we set G as a directed acyclic graph. In G=V,E, we define two associated sets for each class: AncVi,G and DesVi,G. If there is a path from class Vi to class Vj in G, we denote Vi∈AncVj,G and Vj∈DesVi,G. The immediate predecessors and immediate successors of class Vi in G are denoted by PredVi,G and SuccVi,G, respectively.LetΓ be a set of access graphs corresponding to partially ordered hierarchies. An HKAS [13, 33] for Γ is defined as follows.Definition 1.
An HKAS forΓ is defined as a pair of algorithms Gen,Der which satisfy the following conditions:(i)
Gen1κ,G is a probabilistic polynomial-time algorithm that takes a security parameter 1κ and a graph G=V,E∈Γ as input. And it outputs:(a)
A piece of private informationski and an encryption key ki for class Vi∈V;(b)
A piece of public informationpub.(ii)
DerVi,Vj,ski,pub is a deterministic polynomial-time algorithm that inputs the public information pub, two classes Vi,Vj∈V, and Vi’s private information ski. If Vi∈AncVj,G, it outputs the encryption key kj which will be assigned to class Vj. Otherwise, it outputs a rejection symbol ⊥.
We useSK,K,pub to denote the output of Gen1κ,G, where SK and K are considered as the sets of private information and encryption keys of classes, respectively.


### 2.2. Security Model of HKAS

The security model of HKAS was formally provided in [33]. Atallah et al. proposed two different notions of security: security against key recovery (KR-security) and security for key indistinguishability (KI-security). The KR-security means that an adversary is not able to compute an encryption key which cannot be derived from the corrupted users, whereas the KI-security requires that an adversary is not able to distinguish the encryption key from a random string of the same length. Thus the KI-security implies the KR-security. Recently, Freire et al. [34] proposed the notion of security for strong key indistinguishability (S-KI-security) and argued that their new notion is strictly stronger than KI-security. Such a problem has been recently addressed in [35], which shows that S-KI-security is not stronger than KI-security, and claimed the equivalence between these two security notions. A similar result has been also shown in the unconditionally secure setting by [36].Thus based on the above conclusion, in this paper, we mainly concentrate on the KI-security and we only consider the security model for a static adversary. Formally, let there be an access graphG=V,E; we define a static adversary Astat that firstly chooses a class V∗∈V and an algorithm Corrupt which can provide public information pub and some private information skj to the adversary by using Gen algorithm on the access graph G. Let corr denote the output of Corrupt. On receiving a private information skj, the adversary can compute an encryption key kj of class Vj. Then let there be another encryption key k∗ not derived from all the private information skj and encryption keys kj. We finally define a challenge phase that gives either the encryption key k∗ or a random string of the same length; the adversary’s goal is to distinguish these two cases. The definition of KI-security is given as follows.Definition 2.
Let there be a set of access graphsΓ corresponding to partially ordered hierarchies, and lett Gen,Der be an HKAS for Γ. We consider the following two experiments:(i)
ExperimentExpA,V∗KI−11κ,GSK,K,pub←Gen1κ,Gcorr←CorruptV∗SKd←A1κ,G,pub,corr,k∗returnd(ii)
ExperimentExpA,V∗KI−01κ,GSK,K,pub←Gen1κ,Gcorr←CorruptV∗SKρ←0,1lengthk∗d←A1κ,G,pub,corr,ρreturnd
For anyG=V,E∈Γ and V∗∈V, the advantage of Astat is defined as AdvAKI1κ,G=PrExpA,GKI−11κ,G=1−PrExpA,GKI−01κ,G=1. An HKAS is said to be secure in the sense of key indistinguishability with respect to each static adversary, if AdvAKI1κ,G is negligible for each graph G∈Γ and each class V∗∈V.
Then, some underlying attacks, such as the contrary attack, sibling attack, and collaborative attack [16, 27, 37], are investigated in the security assessment. Besides, based on the requirement of practical application, HKAS should also consider the forward and backward security as is stated in [38]. The forward security means that a user cannot access the future data of the class Vi when revoking this user from class Vi, while the backward security implies that a user cannot access the previous data of the class Vj when adding this user into the class Vj. We will consider all these security features in the next part of our paper.


### 2.3. Multilinear Map and Complexity Assumptions

The multilinear map is a novel primitive and has many cryptographic applications, such as the multipartite key exchange protocol [39–42] and revocation system [43, 44].Remark: in this paper, we mainly focus on how to construct an HKAS using the property of multilinear maps. Attacks against an instance of multilinear map can translate to attacks against our proposed scheme, if our scheme is based on this instance. Although various instances of multilinear maps are proved to be insecure, the work on multilinear maps is being continued and new candidates of multilinear maps are proposed. Due to it, some candidates of multilinear maps are proposed in [45, 46]. Thus our proposed scheme can be immediately instantiated with these candidates of multilinear maps.Letp be a prime number, and let G1 and G2 be two multiplicative cyclic groups of order p. A map en:G1n⟶G2 is said to be an n− multilinear map [39] if it satisfies the following properties:(1)
Ifa1,…,an∈ℤp and g1,…,gn∈G1, then eng1a1,…,gnan=eng1,…,gna1⋯an.(2)
The mapen is called nondegenerate once it satisfies the following condition: if g is a generator of G1, then eg,…,g is a generator of G2.Similar to the bilinear case, the computational multilinear Diffie-Hellman (CMDH) and decisional multilinear Diffie-Hellman (DMDH) problem are described as follows.Definition 3.
Letg be a generator of G1 and en:G1n⟶G2 be an n− multilinear map. Given ga1,…,gan+1∈G1, where a1,…,an+1∈ℤp, the CMDH problem is to compute eng,…,ga1⋯an+1 in G2, and the DMDH problem is to distinguish T between eng,…,ga1⋯an+1 and a random G2− element.
CMDH assumption: this assumption says that it is hard to solve the CMDH problem. More precisely, the advantage for any probability polynomial-time algorithmA to solve the CMDH problem is negligible.
DMDH assumption: it supposes that any probability polynomial-time algorithmA has a negligible advantage in solving the DMDH problem.


## 2.1. Hierarchical Key Assignment

The hierarchical structure of a system is represented by a partially ordered set as poset. It is defined as a set of classesV=V1,V2,…,Vn with respect to a binary relation “≤”. The notation Vi≤Vj means that the users in class Vj can access the data of users in class Vi; i.e., the access right of class Vj is higher than or equal to that of class Vi. If Vi≤Vj and there is no class Vk∈V such that Vi≤Vk≤Vj, we say that class Vj is an immediate predecessor of class Vi, which is denoted by Vi≤Vj. Here, class Vi is also considered as the immediate successor of class Vj.Formally, the above mentioned posetV,≤ can be represented as a directed graph G=V,E, and we say that the vertices V in G coincide with the classes and an edge Vi,Vj∈E if and only if Vj≤Vi. Without loss of generation, we set G as a directed acyclic graph. In G=V,E, we define two associated sets for each class: AncVi,G and DesVi,G. If there is a path from class Vi to class Vj in G, we denote Vi∈AncVj,G and Vj∈DesVi,G. The immediate predecessors and immediate successors of class Vi in G are denoted by PredVi,G and SuccVi,G, respectively.LetΓ be a set of access graphs corresponding to partially ordered hierarchies. An HKAS [13, 33] for Γ is defined as follows.Definition 1.
An HKAS forΓ is defined as a pair of algorithms Gen,Der which satisfy the following conditions:(i)
Gen1κ,G is a probabilistic polynomial-time algorithm that takes a security parameter 1κ and a graph G=V,E∈Γ as input. And it outputs:(a)
A piece of private informationski and an encryption key ki for class Vi∈V;(b)
A piece of public informationpub.(ii)
DerVi,Vj,ski,pub is a deterministic polynomial-time algorithm that inputs the public information pub, two classes Vi,Vj∈V, and Vi’s private information ski. If Vi∈AncVj,G, it outputs the encryption key kj which will be assigned to class Vj. Otherwise, it outputs a rejection symbol ⊥.
We useSK,K,pub to denote the output of Gen1κ,G, where SK and K are considered as the sets of private information and encryption keys of classes, respectively.


## 2.2. Security Model of HKAS

The security model of HKAS was formally provided in [33]. Atallah et al. proposed two different notions of security: security against key recovery (KR-security) and security for key indistinguishability (KI-security). The KR-security means that an adversary is not able to compute an encryption key which cannot be derived from the corrupted users, whereas the KI-security requires that an adversary is not able to distinguish the encryption key from a random string of the same length. Thus the KI-security implies the KR-security. Recently, Freire et al. [34] proposed the notion of security for strong key indistinguishability (S-KI-security) and argued that their new notion is strictly stronger than KI-security. Such a problem has been recently addressed in [35], which shows that S-KI-security is not stronger than KI-security, and claimed the equivalence between these two security notions. A similar result has been also shown in the unconditionally secure setting by [36].Thus based on the above conclusion, in this paper, we mainly concentrate on the KI-security and we only consider the security model for a static adversary. Formally, let there be an access graphG=V,E; we define a static adversary Astat that firstly chooses a class V∗∈V and an algorithm Corrupt which can provide public information pub and some private information skj to the adversary by using Gen algorithm on the access graph G. Let corr denote the output of Corrupt. On receiving a private information skj, the adversary can compute an encryption key kj of class Vj. Then let there be another encryption key k∗ not derived from all the private information skj and encryption keys kj. We finally define a challenge phase that gives either the encryption key k∗ or a random string of the same length; the adversary’s goal is to distinguish these two cases. The definition of KI-security is given as follows.Definition 2.
Let there be a set of access graphsΓ corresponding to partially ordered hierarchies, and lett Gen,Der be an HKAS for Γ. We consider the following two experiments:(i)
ExperimentExpA,V∗KI−11κ,GSK,K,pub←Gen1κ,Gcorr←CorruptV∗SKd←A1κ,G,pub,corr,k∗returnd(ii)
ExperimentExpA,V∗KI−01κ,GSK,K,pub←Gen1κ,Gcorr←CorruptV∗SKρ←0,1lengthk∗d←A1κ,G,pub,corr,ρreturnd
For anyG=V,E∈Γ and V∗∈V, the advantage of Astat is defined as AdvAKI1κ,G=PrExpA,GKI−11κ,G=1−PrExpA,GKI−01κ,G=1. An HKAS is said to be secure in the sense of key indistinguishability with respect to each static adversary, if AdvAKI1κ,G is negligible for each graph G∈Γ and each class V∗∈V.
Then, some underlying attacks, such as the contrary attack, sibling attack, and collaborative attack [16, 27, 37], are investigated in the security assessment. Besides, based on the requirement of practical application, HKAS should also consider the forward and backward security as is stated in [38]. The forward security means that a user cannot access the future data of the class Vi when revoking this user from class Vi, while the backward security implies that a user cannot access the previous data of the class Vj when adding this user into the class Vj. We will consider all these security features in the next part of our paper.


## 2.3. Multilinear Map and Complexity Assumptions

The multilinear map is a novel primitive and has many cryptographic applications, such as the multipartite key exchange protocol [39–42] and revocation system [43, 44].Remark: in this paper, we mainly focus on how to construct an HKAS using the property of multilinear maps. Attacks against an instance of multilinear map can translate to attacks against our proposed scheme, if our scheme is based on this instance. Although various instances of multilinear maps are proved to be insecure, the work on multilinear maps is being continued and new candidates of multilinear maps are proposed. Due to it, some candidates of multilinear maps are proposed in [45, 46]. Thus our proposed scheme can be immediately instantiated with these candidates of multilinear maps.Letp be a prime number, and let G1 and G2 be two multiplicative cyclic groups of order p. A map en:G1n⟶G2 is said to be an n− multilinear map [39] if it satisfies the following properties:(1)
Ifa1,…,an∈ℤp and g1,…,gn∈G1, then eng1a1,…,gnan=eng1,…,gna1⋯an.(2)
The mapen is called nondegenerate once it satisfies the following condition: if g is a generator of G1, then eg,…,g is a generator of G2.Similar to the bilinear case, the computational multilinear Diffie-Hellman (CMDH) and decisional multilinear Diffie-Hellman (DMDH) problem are described as follows.Definition 3.
Letg be a generator of G1 and en:G1n⟶G2 be an n− multilinear map. Given ga1,…,gan+1∈G1, where a1,…,an+1∈ℤp, the CMDH problem is to compute eng,…,ga1⋯an+1 in G2, and the DMDH problem is to distinguish T between eng,…,ga1⋯an+1 and a random G2− element.
CMDH assumption: this assumption says that it is hard to solve the CMDH problem. More precisely, the advantage for any probability polynomial-time algorithmA to solve the CMDH problem is negligible.
DMDH assumption: it supposes that any probability polynomial-time algorithmA has a negligible advantage in solving the DMDH problem.


## 3. Our Proposed Scheme

We now propose our HKAS based on multilinear map. Then, we give the processes of rekeying in dynamic environments, including inserting a new class, removing an existing class, adding user, and revoking user.


### 3.1. System Model

The important features of our proposed scheme are the centralized control policy for hierarchy and the distributed key agreement policy for the encryption key in each class. Figure2 shows the system overview of our scheme. It is important to point out that each IoT data owner needs to play the CA’s role of HKAS in IoT data markets. The arrowhead with a solid line in Figure 2 represents the hierarchy between two classes. For example, there is an arrowhead from class Vi to class Vl; it means Vl≤Vi. It should be noted that the hierarchical structure of classes is considered to be public.Figure 2
System model of our scheme.In this system, the CA computes the encryption keys of classes in a top-down manner. That is, the encryption keys of those being the root node inG are firstly computed. Then, the encryption keys of their immediate successors are derived by the CA. This process repeats until the encryption keys of all the classes are computed. Finally, the CA broadcasts the public information of each class. Once receiving this public information, users in each class can obtain the corresponding encryption key via a one-round key agreement protocol. For the private information of each class, it needs to be sent to each user in a unicast channel to accomplish the key derivation. This can be done at the time of registration. Using the encryption key and private information of a class, any of the users in that class can derive the encryption keys in the lower classes. For dynamic key management, it can be solved without the point to point communication between the CA and each involved user.


### 3.2. Key Generation and Derivation

LetG1 and G2 be two multiplicative cyclic groups of the same prime order p, and let g be a generator of G1. H1:0,1∗⟶ℤp and H2:0,1∗⟶G1 are two one-way hash functions. en:G1n⟶G2 is an n− multilinear map. The notation Uij denotes user Uj in the class Vi, and let the identity of Uj be IDij.Key generation: forG=V,E, the CA chooses s,x∈ℤp∗ as the master keys and computes gs as the public information of this system. If class Vi is a root node in G, the CA sets di=1 and the private information of class Vi as si=H1x‖1⋯1k, where k∈ℕ is a public parameter. Otherwise, there exists a maximum path from a root to class Vi in G, and the CA sets di as the number of classes in this path. The private information of class Vi is si=H1H1…H1x‖1…1k…‖1…1k‖1…1k︸di. Take Figure 2 as an example; the private information of class Vi and class Vj is all H1x‖1⋯1k. Then, the private information of class Vl is H1H1H1x‖1⋯1k‖1⋯1k‖1⋯1k. To be specific, such a setting has two reasons. On the one hand, a class Vi may be located in different paths in G=V,E. An intractable problem is how to ensure the consistency of computation on the encryption keys of lower classes for higher classes on different path. If di is set as the above setting, this problem will have gone with the wind. On the other hand, such a setting is conducive to reflecting the hierarchy of classes.If a userUj wants to join into the class Vi, Uj should register with the CA and obtain the private information si. The public key and private key of Uij are pkij=H2IDijkij and skij=H2IDijkijs, respectively. Of course, kij can also be chosen by user Ui.For classVi in the hierarchy, the CA uses di‖gri‖pki1,…,pkit as the public information of class Vi, if Ui1,⋯Uit are the group users in class Vi. The gri can be computed by si and the encryption key of class Vi with hash function H1 as follows.LetVi1,…,Vini be the immediate predecessors of class Vi in G, i.e., PredVi,G=Vi1,…,Vini. Once we obtain the public information of these classes, user Uij can compute the encryption key of class Vi by(1)ki=enpki1,…,pkij−1,skij,pkij+1,…,pkit,gri1,…,grini,gs,…,gs,=enH2IDi1,…,H2IDit,g,…,gki1⋯kitri1⋯rinisn−ni−t+1.Of course, the CA also can compute the encryption key of classVi by using the master key:(2)enpki1,…,pkit,gri1,…,grini,gs,…,gss=enpki1,…,pkit,g,…,gki1⋯kitri1⋯rinisn−ni−t+1=ki.Finally, the public information of classVi is computed by gri=gsi⊕H1ki.The initial encryption key of classVi is eg,…,gri1⋯rinisn−ni+1, if PredVi,G=Vi1,…,Vini and there are no users in this class. This can be seen as a preset way for hierarchy. It can make the data access control more granular and scalable.Key derivation: assume thatVi∈AncVj,G. The path from Vi to Vj in G is Vi=Vjt,Vjt−1,…, Vj1,Vj0=Vj. Each user in class Vi can derive the encryption key of class Vj as shown in Figure 3.Figure 3
The process of key derivation.Form the way of key derivation, users in a class derive the encryption key of the lower classes with the need of iterative computation. To avoid this drawback, we can modify the formula of the encryption key as(3)ki=enpki1,…,skij,⋯pkit,gri1,…,grini,︸thepublicinformationofVicsancestorclassesgs,…,gs.For a class in the hierarchy, the number of its higher class will be much larger than that of its immediate predecessors. This requires that the parametern should be chosen larger for the direct key derivation. As it is widely known, the multilinear map will be more and more costly with the growth of parameter n. Therefore, we only discuss our proposed indirect key scheme in this paper. Furthermore, the number of users in a class is also an important factor for the size of the parameter n. We can integrate users into a virtual user with the help of group key agreement protocol. The private key of this virtual user is gsH1k′, where k′ is the negotiated group key of these users.


### 3.3. Dynamic Key Management

Data access control should consider the dynamic management at the level of individual users, while hierarchical access control also needs to consider the dynamic management at the level of user groups. Therefore, we consider the following four situations in our HKAS, which are corresponding to four scenarios in the dynamic hierarchical access control in IoT: user groups’ addition and revocation and individual user’s subscription and unsubscription.Inserting a new class: let classVi,Vj∈V satisfy the relation Vj≤Vi in the hierarchy. Now, consider that a new class Vt needs to be inserted into the hierarchy such that Vj≤Vt≤Vi. If there are no users in class Vt, the CA needs the following steps to manage a new hierarchical structure.(1)
Compute classVt’s private information st=H1si‖1⋯1k. Then, compute the encryption key of class Vt: kt=engri,gs,⋯.gss. The public information of class Vt is Vt:dt=di+1‖grt=gst⊕H2kt.(2)
For each classVl∈DesVt,G, compute the new dl and grl as described in key generation.(3)
Update the corresponding public information of these classes and broadcast a message with the form of “addVt:dt‖grt into the hierarchy Vl,dl,grl|Vl∈DesVt,G”.After receiving this message, users who are in the affected classes compute the new encryption key of the corresponding class as described in the key generation. Meanwhile, the private information of some affected classes must be updated by the newdl|Vl∈DesVt,G.If the new classVt has some users in the initial status, the process is similar to the above.Removing an existing class: assume that an existing classVi is to be removed from the hierarchy. The CA performs the following steps to maintain the new hierarchical structure:(1)
Remove the public information of classVi.(2)
For each classVj∈DesVi,G, compute the new grj for updating the public information of this class.(3)
Update the public information of the affected classes and broadcast a rekeying message with the form ofRemoveclassVifromthehierarchyVj,grj|Vj∈DesVi,G.After receiving this message, users in the affected classes compute the new encryption key as the key generation.What calls for special attention is that the private information of the affected classes will not be updated. This is because the private information of class is computed by a one-way hash functionH1 and obtaining its preimage is intractable for the involved users.The creation of a new relation into the hierarchy or the revocation of an existing relation from the hierarchy can be easily solved by invoking the above two processes.Adding user: when a new user requests to join a class in the hierarchy, this user should register with the CA, thus obtaining his/her private key and the private information of the joined class by a secure channel. LetIDit+1 denote the identity of this user. This implies that user Ut+1 wants to join into the class Vi. After the registration, the CA firstly appends the public key pkit+1=H2IDit+1kit+1 into the public information of class Vi. Then, the CA computes the new grm for class Vm, where Vm∈DesVi,G∪Vi. When obtaining these results, the CA updates the new grm of these affected classes. Finally, the CA broadcasts a rekeying message with form of “Adding a new user into Vi‖pkit+1‖Vi,gri∪Vm,grm|Vm∈DesVi,G”. Once receiving this message, user Uij updates the encryption key of class Vi by(4)ki′=enpki1,…,skij,…,pkit,H2IDit+1kit+1,gri1,…,grini,gs,⋯.gs=enH2IDi1,…,H2IDit,H2IDit+1,g,⋯.gki1⋯kitkit+1ri1⋯rinisn−ni−t.Users in classVm, where Vm∈DesVi,G, can derive the new encryption key by the updated public information. The computational method is the same as the key generation.Revoking user: when the CA wants to revoke a user with identityIDij, the CA firstly deletes this user’s public information from the public information of class Vi. Secondly, the CA computes and updates the new grm for class Vm, where Vm∈DesVi,G∪Vi. At last, the CA broadcasts a rekeying message with form of RevokingauserfromVi‖pkij=H2IDijkij‖Vi,gri∪Vm,grm|Vm∈DesVi,G. Once receiving this message, the users in class Vi compute the new encryption key of class Vi by(5)ki′=enpki1,…,skit,…,pkij−1,gs,pkij+1,…,pkit,gri1,…,grini,gs,⋯.gs,=enH2IDi1,…,H2IDij−1,gs,H2IDij+1,…,HIDit,g,…,gki1⋯kij−1kij+1⋯kitri1⋯rinisn−ni−t+2.Users in classVm, where Vm∈DesVi,G, also update the corresponding encryption key as described for key generation.Note that the rekeying message broadcasted by the CA has no authentication. This drawback exists widely in all constructions of HKAS. It will suffer from “Man-in-the-Middle” attack, where an attacker can masquerade as the CA to send the rekeying message. For what concerns this security weakness, we can solve it by using a signature scheme.


## 3.1. System Model

The important features of our proposed scheme are the centralized control policy for hierarchy and the distributed key agreement policy for the encryption key in each class. Figure2 shows the system overview of our scheme. It is important to point out that each IoT data owner needs to play the CA’s role of HKAS in IoT data markets. The arrowhead with a solid line in Figure 2 represents the hierarchy between two classes. For example, there is an arrowhead from class Vi to class Vl; it means Vl≤Vi. It should be noted that the hierarchical structure of classes is considered to be public.Figure 2
System model of our scheme.In this system, the CA computes the encryption keys of classes in a top-down manner. That is, the encryption keys of those being the root node inG are firstly computed. Then, the encryption keys of their immediate successors are derived by the CA. This process repeats until the encryption keys of all the classes are computed. Finally, the CA broadcasts the public information of each class. Once receiving this public information, users in each class can obtain the corresponding encryption key via a one-round key agreement protocol. For the private information of each class, it needs to be sent to each user in a unicast channel to accomplish the key derivation. This can be done at the time of registration. Using the encryption key and private information of a class, any of the users in that class can derive the encryption keys in the lower classes. For dynamic key management, it can be solved without the point to point communication between the CA and each involved user.


## 3.2. Key Generation and Derivation

LetG1 and G2 be two multiplicative cyclic groups of the same prime order p, and let g be a generator of G1. H1:0,1∗⟶ℤp and H2:0,1∗⟶G1 are two one-way hash functions. en:G1n⟶G2 is an n− multilinear map. The notation Uij denotes user Uj in the class Vi, and let the identity of Uj be IDij.Key generation: forG=V,E, the CA chooses s,x∈ℤp∗ as the master keys and computes gs as the public information of this system. If class Vi is a root node in G, the CA sets di=1 and the private information of class Vi as si=H1x‖1⋯1k, where k∈ℕ is a public parameter. Otherwise, there exists a maximum path from a root to class Vi in G, and the CA sets di as the number of classes in this path. The private information of class Vi is si=H1H1…H1x‖1…1k…‖1…1k‖1…1k︸di. Take Figure 2 as an example; the private information of class Vi and class Vj is all H1x‖1⋯1k. Then, the private information of class Vl is H1H1H1x‖1⋯1k‖1⋯1k‖1⋯1k. To be specific, such a setting has two reasons. On the one hand, a class Vi may be located in different paths in G=V,E. An intractable problem is how to ensure the consistency of computation on the encryption keys of lower classes for higher classes on different path. If di is set as the above setting, this problem will have gone with the wind. On the other hand, such a setting is conducive to reflecting the hierarchy of classes.If a userUj wants to join into the class Vi, Uj should register with the CA and obtain the private information si. The public key and private key of Uij are pkij=H2IDijkij and skij=H2IDijkijs, respectively. Of course, kij can also be chosen by user Ui.For classVi in the hierarchy, the CA uses di‖gri‖pki1,…,pkit as the public information of class Vi, if Ui1,⋯Uit are the group users in class Vi. The gri can be computed by si and the encryption key of class Vi with hash function H1 as follows.LetVi1,…,Vini be the immediate predecessors of class Vi in G, i.e., PredVi,G=Vi1,…,Vini. Once we obtain the public information of these classes, user Uij can compute the encryption key of class Vi by(1)ki=enpki1,…,pkij−1,skij,pkij+1,…,pkit,gri1,…,grini,gs,…,gs,=enH2IDi1,…,H2IDit,g,…,gki1⋯kitri1⋯rinisn−ni−t+1.Of course, the CA also can compute the encryption key of classVi by using the master key:(2)enpki1,…,pkit,gri1,…,grini,gs,…,gss=enpki1,…,pkit,g,…,gki1⋯kitri1⋯rinisn−ni−t+1=ki.Finally, the public information of classVi is computed by gri=gsi⊕H1ki.The initial encryption key of classVi is eg,…,gri1⋯rinisn−ni+1, if PredVi,G=Vi1,…,Vini and there are no users in this class. This can be seen as a preset way for hierarchy. It can make the data access control more granular and scalable.Key derivation: assume thatVi∈AncVj,G. The path from Vi to Vj in G is Vi=Vjt,Vjt−1,…, Vj1,Vj0=Vj. Each user in class Vi can derive the encryption key of class Vj as shown in Figure 3.Figure 3
The process of key derivation.Form the way of key derivation, users in a class derive the encryption key of the lower classes with the need of iterative computation. To avoid this drawback, we can modify the formula of the encryption key as(3)ki=enpki1,…,skij,⋯pkit,gri1,…,grini,︸thepublicinformationofVicsancestorclassesgs,…,gs.For a class in the hierarchy, the number of its higher class will be much larger than that of its immediate predecessors. This requires that the parametern should be chosen larger for the direct key derivation. As it is widely known, the multilinear map will be more and more costly with the growth of parameter n. Therefore, we only discuss our proposed indirect key scheme in this paper. Furthermore, the number of users in a class is also an important factor for the size of the parameter n. We can integrate users into a virtual user with the help of group key agreement protocol. The private key of this virtual user is gsH1k′, where k′ is the negotiated group key of these users.


## 3.3. Dynamic Key Management

Data access control should consider the dynamic management at the level of individual users, while hierarchical access control also needs to consider the dynamic management at the level of user groups. Therefore, we consider the following four situations in our HKAS, which are corresponding to four scenarios in the dynamic hierarchical access control in IoT: user groups’ addition and revocation and individual user’s subscription and unsubscription.Inserting a new class: let classVi,Vj∈V satisfy the relation Vj≤Vi in the hierarchy. Now, consider that a new class Vt needs to be inserted into the hierarchy such that Vj≤Vt≤Vi. If there are no users in class Vt, the CA needs the following steps to manage a new hierarchical structure.(1)
Compute classVt’s private information st=H1si‖1⋯1k. Then, compute the encryption key of class Vt: kt=engri,gs,⋯.gss. The public information of class Vt is Vt:dt=di+1‖grt=gst⊕H2kt.(2)
For each classVl∈DesVt,G, compute the new dl and grl as described in key generation.(3)
Update the corresponding public information of these classes and broadcast a message with the form of “addVt:dt‖grt into the hierarchy Vl,dl,grl|Vl∈DesVt,G”.After receiving this message, users who are in the affected classes compute the new encryption key of the corresponding class as described in the key generation. Meanwhile, the private information of some affected classes must be updated by the newdl|Vl∈DesVt,G.If the new classVt has some users in the initial status, the process is similar to the above.Removing an existing class: assume that an existing classVi is to be removed from the hierarchy. The CA performs the following steps to maintain the new hierarchical structure:(1)
Remove the public information of classVi.(2)
For each classVj∈DesVi,G, compute the new grj for updating the public information of this class.(3)
Update the public information of the affected classes and broadcast a rekeying message with the form ofRemoveclassVifromthehierarchyVj,grj|Vj∈DesVi,G.After receiving this message, users in the affected classes compute the new encryption key as the key generation.What calls for special attention is that the private information of the affected classes will not be updated. This is because the private information of class is computed by a one-way hash functionH1 and obtaining its preimage is intractable for the involved users.The creation of a new relation into the hierarchy or the revocation of an existing relation from the hierarchy can be easily solved by invoking the above two processes.Adding user: when a new user requests to join a class in the hierarchy, this user should register with the CA, thus obtaining his/her private key and the private information of the joined class by a secure channel. LetIDit+1 denote the identity of this user. This implies that user Ut+1 wants to join into the class Vi. After the registration, the CA firstly appends the public key pkit+1=H2IDit+1kit+1 into the public information of class Vi. Then, the CA computes the new grm for class Vm, where Vm∈DesVi,G∪Vi. When obtaining these results, the CA updates the new grm of these affected classes. Finally, the CA broadcasts a rekeying message with form of “Adding a new user into Vi‖pkit+1‖Vi,gri∪Vm,grm|Vm∈DesVi,G”. Once receiving this message, user Uij updates the encryption key of class Vi by(4)ki′=enpki1,…,skij,…,pkit,H2IDit+1kit+1,gri1,…,grini,gs,⋯.gs=enH2IDi1,…,H2IDit,H2IDit+1,g,⋯.gki1⋯kitkit+1ri1⋯rinisn−ni−t.Users in classVm, where Vm∈DesVi,G, can derive the new encryption key by the updated public information. The computational method is the same as the key generation.Revoking user: when the CA wants to revoke a user with identityIDij, the CA firstly deletes this user’s public information from the public information of class Vi. Secondly, the CA computes and updates the new grm for class Vm, where Vm∈DesVi,G∪Vi. At last, the CA broadcasts a rekeying message with form of RevokingauserfromVi‖pkij=H2IDijkij‖Vi,gri∪Vm,grm|Vm∈DesVi,G. Once receiving this message, the users in class Vi compute the new encryption key of class Vi by(5)ki′=enpki1,…,skit,…,pkij−1,gs,pkij+1,…,pkit,gri1,…,grini,gs,⋯.gs,=enH2IDi1,…,H2IDij−1,gs,H2IDij+1,…,HIDit,g,…,gki1⋯kij−1kij+1⋯kitri1⋯rinisn−ni−t+2.Users in classVm, where Vm∈DesVi,G, also update the corresponding encryption key as described for key generation.Note that the rekeying message broadcasted by the CA has no authentication. This drawback exists widely in all constructions of HKAS. It will suffer from “Man-in-the-Middle” attack, where an attacker can masquerade as the CA to send the rekeying message. For what concerns this security weakness, we can solve it by using a signature scheme.


## 4. Security Analysis

In this section, we show that the proposed scheme can resist various attacks through formal and informal security analysis. Then, we discuss the performance of our proposed scheme.From the construction of our proposed scheme, we can see that such a scheme belongs to the HKAS and is based on the dependent key approach which refers to the users in each class. Thus the users should be considered in the security model. For this purpose, we modify Definition2 by allowing the adversary A to corrupt some users. All the corrupted users are only in the classes whose access right is lower than that of the attacked class. In our proposed scheme, we assume that the encryption key of a class cannot be deduced from the private information of that class. We require that Corrupt can provide the encryption keys of some classes to the adversary, besides the public information pub and some private information skj. Finally, all the private information and encryption keys provided to the adversary are assigned to the classes whose access right is lower than that of the attacked class.Theorem 1.
Our proposed scheme satisfies the KI-security, assuming that the DMDH problem is hard to be solved.Proof.
In the proof, we need to show how to turn a static adversaryA that can break our proposed scheme into a challenger S that can break the DMDH problem. Assume that the static adversary A chooses class Vm.
Once obtaining the parameters of DMDH problem:ga1,…,gan+1 and T, the challenger S sets ga1,…,gan as the public key of the users in the class Vm and the public information of Vm’s immediate predecessors. The public information of the system is denoted by gan+1. Moreover, the challenger S randomly chooses x′∈ℤp to generate the private information of each class.
Observed from Definition2, the only difference between ExpA,V∗KI−11κ,G and ExpA,V∗KI−01κ,G is the input of A, which corresponds to the real encryption key k∗ and a random value ρ∈0,1lengthk∗. The encryption key of class Vm is set as km=T. If T=eng,…,ga1⋯an+1, then km is the real encryption key of class Vm. Otherwise, km is a random value in G2. The public information of class Vm is computed by gsm′⊕H1km, where sm′ is computed by x′‖1⋯1k along with hash function H1.
For each classVi∈AncVm,G, the challenger S randomly chooses cj∈ℤp for user Uij. The public key and private key of user Uij are gcj and gan+1cj, respectively. Thus, the challenger S can compute the encryption key and public information of class Vl, where Vl∈AncVm,G and Vl∉PredVm,G.
Since classVi and users in class Vi, where Vi∈AncVm,G, cannot be corrupted by the adversary A in the attack game, such modifications can be regarded as independent on the public and private information of classes in the adversary’s view.
For each user in classVt, where Vt∉AncVm,G∪Vm, the challenger S randomly chooses c∈ℤp and sets gc as the public key of this user. If A wants to corrupt this user, the challenger S returns gan+1c to the adversary A, as the private key of this user. Then, the private information and the encryption key of class Vt are all allowed to be corrupted by the adversary A, due to the fact that the challenger S has x′ and the private key of the user in class Vt. Furthermore, the distribution of the encryption key kt is the same as the one described in the key generation. Moreover, the public information of class Vt which can be computed by the challenger S is also provided to adversary A.
Finally,A outputs a bit d as the response to whether the given value from S is the real encryption key of class Vm. And this output is also the answer of challenger S for the DMDH problem.
Thus, we haveAdvAKI1κ,G≤AdvS,GDMDHλ.
By DMDH assumption, we know thatAdvS,GDMDHλ is negligible. Thus, we complete the proof of this theorem.
Collusive attack: letVi≤Vj. Collusive attack means that an insider attacker in class Vi attempts to derive the encryption key of class Vj. The insider attacker only uses the public parameters, ki, si, and his/her private key. The encryption key kj in our proposed scheme is hidden in the value of the discrete logarithm with the first treatment of hash function. Due to the discrete logarithm and one-way hash function properties, it is computationally hard for this attacker. That is, our proposed scheme can resist the contrary attack.
Sibling attack: assuming thatVi≤Vk and Vy≤Vk are satisfied, neither the relation Vi≤Vj nor Vj≤Vi exists. The sibling attack considers whether a malicious user in class Vi can derive the encryption key of class Vj. This malicious user has to encounter the difficulty of computing the preimage of H1 even if di≤dj. Similarly, the attacker needs to solve the discrete logarithm problem and the CMDH problem if starting from the public information grj and the generation of kj, respectively. It is an intractable problem for the malicious user. Hence, the proposed scheme is secure against this attack.
Collaborative attack: collaborative attack is the case when several users in the set of classesCS=Vi|Vi∉AncVj,G collaborate to derive the encryption key kj. To launch such an attack, these users need to derive the master key from gs or solve the CMDH problem. At least, these users must derive the preimage kj from the one-way hash function H1, if Vi⋠Vj and di≤dj exist. It is computationally infeasible to do these tasks. Thus, the proposed scheme can resist a collaborative attack.
Forward security: from the processes of removing an existing class or revoking user, we know that the encryption keys of the corresponding classes will be updated by the computation of the multilinear map. Consider, for example, the user revocation; the new encryption key of the corresponding class is obtained by substituting the public informationgs for the public key of the revoked user in the multilinear map. Since the private keys of other users in the corresponding class and the master key are unknown, the revoked user should solve the CMDH problem if he/she wants to obtain the new encryption key. It is impossible for the revoked user because of the CMDH assumption. If the revoked user wants to derive the new encryption key from the public information of the corresponding class, he/she has to deal with two intractable problems: solving the discrete logarithm and obtaining the preimage of a one-way hash function. Therefore, our proposed scheme can guarantee forward security.
Backward security: As previously stated, the involved users use the public information of the new inserted class or the new public information of the immediate predecessors to compute the new encryption key of the corresponding class when inserting a new class into the hierarchy. If adding a new user into a class, users in that class obtain the new encryption key by substituting the public key of this new user for anyone of public informationgs in the multilinear map. The encryption keys of these classes lower down in the hierarchy are all updated by the new public information. For the previous encryption keys of the affected classes, it is an instance of the CMDH problem to this new user. So, backward security is retained in our proposed scheme.
We compare our proposed scheme among some existing HKASs in terms of security. Table1 gives the comparison results.Table 1
Security comparison among some existing HKASs.
SchemeSecurity assumptionSecure against collusive attackSecure against sibling attackSecure against collaborative attackForward securityBackward securityHwang-Yang scheme [19]Integers factorization×√√√√Lo et al.’s scheme [21]PKE with CPA-secure and hash function√√√×√Jeng and Wang scheme [24]ECC√√×√√Chung et al.’s scheme [25]ECC and hash function√×√√√Our schemeCMDH and DMDH√√√√√


## 5. Performance Analysis

It is known that computation, storage, and communication costs are the three main factors in the performance evaluation. For ease of exposition, letni1=AncVi,G, ni2=DecVi,G and ni3=PrecVi,G. It is clear that ni3≤ni1.In our proposed scheme, the storage overheads of each user are the size of his/her private key and private information of the corresponding class. To obtain the encryption keyki, each user in the class Vi needs to compute one time of the multilinear map. Let Vj≤Vi; users in class Vi need to compute l−1 times of multilinear map and XOR operator, along with multiple times of hash function for deriving the encryption key of Vj, where l is the number of classes in the path from class Vi to class Vj. The times of hash function are certainly no more than 2V.The rekeying computation costs for the CA areni2+1 times of the multilinear map, modular exponentiation, and XOR operator, along with multiple times of hash function when inserting or removing a class in the hierarchy. The communication cost for rekeying is one broadcast. The involved users need one computation of a multilinear map for obtaining the new encryption key of the corresponding class. Besides, the update of the private information for each affected class needs no more than one time of the hash function.Although our proposed scheme belongs to a dependent key scheme, in the construction of encryption keys, it also focuses on each user. Thus the system public information for the dependent key scheme should also contain the public key of each user. The average number of users in each class is denoted bym. Besides these, we also set the average number of affected user groups in the independent key scheme as ni1+ni2.We compare our proposed scheme with Zhou et al.’s scheme [32] in terms of performance. The results are given in Table 2, where L1 denotes the size of user’s private key or the security parameter of a public key encryption scheme, L2 represents the size of the ciphertext for a public key encryption scheme, and L3 denotes the security parameter for multilinear map. Our proposed scheme may have some advantages over communication costs for rekeying, while the computation cost is a disadvantage for each user in the system. The parameter for the multilinear map used in our proposed scheme is less than that in Zhou et al.’s scheme with high probability. More importantly, our proposed scheme does not limit the number of user groups or access resources if the total number between users in a class and immediate predecessors of that class is a feasible value for a multilinear map. Once we employ the technology of virtual users, the computation cost of our proposed scheme is certainly less than that of Zhou et al.’s scheme.Table 2
Performance comparison between our scheme and Zhou et al.’s scheme.
SchemePrivate information of each user (besideski)Public information of systemKey derivation in dependent key scheme or obtaining encryption key in independent key schemeMaximal computation and communication costs for rekeyingZhou et al.’s scheme [32]L1V+NL1≈⌊log2m⌋+1CPE≈CMMni1+ni2+CH+mni1+ni2CPE≈mni1+ni2L2+ni1+ni2L1,Our scheme≈L3+log2VV+NL3+Vlog2V≤l−1CMMni3+m+CXOR+2V+l−1CH≤ni2+1CMMni3+m+CME+CXOR+2VCH≈ni2L3+log2V,Notations:V: number of classes in the access graph G. N: number of users in the access graph G. CPE: computation cost for decryption of a public key encryption scheme. CMMn: computation cost of n-multilinear map. CME: computation cost of modular exponent. CXOR: computation cost of XOR operator. CH: computation cost of hash function.


## 6. Conclusion

In this paper, we propose an HKAS by using the building block of multilinear map for secure and flexible access control in IoT data markets. In our proposed scheme, the CA only updates the public information of each class for maintaining the hierarchical structure, and users in each class almost independently manage the corresponding encryption key via a one-round key agreement protocol. Moreover, the public information of the higher classes does not need to do any operation in dynamic environments. We show that the proposed scheme ensures KI-security based on the DMDH assumption. A shortcoming of our proposed scheme is that it only applies to the case of a very small amount of users, since the computation and storage costs for implementing the multilinear map are all expensive. To construct a simple and practical dependent key scheme without using a key assignment, novel ideas are expected, and we leave it as our future work.



---

*Source: 6174506-2021-12-06.xml*