Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The Distributed cloud [16] makes use of resources provided by users in a P2P manner. In the distributed cloud resources are virtualized.. The existing cloud uses huge data centers where resources are provided using virtualization techniques. Some of the voluntary computing systems such as BOINC [14], SETI [15] and Planetlab [20] uses resources provided by users, but these are managed by a central entity and are completely different from either a centralized cloud or the distributed cloud. Unlike users of the existing cloud, who don’t have control over the resources, in the distributed cloud users can choose resources of their choice. Moreover, in the distributed cloud, resources are provided by users. Since users of the distributed cloud have more control over resource selection, they can perform strong encryption to secure their data. The only issue will be managing these keys. We use secret sharing mechanism in this paper to protect secret keys in the distributed cloud.

Secret sharing schemes can mitigate the risks of managing these keys. Secret sharing schemes are used in many cryptographic protocols. Threshold secret sharing scheme is the most widely used technique. The main ides behind the threshold secret sharing schemes was introduced by Shamir [1] and Blakley [2]. In the threshold secret sharing mechanism, information is split into multiple shares and these shares are distributed among multiple users. The only way to retrieve the information back is to have all the shares or a qualified number of shares available. This qualified number is the threshold. This means that any number of shares less than the threshold cannot retrieve the information. Shamir’s secret sharing scheme is based on polynomial interpolation whereas Blakley’s secret sharing scheme is based on geometry. Several secret sharing schemes has been introduced, e.g., threshold secret sharing scheme, ideal secret sharing, linear secret sharing, multi linear secret sharing, [1, 2, 4, 5] etc. The Asmuth and Bloom secret sharing scheme [17] uses the Chinese reminder theorem to reconstruct shares. Multi linear secret sharing schemes [18] uses monotone span programs. In these schemes, secret is a sequence of elements from a finite field and the share is derived using the secret and some random elements from the field. If the secret is of size one i.e. has only one element it is called linear.

In this paper we propose a multilevel threshold secret sharing scheme to provide security of secret key in the distributed cloud. In the first level of the proposed secret sharing scheme we split the secret key into multiple shares and distribute them among multiple resource providers. The second level consists of splitting each share into multiple numbers of sub-secrets at each resource provider. To make our scheme secure we make the determination of threshold value at the second level dynamic. We generate a share pool which is used to determine the number of shares at each resource provider using Chinese Remainder Theorem (CRT) [13]. The advantage of our proposed scheme is that in the distributed cloud, users provide resources and therefore user do not need to invest in the commercial cloud (e.g., Amazon AWS [22], EC2 [23], Windows Azure [24] etc.). Security in the distributed cloud has not been studied much and our scheme provides a way to get a secure way to protect the secret key. We perform the multilevel threshold secret sharing mechanism on the secret key itself as key plays an important role to encrypt or decrypt the file content. In our proposed scheme the secret is distributed over multiple resource providers therefore an attacker cannot have the original secret until and unless all the participating resource providers are compromised. We generate the replica of each secret shares to ensure the fact that if a provider is compromised then that particular share is available from other providers. Moreover the user can revoke the access of any resource provider if the provider is compromised. We increase the chance to detect if a provider is compromised by introducing dummy key shares at each resource provider.

The rest of the paper is organized as follows. In Sects. 2 and 3, we describe related work and present the problem statement respectively. In Sect. 4, we explain our proposed solution. In Sect. 5, we discuss the performance evaluations of our approach and in Sect. 6 we provide our conclusions.

2 Related Work

In this paper we use Shamir’s threshold secret sharing scheme [1]. [1] is an ideal perfect secret sharing scheme as the size of shares are exactly same with the size of each share. A lot of work [5–7] has been developed based on [1]. A threshold ideal secret sharing has been proposed in [6] which uses only XOR operations to make shares and to recover the secret. The authors also show that this scheme is perfect and faster with reduced storage usage and computational cost compared to [1]. In [7] a multilevel threshold secret sharing scheme has been proposed with two modifications of [1]. The first modification allow the shareholders to keep both x coordinate and y- coordinate along with the share of secret and in the second modification a polynomial degree larger than the threshold value is used by the dealers to generate the share. In our scheme we perform splitting the secret twice, once by the user and the other by the resource provider. At resource provider along with the shares we also store dummy shares which improves security. Another type of secret sharing scheme, Linear secret sharing scheme [1, 2, 5] is based on linear algebra and it contains super polynomial lower bounds on the share size. Though [1] can only realize the access structure of the secret sharing scheme, [5] can design a secret sharing scheme from any given access structure. A multi linear secret sharing scheme which uses super polynomial bounds on the share size has been proposed in [4]. In [3] the authors introduce a hierarchical threshold secret sharing scheme. In this scheme secret is shared in a hierarchical structure among groups of participants which is further partitioned into levels.

Security is an important concern for cloud architecture as cloud storage is vulnerable to security threats. Protecting data storage and key management are two of the most important concerns among them. [8–12] concentrate on the cloud storage security and the secure key management scheme in different cloud environments. Cloudstash [8] concentrates on providing the security of the cloud storage. It considers the file as secret and applies secret sharing scheme directly on the multiple shares of secrets. This scheme hashes and signs each share of file and then distributes these signed multi shares into multi clouds. To overcome the limitations of single domain cloud a new second layer in the dependable cloud computing stack named Intercloud has been introduced in [9].This scheme performs symmetric encryption on the data and splits the key into shares using secret sharing scheme. It attaches the key shares as metadata to the pieces of data and distributes them to the clouds. The N cloud scheme [10] propose an improved cloud storage scheme in terms of availability, performance and confidentiality in cloud. It splits the file in many chunks and uploads the encrypted file chunks in geographically separated cloud storage’s in parallel. It also replicates the chunks in non overlapping manner into many cloud storages. To reconstruct the file it downloads the chunks, decrypts them and reassembles them back to a file. This technique manages the encryption keys at client side and does not save them in clouds. To overcome the limitation of single cloud, the DepSky system [11] builds a cloud of clouds named Intercloud, on top of a set of storage clouds by using a combination of diverse commercial clouds. It uses the combination of Byzantine quorum system protocols, cryptographic secret sharing, erasure codes and diversity of several clouds to improve the availability and confidentiality provided by commercial storage cloud. The CloudSeal scheme [12] provides an end to end content confidentiality protection mechanism for large scale content storage. It uses integrated symmetric encryption, threshold secret sharing, and proxy based re- encryption scheme to protect the content and to manage the user access. It also supports forward and backward security. In our multi-level threshold secret sharing scheme we provide security to protect secret key in the distributed cloud.

Fig. 1.
figure 1

Distributed cloud model

Full size image

3 Problem Statement

In the distributed cloud model [16, 21], users do computation and store data in resources provided by other users as shown in Fig. 1. Since users use resources provided by other users, there are obvious security concerns. Dependable Storage in the Intercloud [11], provides reasons why single cloud is not secure, namely, we need to have more than one cloud to make the system more secure. The Distributed cloud model by itself solves the problem of single domain cloud as it has more than one user who will be acting as a cloud provider. In distributed cloud, protecting data stored on other users’ resources poses security issues, which is handled using standard encryption techniques, which in turn leads to key management issues and insider attacks. A resource provider can get access to the data stored on his resources with ease and can use brute force attacks on it. Security of data storage currently depends on how strong encryption keys a user has used or how effective the key management schemes used are. So instead of having a single key that gives access to the encrypted files, we propose using multiple shares. In our proposed secret sharing mechanism in the distributed cloud we use secure mechanisms to enhance the security of secret key shares. We have a share pool that determines the number of shares for a particular key share.

In the distributed cloud, since users can join and leave the cloud, we need to make sure this resource pool is always available. So we make duplicates of this pool and store them for multiple resource providers in all clusters in the distributed cloud.

4 Proposed Solution

4.1 Preliminaries

In this section we discuss the basic preliminaries we use in this paper, that is, Shamir’s threshold secret sharing scheme and Chinese Remainder Theorem.

Shamir’s Threshold Secret Sharing. In this paper we use Shamir’s (k, n) threshold secret sharing scheme [1]. Shamir’s (k, n) threshold secret sharing scheme is based on polynomial interpolation. A secret S can be shared by n number of users and can be reconstructed as well, if the number of shares to reconstruct exceeds some threshold value k. This scheme uses a polynomial function of order \((k-1)\) which can be constructed as,

f(x)= \(d_0\)+ \(d_1x\)+ \(d_2x^2\)+ ....\(d_{k-1}x^{k-1}\) Here \(d_0\) is the secret S. Given any k shares \(<x_0,f(x_0)>,..,<x_{(k-1)},f(x_{(k-1)} ) > \) the secret S can be reconstructed using Lagrange Interpolation formula as follows:

$$\begin{aligned} \sum \nolimits _{i=0}^{k-1} ( \varPi _{i \ne j}\frac{x_{j}}{x_{j}-x_{i}})f(x_i) \end{aligned}$$

Chinese Remainder Theorem. We use the Chinese Remainder Theorem (CRT) [13] to generate the threshold value at each resource provider at the second level of the threshold secret sharing scheme. Given the following system of equations,

$$\begin{aligned} x&=a_1 mod p_1\\ x&=a_2 mod p_2\\&\,.............\\ x&=a_k mod p_k\\ \end{aligned}$$

There is one unique solution as

$$\begin{aligned} x= \sum \nolimits _{(i=1)}^k\frac{P}{p_i} y_i a_i mod P \end{aligned}$$

where \(P= p_1 p_2\)...\(p_k\) and \(\frac{P}{p_i} y_i modp_i=1\), if all moduli are pairwise coprime, i.e., \(gcd(p_i ,p_j )=1\) for every \(i\ne j\).

4.2 Proposed Scheme

The Distributed cloud is formed using the resource provided by users and can provide resource for free to everyone who is part of the system. The Distributed cloud makes use of virtualization to allocate resources to multiple users and shares available resources efficiently and it also avoids single point of failure. In this paper we propose a scheme to protect the secret key using a multilevel threshold secret sharing mechanism shown in Fig. 2 in the distributed cloud environment. Our proposed scheme encrypts the file using the secret key before distributing the key shares among participant resource providers whoom we assume to be honest. At the first level the user splits the key and distributes the shares among resource providers. Instead of attaching key shares as metadata to the pieces of data [9] we split the key shares at each resource provider again into multiple shares in the second level. The second level of our mechanism improves the security since to get the original secret the attacker has to have all the shares from the two levels. We generate the threshold value in the second level dynamically which enhances the security as the attacker cannot know about the threshold value beforehand. In addition to that at each resource provider we create dummy keys which increases the probability of knowing if a resource provider is compromised by any attacker. In Algorithm 1 we ensure the security of the secret key in a distributed cloud environment. To do that we use the multilevel threshold secret sharing scheme (t, n) in which the first level uses the threshold \(t < n\) and the second level uses the threshold \(t = m\).

Fig. 2.
figure 2

Proposed multilevel threshold secret sharing scheme

Full size image

First the user splits the secret key into n number of shares \(S_i\),where \(i \in {(1,n)}\) and distribute them among all resource providers (Algorithm 1.2. line 1 to 7). In this level the threshold value \(t < n\) which indicates that to reconstruct the secret key at least t number of shares would be required. Each share of secret \(S_i\) is replicated into k numbers so that if one resource provider goes offline or compromised then that share can be accessed from other resource provider. At each resource provider we further split the share \(S_i\) into m number of shares \(S_{ij}\) (Algorithm  1.2. line 12). At this level, i.e., second level the threshold value m is generated dynamically. To determine the number of shares m each resource provider \(R_i,i\in {(1,n)}\) selects a \((P_i,N_i)\) pair from the share pool SP (Algorithm 1.2 line 9 to 12). The share pool is created beforehand (Algorithm 1.1. Generate share pool SP).The user saves the pair \((i,P_i)\) for each provider \(R_i\) and the provider saves \(N_i\). We intend to have multiple share pools and place one or two of them in each cluster of the distributed cloud. The CRT solution generates a number m which decides the number of shares to split and reconstruct in the second level. At each resource provider at least j number of dummy shares \(S_{ij}^D\),where \(i \in {(1,n)}\) and \(j\ge m\), are generated (Algorithm 1.2 line 13). Whenever a resource provider is compromised, the user revokes the access of that particular resource provider. We intend to have a greater number of dummy shares than secret shares,i.e.,\(j\ge m\), so that if any outside attacker tries to get the share, the probability that he ends up with the dummy share instead of a real share is greater than or equal to 0.5. This helps the user to take action (e.g., revoke the access of that resource provider) accordingly when some attacker selects a dummy key. To reconstruct the key sub shares, each resource provider need to have the \(P_i\) from the user to generate the threshold value m (Algorithm 1.3. line 2). The user reconstructs the secret S from t numbers of \(S_i\) shares.

Algorithm 1

Input: The secret key S, n number of resource providers in distributed cloud, threshold value \(t \le n\).

Algorithm 1.1. Generate share pool SP

From this share pool each resource provider generates a number out of a selected pair.

figure a

Algorithm 1.2. Split Algorithm

figure b

Algorithm 1.3. Reconstruction Algorithm

figure c

5 Analysis

5.1 Experimental Analysis

We performed simulations using a distributed cloud model that is based on the P2P overlay Kademlia [19]. We implemented our algorithm for secret sharing on the distributed cloud. We assumed that resource providers have a minimum of 2 GB RAM up to 16 GB, 2 to 8 cores. First a node identifies available resource providers near him and then divides the key into multiple shares and distributes each share to an available resource provider. The Resource provider again creates more shares by using his share as the secret and stores it. User will maintain the list of providers who store the secret shares. When a user requires the key, he contacts other resource providers who have the shares. Once resource providers receive the request, they combine the shares they have and send the actual share to the user. Once the threshold numbers of shares are received by the user, he will reproduce the original key and use it. Figure 3 shows the average total time. The total time includes time taken to split the secret into shares at first level, find resources, distribute the shares to resource providers and split the shares at second level. We can see that as the number of nodes increases, the time to find nodes and distribute shares to nearby nodes decreases. Since the distributed cloud is formed by many users we can see our mechanism for secret sharing is feasible and efficient.

Fig. 3.
figure 3

Time to split shares and distribute them to other nodes

Full size image

Figure 4 shows the time to retrieve the shares from resource providers and combine them to reproduce the secret. We see that the average time to retrieve shares from resource providers and to combine them takes significantly less time when compared to distributing the shares. In order to make sure that we have shares available to the user any time we will make replicas of shares and store them on multiple resource providers in the distributed cloud. This increases the chances of retrieving the share efficiently even when some of the nodes leave the network.

Fig. 4.
figure 4

Time to retrieve shares and combine them

Full size image

5.2 Security Analysis

In this paper since we are using a threshold secret sharing scheme and we are storing the shares and their replicas on multiple resource providers, compromising one or more resource providers will not disclose the secret. At the second level at each resource provider we generate equal or more dummy shares which an attacker may access as actual shares. If the resource provider is compromised by any outside attacker then the probability of using the dummy shares is greater than or equal to 0.5. This increases the chances for a resource provider to react to any security breach immediately. We create a share pool to reduce the user overhead in deciding the number of shares to be split. Since the resource provider selects \((P_i,N_i)\) pairs randomly no eavesdropper can make a guess about the number of shares beforehand. In the distributed cloud model we have used, RP’s are selected using game theory [25], which ensures that RP’s are honest. This ensures that our model is not vulnerable to collusion attack

6 Conclusion

In this paper we propose a multilevel threshold secret sharing scheme to ensure the security of secret key in the distributed cloud environment. Our scheme can also be used for other distributed and P2P systems. Our findings show that a secret key, which plays a significant role to encrypt and decrypt the file content to be stored in cloud storage, can be stored securely in a distributed cloud environment. The increasing number of providers in the distributed cloud decreases the time to split and distribute the shares. Experimental and security analysis shows that our scheme is feasible and secure. Data replication is an other issue in distributed systems and we will look into new strategies to perform data replication to increase response time for finding data and making distributed cloud more robust.