A Key Management Scheme Based on Hypergraph for Fog Computing

Zhi Li＊, Yanzhu Liu, Di Liu Chunyang Li Wei Cui Guanglin Hu

1 State Grid Information & Telecommunication Group Co., Ltd., Beijing 102211, China

2 Great Wall Computer Software and Systems Inc., Beijing 100190, China

Abstract: Fog computing is a new paradigm supporting the stringent requirements of mobility applications by bridging cloud computing and smart devices. Since the smart devices may be deployed in dynamic areas where are out of strict monitoring and protection, fog computing requires security protections to ensure confidentiality and integrity. In this article, to deal with security requirements and considering the distinctive features, a key management based on hypergraph schemed is designed. Firstly, based on the key hypergraph, the three hierarchy architecture of fog computing is divided into two subnetworks.Furthermore, each key management process of both two subnetworks is designed to satisfy the operational and security requirements of fog computing. Finally, the performance evaluation and numerical simulation have been provided to validate the proposed scheme.

Keywords: fog computing; fog security; key management; hypergraph

I. INTRODUCTION

With the development of smart devices and the ubiquitous mobile Internet, Internet of Things (IoT) has pervaded people’s daily life.IoT is made up of consumer products, cars and trucks, sensors and other everyday objects,which are becoming more intelligent with powerful data analytic and storage capabilities[1]. In general, IoT collects and aggregates data by using smart devices, and sends the data to the cloud services for storage and processing. Cloud computing provides a highly scalable computing platform to large scale data processing, in which the physical and virtual cloud resources can be allocated and recovered on-demand.

However, the explosive growth of data traffics led by the ubiquitous and intensive use of smart devices also bring new challenges to the network environment. The billions of smart devices, such as wearable sensors, phablets and smartphones, have already being used to generate and transfer data. Transmitting this huge amount of data between cloud data center and user’s devices needs a good bandwidth, which requires considerable time. It is neither efficient nor effective to transfer all the data to the cloud data center, since it is hard for cloud computing to satisfy the requirements of mobility support, location awareness and low latency [2]. To solve aforementioned problem, fog computing as an extension of the traditional cloud computing paradigm was proposed by Cisco in 2011 [3]. According to Cisco’s perspective, cloud computing paradigm can be extended by fog computing to the edge of the network [4]. Fog computing is a highly virtualized platform providing network services such as computing or storage between the end devices and cloud. In contrast to the cloud, which is considered as a more centralized computing, the fog computing is a new generation of distributed computing which targets the applications and services with widely distributed deployments. Since the fog computing brings computing resources close to the underlying devices and IoT, there are a number of characteristics which make the fog computing a non-trivial extension of the cloud computing, such as edge location,location awareness, low latency, geographical distribution, supporting for mobility, real-time interactions, heterogeneity, interoperability and federation [5].

With the growing popularity of fog computing, the importance of security shows gradual upward trend, becoming a significant factor in the development of fog computing. Smart devices are deployed in a distributed platform for multi-user virtual environments, where is out of strict monitoring and protection. It is more prone to security threats and vulnerabilities, which attracts malicious users to attack them. Some traditional attacks such as eavesdropping, data hijacking etc., may seriously threaten to the fog devices for its malicious purpose. Thus, fog computing requires security mechanisms to protect messages exchanged among legitimate users, and prevent the non-legitimate member from accessing the group communication. Key management is a core mechanism to ensure the security of services and applications [6]. As a set of processes and mechanisms, key management supports the key establishment and maintenance according to a security policy [7]. Over the past years, many key management schemes have been proposed [8-10]. However, due to the unique characteristics of fog computing,these schemes may be not suitable [11]. One reason is that some of them do not consider the three hierarchy architecture of fog computing which is more complex than other network environments. Another reason is they have also not taken account of the fog computing’s characteristics, i.e., the limited computational power and storage capacity of the fog devices could incur a heavy storage overhead in these schemes. Therefore, in this paper, we try to establish a reliable and efficient key management scheme for the security in fog computing.

The problem of key management in Fog Computing was addressed and a new key management scheme based on hypergraph,is presented for security communication in this paper.

In this work, a key management framework based on key hypergraph is proposed to manage the keys of fog computing. In this approach, the fog computing network was divided into two sub networks, the Cloud-Fog subnetwork and the Fog-User subnetwork.The key management processes of both subnetwork are designed in detail. z which guarantees forward secrecy and backward secrecy[12]. By this key management framework, it is aimed to reduce the need for storage, computation, and communication in fog computing,and to increase the scalability and security of the network.

The rest of this paper is organized as follows. The structure of fog computing and the related works on key management are presented in Section II. The framework and performance analyses of the key management based on hypergraph are described in Section III and Section IV. Simulation results are presented in Section V. Conclusions of the work are brought in Section VI.

II. RELATED WORKS

Fog computing was firstly introduced by Cisco in 2011. This platform is called fog computing simply because “the fog is a cloud close to the ground” [13]. A typical fog computing framework is a three hierarchy architecture.As shown in figure1, fog computing extends the cloud computing paradigm to the edge of the network by adding an intermediate layer between terminal devices and cloud. In fog computing, smart devices which have a large variety of sensors and local data will connect to fog nodes through a short-range communications, such as Wi-Fi, Bluetooth. Compared with the smart devices, the fog nodes have more storage ability for computing, which make it be possible to process a significant amount of data from users. Those processes which request more resources will be sent to the cloud by fog nodes through high-speed wireless/wire communication.

Since the smart devices may be deployed in dynamic areas where is out of strict monitoring and protection, fog computing is more prone to security threats and vulnerabilities, which attract malicious users to attack it. More and more attention has been paid to the importance of the fog computing security, and the several unique security threats of fog computing was argued, such as intrusion detection, malicious detection [14] [15]. To ensure the security, the key management for large amounts of smart devices in fog computing is indispensable.Most cryptosystem rely on some robust and efficient key management system [16]. In fact, a variety of key management schemes are used to study security in different network environments, such as the wireless network[17], cloud computing [18]. However, there are little researches on the key management for fog computing at present. Since the limited computational power and storage capacity of the smart devices and the distributed virtual environment of the network, the existing key management schemes may be not suitable for fog computing. Hypergraph, as a branch of mathematics, influenced by the advent of computer science, has developed very rapidly in these years [19]. It provides a new method to establish secure model for various networks[20]. In this paper, a key management scheme based on hypergraph theory is designed to satisfy the operational and security requirements of fog computing.

Fig. 1. The fog computing architecture.

III. KEY MANAGEMENT HYPERGRAPH

In this section, we illustrate the hypergraph-based key management protocol(HKM) for fog computing. As depicted in figure 1, the fog computing extends the cloud computing by adding fog layer between users’smart devices and cloud. Actually, the key management protocol of fog computing consists of the following four elements:

● Key Generation Center (KGC): KGC generates the master secret keys and user-specific private keys for Cloud-Fog subnetwork and Fog-User subnetwork. It is fully trusted by all other members of the fog computing system.

● Cloud Server Provider (CSP): CSP provides data storage and other cloud services to its users.

● Fog Server (FS): FS comprises of devices,such as routers, gateways, switches, and access points, which are capable of computing, processing and storing data.

● User: Users are terminal nodes in the fog computing network, which connect the FS through a short-range communication, such as Bluetooth, ZigBee and Wi-Fi.

In this case, it is easy to divide the fog computing three-layer hierarchy into two sub-networks, which are Cloud-Fog subnetwork and Fog-User subnetwork as shown in figure2.Based the Hypergraph theory, the fog computing hypergraph structure is given as following.

Definition 1. The hypergraph structure for fog computing FH is defended as FH=(V,E),where

(i) V ={v1,v2,…,vn} is the set of vertexes,which represent the members in the hypergraph. According to the different subnetworks,there are two types vertexes in FH, which can be denoted as Vtype={VFS,VUser}. In Cloud-Fog subnetwork and Fog-User subnetwork,the vertexes of the hypergraph are composed of FSs and Users respectively.

(ii) E ={e1,e2,…,em} is the hyperedge,where ei≠∅The hyperedges in Cloud-Fog subnetwork and Fog-User subnetwork are denoted as E(·) and e(·) respectively.

The parameters set are shown in Table 1.

3.1 Key management in the cloudfog subnetwork

The main elements in Cloud-Fog subnetwork are KGC, CSP and FS. In this subnetwork, the users’ data which need more computing power will be sent to CSP by FS through high-speed communication. KGC generates the master secret keys and user-specific private keys for this subnetwork.

(1) Phase one: Initialization of key management protocol in the Cloud-Fog subnetwork

In the HKM, each FS corresponds to a vertex of the key hypergraph. We denote the hyperedge Ei(Ki) as a secure sub-group, in which a set of FSs share the same sub-group key Ki. Additionally, KGC and CSP are the intersection of all the hyperedges. At the beginning of the protocol, KGC needs to set up the key hypergraph for Cloud-Fog subnetwork.After selecting a key K0∈(0，1)nas the master key of the Cloud-Fog subnetwork, KGC will dispatch K0to all legitimate FSs through the secure channels. At same time, each FS shares a long-term individual key with CSP.

(2) Phase two: A new FS joins the Cloud-Fog subnetwork

Due to the demands of fog computing load balancing, a new FS needs to join the Cloud-Fog subnetwork sometime. In this case, the protocol has to rekey to keep the security of Cloud-Fog subnetwork. When receiving the join request from the new FS, CSP needs todecide whether to approve or refuse it. Once approved, CSP will send a long-term individual key to the new FS for key update through a secure channel. In order to guarantee backward secrecy, KGC needs to update the group key and sub-group key of the joining hyperedge. The new group key and sub-group key are randomly generated by KGC, and will be dispatched to all legitimate FSs in the Cloud-Fog subnetwork and the joining FS.

Table I. Parameters table.

Fig. 2. The key hypergraph of Cloud-Fog subnetwork and Fog-User subnetwork key hypergraph.

Fig 3 shows the processing of FS 11 joining the Cloud-Fog subnetwork. Generally, when a new FS FSjjoin the hyperedge Ei(Ki), the rekey protocol can be presented as follows.

Fig. 3. FS 11 joins the Cloud-Fog subnetwork.

Fig. 4. FS 10 leaves the Cloud-Fog subnetwork.

FSjsends the request for joining hyperedge Ei(Ki) in Cloud-Fog subnetwork.

According to the authentication protocol,KGC will certify FSjand generate an individual key Kjfor FSj. This individual key will be dispatched to FSjthrough the secure channel.

KGC randomly generates a new group key K0'and a new sub-group key Ki'for the joining hyperedge. A new group key K0'for all the FSs which are not in the hyperedge Ei(Ki)will also be dispatched. E0is the set of all hyperedges in the fog computing. K0is the original group key.

KGC dispatches the new group key K0'and the new sub-group key Ki'to the FSs which are in the hyperedge Ei(Ki). Kiis the original sub-group key of Ei(Ki).

KGC dispatches the new group key K0'and the new sub-group key Ki'to FS j through the individual key Kj.

From the above observation, when a new FS joins the Cloud-Fog subnetwork, KGC needs to send three key update messages. And the encrypted cost for KGC is five.

(3) Phase three: A FS leaves the Cloud-Fog subnetwork

In some special cases, the Fog Server Provider will close some FSs in Cloud-Fog subnetwork. At this time, KGC needs to update the key hypergraph by deleting vertex from the hyperedge.

In order to guarantee forward secrecy, KGC needs to update the group key and sub-group key of the leaving hyperedge. The new group key and sub-group key are randomly generat-ed by KGC, and will be distributed to all related FSs in the Cloud-Fog subnetwork.

Fig 4 shows the processing of FS 10 leaving the Cloud-Fog subnetwork. Generally, when FSjdecides to leave the hyperedge Ei(Ki),the rekey protocol is shown as follows.

FSjsends the request for leaving hyperedge Ei(Ki) in Cloud-Fog subnetwork.

KGC grants the request and generates a new group key K0'and a new sub-group key Ki'for leaving hyperedge.

KGC dispatches the new group key K0'to all the FSs which are not in the hyperedgeand Kmis the sub-group key of the hyperedge Em(Km).

KGC dispatches the new group K0'and the new sub-group key Ki'to all FSs which are in the leaving hyperedge Ei(Ki), where FSgindicates all left FSs and Kgis the individual key of FSg.

3.2 Key management in the Fog-User subnetwork

In the Fog-User subnetwork, FS is also responsible for key management.

(1) Phase one: Initialization of key management protocol in the Fog-User subnetwork

In the Fog-User subnetwork, each fog user corresponds to a vertex of the key hypergraph.The subnetwork is divided into several logical sub-groups, which own individual sub-group key. We denote the hyperedge ei(ki) and the key kias a secure sub-group and a group key respectively. All the hyperedges intersect at one point, that is, the FS. At the beginning of the protocol, each FS needs to set up the key hypergraph for Fog-User subnetwork. After selecting a key k0∈(01，)nas the master key of the Fog-User subnetwork, each FS will dispatch k0to all legitimate fog users through the secure channels. Meanwhile, each user shares a long-term individual key with its connected FS.

(2) Phase two: A new fog user joins the Fog-user subnetwork

When a new fog user joins the Fog-User subnetwork through a short-range communication, the corresponding FS will do series of actions to ensure subnetwork security. Once approved the user’s join request, in order to guarantee backward secrecy, the corresponding FS needs to update the group key and subgroup key of the joining hyperedge. The new group key and sub-group key are randomly generated, and will be dispatched to all legitimate users in the corresponding hyperedge and the new fog users through a secure channel.

Fig 5 shows the processing of fog user 13 joining the Cloud-Fog subnetwork. Generally,when FS FSigets a request from a new fog user Userαto join the hyperedgethe rekey protocol can be presented as follows.

Fig. 5. Fog user 13 joins the Cloud-Fog subnetwork.

Fog user Userαsends the request for joining hyperedgein Fog-User subnetwork.

According to the authentication protocol,FSicertifies Userαand generates an individual key kαfor user Userα. This individual key kαwill be dispatched to user Userαthrough a secure channel.

FSirandomly generates a new group keyand a new sub-group key k(i,m)'for the joining hyperedge. FSidispatches the new group key k(i,0)'to all the fog users which are not in the hyperedgeis a set of all users in the FSi. k(i,0)is the original group key.

Fig. 6. Fog user 2 leaves the Cloud-Fog subnetwork.

FSidispatches the new group key k(i,0)'and the new sub-group key k(i,m)'to the fog users which are in the hyperedgethe original sub-group key of

FSidispatches the new group key k(i,0)'and the new sub-group key k(i,m)'to user Userαthrough the individual key kα.

From the above observation, when a new user joins the Fog-User subnetwork, the FS needs to send three key update messages. And the encrypted cost for FS is five.

(3) Phase three: A fog user leaves the Fog-User subnetwork

When a fog user decides to leave the fog computing network environment or the smart device energy is exhausted, the network will delete this node. In order to guarantee forward secrecy, FS needs to update the key hypergraph by deleting vertex from the hyperedge.

Fig 6 shows the processing of fog user 2 leaving the Fog-User subnetwork. Generally,when FSjdetects that a fog user Userβleaving the hyperedge, the rekey protocol can be presented as follows.

Fog user Userβsends the request for leaving hyperedgein Fog-User subnetwork.

FSjgrants the request and randomly generates a new group key k(i,0)'and a new subgroup key k(i,m)'for leaving hyperedge.

FSjdispatches the new group key k(i,0)'to all the users which are not in the hyperedge, whereand k(i,n)is the sub-group key of the hyperedge

FSjdispatches the new group k(i,0)'and the new sub-group key k(i,m)'to all left users which are in the leaving hyperedgewhere Userγ, Userγ≠ Userβ, is the users in hyperedge em(k(i,m)) and kγis the individual key of Userγ.

3.3 The security transmission of the network data

A secure transmission channel have to be established to ensure the security of network data. We assume that Ksis the session key generated by KGC for the whole fog network.The data transmission protocol can be presented as follows.

KGC firstly sends the session key Ksto all FSs in Cloud-Fog subnetwork encrypted by the master key K0.

FSigets the session key Ksby decrypting the message {Ks}K0and sends the session key Ksto all users in Fog-User subnetwork encrypted by the master key k(i,0)

Each fog user Userpcan get the ciphertext by function EncKs(·) to encrypted the message with Ks.

Each fog user Userpcan also get the message by function DecKs(·) to decrypt the ciphertext with Ks.

IV. PERFORMANCE AND SECURITY ANALYSIS

In this section, we present the performance and security analysis to help understand the proposed hypergraph-based key management protocol (HKM) for fog computing.

4.1 The performance analysis

We assume the number of fog users is nu, and the number of FS is nFS. Thus, the average number of users in each Fog-User subnetwork is nu/nFS. Let nu/nFS=, whereis the average number of hyperedges in one Fog-User subnetwork.is the average number of fog user in one Fog-User subnetwork hyperedge. Similarly, we denote nFS=whereis the average number of hyperedges in one Cloud-Fog subnetwork andis the average number of FS in one Cloud-Fog subnetwork hyperedge.

(1) Fog user joins or leaves the fog network

From the above observation, when a new fog user joins the network, the FS needs to send three key update messages, which include an individual key for the new user, a new group key and a new sub-group key for the hyperedge in Fog-User subnetwork. The encrypted cost for KGC is five.

When a fog user leaves the network, the cost of other users in the Fog-User subnetworks for updating the group key isand the cost of other users is2 (-1).Therefore, the total encryption cost is

We have

(2) FS joins or leaves the Cloud-Fog subnetwork

Similarly, when a new FS joins the Cloud-Fog subnetwork, KGC needs to send three key to update messages, which include an individual key for the new user, a new group key and a new sub-group key for the hyperedge in Fog-User subnetwork. And the encrypted cost for KGC is five.

When a FS leaves the subnetwork, the cost of other FSs in Cloud-Fog subnetwork is-1 and the cost of other FSs of updating the group key and sub group key is 2 (-1). Therefore, the total encryption cost is

(3) Key management initialization overhead

Based on the foregoing definition, one FS will dispatchindividual keys andeFUsubgroup keys at the beginning of key management establishment. Sinceand, we havethe total cost of FS for key initialization is

(4) Storage overhead

In the proposed fog computing key management, KGC needs to store the FSs’ individual keys, sub group keys and one group key.Therefore, the size of keys stored by KGC isSimilarly, the size of keys stored by each FS isincluding nm individual keys,subgroup keys, one group key in Fog-User subnetwork, one individual key, one group key and one sub group key in Cloud-Fog subnetwork.

The number of keys stored by each fog user is 3, which is one group key, one sub group key and one individual key in Fog-User subnetwork.

4.2 The security analysis

In this section, the forward and backward security and PPT adversaries are analyzed to present the security analysis of HKM.

(1) Forward and backward security

Theorem 1 The proposed HKM scheme can satisfy the forward and backward security.

Proof In the proposed HMK scheme, no matter in the Cloud-Fog subnetwork or in the Fog-User subnetwork, the new group key will generate after member left the subnetwork.Meanwhile, according to the existing information, the attacker or the left member cannot generate the current or future group key.Therefore the proposed scheme satisfies the forward security.

Similarly, the attacker cannot get the used key according to the existing group key. Consequently, HMK satisfies the backward security.

(2) PPT adversaries

According to the study of Katz J et al.[26],the adversarial indistinguishability experiment can be defined as follows:

Definition 2. [26] The attacker A is a Probabilistic Polynomial Time (PPT) adversary.For each symmetric encryption algorithm Π=(Gen (·), E nc (·), D ec (·)), the indistinguishability experiment Priv(λ) can be denoted as following:

① Based on security parameters λ, A generates two message {m0,m1} which are the same bit length with λ.

② Generate k←Gen(λ) and randomly chose b←{0,1}. Then compute the ciphertext c, c ← Enck(mb) and send c it to A.

③ A outputs b'. If b'≠b, A failed, and Priv(λ)= 0, otherwise Priv(λ)=1.

④ For any probabilistic PPT attacker A, in order to keep Π=(Gen (·), E nc (·), D ec(·))indistinguishable, it should hold thats negligible.

Theorem 2 The proposed HKM scheme is secure for PPT adversaries.

Proof Let A be a PPT adversary and function ε(λ) denote as follows:

Based on the Definition 2, we can build the indistinguishability experiment PrivKAeav,Π(λ).We have

Since ε(n) is a negligible function, according to Definition 2, HKM is secure for PPT adversaries.

V. NUMERICAL SIMULATION

In this section, numerical analyses are presented to evaluate the performance of HKM. The key management schemes of LKH[22-23],OFT[24], GKMP[25] are selected for comparison in terms of keys efficiency and storage of the proposed scheme.

Fig. 7. The key generation costs of different schemes when a new FS joins the Fog, k=3.

Fig. 8. The key generation costs of different schemes when a FS leaves the Fog, k=3.

Fig. 10. The key generation costs of different schemes when a user leaves the Fog.

Fig. 7 and figure 8 illustrate the key generation costs of different key management schemes, when a FS joins or leaves the fog network. The initial number of FS is 40. It is also assumed that the branching factor k was 3. It is easy to see that the key generation cost of both HKM scheme and GKMP scheme are fixed whereas LKH scheme and OFT scheme grow with the increase of fog users. From the perspective of key generation cost, while a FS joins or leaves the fog network, the proposed scheme is better than LKH scheme and OFT scheme, slightly lower than GKM.

Fig 11. The key storage overhead of different schemes, k=2.

Fig. 12. The key storage overhead of different schemes, k=3.

Fig. 9 and figure 10 show the key generation costs of different key management schemes, when a fog user joins or leaves the fog network. As shown in figure9, when a fog user joins the fog network, the key generation cost of HKM scheme is fixed whereas OFT scheme grows with the increase of fog users.When a fog user leaves the fog network, both the proposed scheme and OFT scheme are increased with the number of fog users. Moreover, the key hypergraph scheme has a faster grow rate than OFT. In order to reduce the server load, the fog computing provider can appropriately increase the number of FSs.

Since the keys should be stored in one secure place, it is necessary to reduce the storage overhead. The key storage overhead of different schemes are depicted in figure 11 and figure 12. The branching factor k is set as 2 and 3 respectively. As shown in these two figures, the other three schemes increase linearly with the growth of fog users, while the storage overhead of the proposed scheme is constant and has lowest overhead. Moreover, the HKM scheme can support more users when the storage space is limited.

VI. CONCLUSIONS

Fog computing extends cloud computing and services to the edge of the network. With the rich potential applications in both wireless network and IoT, the fog computing also opens broad research issues on network security, resource management, big data and novel service delivery. Due to serious limitation of computation resource, a scalable and efficient is necessary in for fog computing. Forcing on the keys security in fog computing, the problem of key management was addressed and HKM, as a new key management scheme based on hypergraph, is presented for security communication.

The design of HKM is closely integrated with the hierarchy architecture of fog computing, which are divided into Cloud-Fog subnetwork and Fog-User subnetwork. The key management processes are designed to satisfy the operational and security requirements of fog computing, which can ensure the forward and backward security, and also make the computation and storage of keys easy to be implemented. The performance evaluation and numerical simulation show that the proposed scheme has low key generation costs and overhead, which can be used to build an efficient secure system for fog computing.