Privacy-Preserving Protocol for Data Stored in the Cloud

The work is supported by the National Natural Science Foundation of China under Grant No. 60873231, the National Basic Research Program of China (“973” Program) under Grant No. 2011CB302903, the High Education Natural Science Foundation of Jiangsu Province under Grant No. 08KJB520006 and Funds of Key Lab of Fujian Province University Network Security and Cryptology under Grant No. 09A010, and Innovation Project for postgraduate cultivation of Jiangsu Province, China under Grant No. CX10B_195Z.

    Cloud computing is a new service platform. When data is stored in clouds, the owner no longer has physical possession of the data’s storage. But untrusted service providers have independent administrator authority over the data, and this creates potential security threats.  Data integrity is also a security challenge in cloud computing [1]. Protecting the privacy of data owners has become a new challenge in cloud computing [2].

    In this paper, we propose a privacy-preserving protocol with elliptic curve cryptography and secret sharing. In a given scenario, service providers comprise coordinate servers in which sensitive data (entries of cloud databases) are re-computed with k servers (k  is a threshold value). Users also verify the shares from k  servers on the condition that they (the users) only rely on the trust of data owners’ signatures.

1 Related Work
    Identity-Based Encryption (IBE) is a key technique for the proposed protocol. A novel IBE on a bilinear map was proposed in [3]. However, it failed in a distributed environment and did not prevent collusion between k  dishonest service providers. Joonsang Baek [4] constructed the first identity-based threshold decryption, which is secure against chosen-ciphertext attack.

    Baek’s scheme is based on the concept of “federal identity,” introduced by Liang Yan [5], and is a new solution to strengthening cloud security.

    Brian Thompson [6] leveraged database entries of data owners as shared secrets. Owner identities can be replaced by database entries and used as owners’ signatures. This can prevent disclosure of private information from the identity. Cong Wang [2] introduced a third party auditor (TPA) to audit cloud service providers before a user accesses cloud storage services. TPA guarantees that data integrity will be maintained and service providers will behave ethically.

    We use database entries as federal identities to verify service providers’ data. We also use threshold encryption on a bilinear map to adapt to distributed cloud storage.

2 The Proposed Model and Protocol

2.1 The Proposed Model
    The model we propose aims to protect cloud data against untrusted service providers. This model involves data owners, cloud service providers, and data users, as shown in Fig. 1. Data owners store data in the cloud and send every share of data entries to k service providers. Cloud service providers collaboratively store data, especially the shares of cloud databases entries. They have the signature of database entries (shadow secret) from data owners. Data users access data from the service providers and have access to the public information of data owners in order to verify the shares received from service providers.

2.2 Process of The Proposed Protocol
    The proposed protocol is based on IBE [3] and secret sharing [7]. The identity in this protocol is replaced by the entry of cloud databases as a secret to be shared. Strings or multimedia data can be converted by hash functions. A data owner outsources the database (such as m shares of the entry for the database) to m service providers and requires that at least any k servers can reconstruct the entry of the database collaboratively. However, k-1 servers cannot. Shadow secrets are also proposed to verify each share of the entry. Furthermore, the data owner and data user can delegate one of m providers as the primary provider SPu  in order to reduce the cost of communication. SPu gathers other k-1 shares and shadow secrets and sends k  shares to users. This solution requires that should be absolutely trustworthy. Finally, the primary provider (delegated by data users) reconstructs the entry of the database and verifies the shares of other k-1 providers with shadow secrets.

    The proposed protocol is implemented in four phases:  initialization, distribution, verification, and reconstruction.

    (1)  Initialization
    The proposed model takes a security parameter h and chooses a big primer p (h bit) in order to find a hypersingular elliptic curve E/GF(p). The following notations are used:

• l is the length of  plaintext, and we use hash function to convert entry x into plaintext
• P is the generator of subgroup (G,+) in E/GF(p)
• q (q>2h) is the order of (G, +)
• G and G* are two (multiplicative) cyclic groups of prime order p    
• Zq* denotes the group {0; . . . ; q-1} under addition modulo q
• e:  is a bilinear map e: G×G →GF(P 2)*
• H1, H2 are one-way hash functions H1: {0,1}*→G *; H2: GF (P 2)*→{0,1}'.

    First, a master key s is chosen to compute system public key Ppub=sP. Broadcast system parameters {G, q, P, e, H1, H2, Ppub} are also set for data owners, data users, and service providers.

  
    The process of distributing shares has the following six steps :
Step1: Execute the function Extract from IBE [3] to compute a key pair <QE, DE>, QE=H1(E); DE =sQE

    Step2: Randomly choose k coefficients from G* {aj |aj∈G*; j=1,2,…,k-1; ak-1≠0} and compue m shares of De with a polynomial F (x ) of order k-1,

    Step3: Compute service provider SPi’s shadow secret Si=F (i ), then compute yi =e (Si, P ), 1≤i≤m

    Step4: Compute verification key Uj=e (aj, Ppub), 1≤j≤t-1, U0=e(DID, Ppub)

    Step5: Send Si to SPi with a private channel, and broadcast yi, Uj; 1≤i≤m, 0≤j≤k-1

    Step6: Compute Proof for verification key.

    After choosing wi∈(G, +), data owners compute E1i =e (wi, Ppub), E2i =
e (wi, P ), ci =H2(E1i +E2i), ri =wi -Si ci  mod q. Owners broadcast PROOFi =(ri , ci ), 1≤i≤m.

    (3) Verification
    SPμ applies for other k-1 providers’ shadow secrets Si  and uses the public information to verify the validity of Si  in the following steps:

    (a) SPμ collects Ui (0≤i≤k -1),yi (1≤i≤m) to compute 

    (b) It verifies E1i =e (ri, Ppub)Yi    , E2i =e (ri, P )Yi       and then H2 (E1i +E2i ) to compare with ci from PROOFi =(ri , ci). If the result is equal, Si is proven valid.

    (4) Reconstruction
    After verification, SPμ collects Si from other k-1 service providers. Given the ciphertext <C, U >, SPμ uses the following expression to revert to the entry E:

Then following IBE, SPμ reduces the entry E:

2.3 Verification of the Proposed Protocol
    The proposed protocol is proven correct by calculating Yi, given Ui (0≤i≤k -1).

    (1) Verification of the validity of shadow secret Si

    The primary provider SPm collects information set (Ppub, Ui; P,yi; Si ) for the verification. 
    The correctness of  is given below:

 According to Yi , yi , it is easy to prove the correctness of PROOFi =(ri , ci) as follows:

    With the computation of ci in PROOFi =(ri, ci), H2(E1i +E2i ) is equal to ci. PROOFi =(ri, ci) can prove the validity of Si.

    (2) Reconstruction of the entry (E) of the database:
    After verifying k (threshold value) shadow secrets Si, the primary provider computes a bilinear map with U  in the ciphertext and Sj. The correctness is proven as follows:

    According to IBE, SPμ reverts the entry E = C ??H2 (sum).

3 Simulation
    The simulation was conducted using C language on a Windows XP system running on two 2.0 GHz Intel Core processors each with 2 GB of RAM and a Western Digital 320 GB Serial ATA driver. Multiprecision Integer and Rational Arithmetic C/C++ Library (MIRACL) version 5.3 was used. The simulation result is the mean of ten trials.

    (1) Cost of Distributing Shares of Secret and Signature by Data Owners
    We assess the performance of distributing shares according to two criteria: CPU time and the number of shares distributed. As shown in Fig.2, when the total number of service providers increases (based on different threshold values), the time cost increases. When the threshold value increases, the time cost also increases. So when a data owner distributes shares of database entry and signature, the total number of service providers, as well as the threshold value, needs to be considered. Moreover, in order to guarantee protection against collusion from service providers, the range of the threshold should be considered. A threshold value of half the total number of service providers is a good choice for balancing security and efficiency.

    (2) Comparison of the Time Costs of Distribution, Verification, and Reconstruction by Data Users
    The time cost of reconstruction and of verification are similar at the same threshold level regardless of the total number of service providers, as shown in Figs. 3 and 4. In the proposed protocol, verification and reconstruction are run by the primary service providers delegated by data users. So the primary service provider can save communication cost by gathering k-1 shares. The figures show that efficiency in verification and reconstruction is greater than that in distribution.

4 Conclusion
    In this paper, we propose a privacy-preserving protocol for data storage in the cloud. We focus on stopping data being disclosed by untrusted service providers when data owners distribute their database entries. By using IBE algorithm and a secret-sharing scheme, the protocol protects against collusion by multiple service providers. The simulations show that regardless of network environment, the proposed protocol is correct and efficient.

References
[1] W. Zeng, Y. Zhao, O. Kairi, and W. Song, "Research on cloud storage architecture and key technologies," in Proc. 2nd Int. Conf. Interaction Sciences, Seoul, 2009, pp.1044-1048.
[2] Q. Wang, C. Wang, K. Ren, and W. Lou, "Privacy-preserving public auditing for data storage security in cloud computing," in Proc. IEEE INFOCOM, San Diego, CA, 2010,  pp.1-9.
[3] D. Boneh, B. Lynn, and H. Shacham, "Short signatures from the weil pairing," J. Cryptology, vol.17, no.4, pp. 297-319, 2004.
[4] J. Baek, and Y. Zheng, "Identity-based threshold decryption," in Proc. 7th Int. Workshop on Public Key Cryptography (PCK 2004), Singapore, pp.262-276.
[5] L. Yan,  C. Rong, and G. Zhao, "Strengthen cloud computing security with federal identity management using hierarchical identity-based cryptography," in Proc. 1st Int. Conf. Cloud Comput. (CloudCom’09), Beijing, pp. 167-177.
[6] B. Thompson, S. Haber, W.G. Horne, and T. Sander, D. Yao, "Privacy-preserving computation and verification of aggregate queries on outsourced databases," in Proc. 9th Int. Symp. on Privacy Enhancing Tech.(PETS’09), Seattle, WA, pp.185-201.
[7] A. Shamir, "How to share a secret," in Commun. ACM, vol.22, no.11, pp.612-13, 1979.
[8] A. Shraer, C. Cachin, A. Cidon, I. Keidar, Y. Michalevsky, and D. Shaket, "Venus: Verification for untrusted cloud storage," in Proc. ACM Workshop on Cloud Comput. Security (CCSW’10), Chicago, Ill., pp.19-30.
[9] E. Bertino, F. Paci, and R. Ferrini, "Privacy-preserving digital identity management for cloud computing," IEEE Comput. Soc. Data Engineering Bulletin, pp. 1-4, 2009.
[10] W. Itani, A. Kayssi, and A. Chehab, "Privacy as a Service: Privacy-Aware Data Storage and Processing in Cloud Computing Architectures," in Proc. 8th IEEE Int. Conf. on Dependable, Autonomic and Secure Comput., Chengdu, China, 2009, pp.711-716.

    First, a master key s is chosen to compute system public key Ppub=sP. Broadcast system parameters {G, q, P, e, H1, H2, Ppub} are also set for data owners, data users, and service providers.

    (2) Distribution
    The data owner distributes m shares of the entry E of the database to m service providers along with the verification key. Let E  be the entry of database, and use IBE to produce plaintext(c,u ), where

    (2) Distribution
    The data owner distributes m shares of the entry E of the database to m service providers along with the verification key. Let E  be the entry of database, and use IBE to produce plaintext(c,u ), where

[Abstract] Data storage is an important application of cloud computing. With a cloud computing platform, the burden of local data storage can be reduced. However, services and applications in a cloud may come from different providers, and creating an efficient protocol to protect privacy is critical. We propose a verification protocol for cloud database entries that protects against untrusted service providers. Based on identity-based encryption (IBE) for cloud storage, this protocol guards against breaches of privacy in cloud storage. It prevents service providers from easily constructing cloud storage and forging the signature of data owners by secret sharing. Simulation results confirm the availability and efficiency of the proposed protocol.

[Keywords] privacy; cloud storage; IBE; secret sharing

The work is supported by the National Natural Science Foundation of China under Grant No. 60873231, the National Basic Research Program of China (“973” Program) under Grant No. 2011CB302903, the High Education Natural Science Foundation of Jiangsu Province under Grant No. 08KJB520006 and Funds of Key Lab of Fujian Province University Network Security and Cryptology under Grant No. 09A010, and Innovation Project for postgraduate cultivation of Jiangsu Province, China under Grant No. CX10B_195Z.

    Cloud computing is a new service platform. When data is stored in clouds, the owner no longer has physical possession of the data’s storage. But untrusted service providers have independent administrator authority over the data, and this creates potential security threats.  Data integrity is also a security challenge in cloud computing [1]. Protecting the privacy of data owners has become a new challenge in cloud computing [2].

    In this paper, we propose a privacy-preserving protocol with elliptic curve cryptography and secret sharing. In a given scenario, service providers comprise coordinate servers in which sensitive data (entries of cloud databases) are re-computed with k servers (k  is a threshold value). Users also verify the shares from k  servers on the condition that they (the users) only rely on the trust of data owners’ signatures.

1 Related Work
    Identity-Based Encryption (IBE) is a key technique for the proposed protocol. A novel IBE on a bilinear map was proposed in [3]. However, it failed in a distributed environment and did not prevent collusion between k  dishonest service providers. Joonsang Baek [4] constructed the first identity-based threshold decryption, which is secure against chosen-ciphertext attack.

    Baek’s scheme is based on the concept of “federal identity,” introduced by Liang Yan [5], and is a new solution to strengthening cloud security.

    Brian Thompson [6] leveraged database entries of data owners as shared secrets. Owner identities can be replaced by database entries and used as owners’ signatures. This can prevent disclosure of private information from the identity. Cong Wang [2] introduced a third party auditor (TPA) to audit cloud service providers before a user accesses cloud storage services. TPA guarantees that data integrity will be maintained and service providers will behave ethically.

    We use database entries as federal identities to verify service providers’ data. We also use threshold encryption on a bilinear map to adapt to distributed cloud storage.

2 The Proposed Model and Protocol

2.1 The Proposed Model
    The model we propose aims to protect cloud data against untrusted service providers. This model involves data owners, cloud service providers, and data users, as shown in Fig. 1. Data owners store data in the cloud and send every share of data entries to k service providers. Cloud service providers collaboratively store data, especially the shares of cloud databases entries. They have the signature of database entries (shadow secret) from data owners. Data users access data from the service providers and have access to the public information of data owners in order to verify the shares received from service providers.

2.2 Process of The Proposed Protocol
    The proposed protocol is based on IBE [3] and secret sharing [7]. The identity in this protocol is replaced by the entry of cloud databases as a secret to be shared. Strings or multimedia data can be converted by hash functions. A data owner outsources the database (such as m shares of the entry for the database) to m service providers and requires that at least any k servers can reconstruct the entry of the database collaboratively. However, k-1 servers cannot. Shadow secrets are also proposed to verify each share of the entry. Furthermore, the data owner and data user can delegate one of m providers as the primary provider SPu  in order to reduce the cost of communication. SPu gathers other k-1 shares and shadow secrets and sends k  shares to users. This solution requires that should be absolutely trustworthy. Finally, the primary provider (delegated by data users) reconstructs the entry of the database and verifies the shares of other k-1 providers with shadow secrets.

    The proposed protocol is implemented in four phases:  initialization, distribution, verification, and reconstruction.

    (1)  Initialization
    The proposed model takes a security parameter h and chooses a big primer p (h bit) in order to find a hypersingular elliptic curve E/GF(p). The following notations are used:

• l is the length of  plaintext, and we use hash function to convert entry x into plaintext
• P is the generator of subgroup (G,+) in E/GF(p)
• q (q>2h) is the order of (G, +)
• G and G* are two (multiplicative) cyclic groups of prime order p    
• Zq* denotes the group {0; . . . ; q-1} under addition modulo q
• e:  is a bilinear map e: G×G →GF(P 2)*
• H1, H2 are one-way hash functions H1: {0,1}*→G *; H2: GF (P 2)*→{0,1}'.

    First, a master key s is chosen to compute system public key Ppub=sP. Broadcast system parameters {G, q, P, e, H1, H2, Ppub} are also set for data owners, data users, and service providers.

  
    The process of distributing shares has the following six steps :
Step1: Execute the function Extract from IBE [3] to compute a key pair <QE, DE>, QE=H1(E); DE =sQE

    Step2: Randomly choose k coefficients from G* {aj |aj∈G*; j=1,2,…,k-1; ak-1≠0} and compue m shares of De with a polynomial F (x ) of order k-1,

    Step3: Compute service provider SPi’s shadow secret Si=F (i ), then compute yi =e (Si, P ), 1≤i≤m

    Step4: Compute verification key Uj=e (aj, Ppub), 1≤j≤t-1, U0=e(DID, Ppub)

    Step5: Send Si to SPi with a private channel, and broadcast yi, Uj; 1≤i≤m, 0≤j≤k-1

    Step6: Compute Proof for verification key.

    After choosing wi∈(G, +), data owners compute E1i =e (wi, Ppub), E2i =
e (wi, P ), ci =H2(E1i +E2i), ri =wi -Si ci  mod q. Owners broadcast PROOFi =(ri , ci ), 1≤i≤m.

    (3) Verification
    SPμ applies for other k-1 providers’ shadow secrets Si  and uses the public information to verify the validity of Si  in the following steps:

    (a) SPμ collects Ui (0≤i≤k -1),yi (1≤i≤m) to compute 

    (b) It verifies E1i =e (ri, Ppub)Yi    , E2i =e (ri, P )Yi       and then H2 (E1i +E2i ) to compare with ci from PROOFi =(ri , ci). If the result is equal, Si is proven valid.

    (4) Reconstruction
    After verification, SPμ collects Si from other k-1 service providers. Given the ciphertext <C, U >, SPμ uses the following expression to revert to the entry E:

Then following IBE, SPμ reduces the entry E:

2.3 Verification of the Proposed Protocol
    The proposed protocol is proven correct by calculating Yi, given Ui (0≤i≤k -1).

    (1) Verification of the validity of shadow secret Si

    The primary provider SPm collects information set (Ppub, Ui; P,yi; Si ) for the verification. 
    The correctness of  is given below:

 According to Yi , yi , it is easy to prove the correctness of PROOFi =(ri , ci) as follows:

    With the computation of ci in PROOFi =(ri, ci), H2(E1i +E2i ) is equal to ci. PROOFi =(ri, ci) can prove the validity of Si.

    (2) Reconstruction of the entry (E) of the database:
    After verifying k (threshold value) shadow secrets Si, the primary provider computes a bilinear map with U  in the ciphertext and Sj. The correctness is proven as follows:

    According to IBE, SPμ reverts the entry E = C ??H2 (sum).

3 Simulation
    The simulation was conducted using C language on a Windows XP system running on two 2.0 GHz Intel Core processors each with 2 GB of RAM and a Western Digital 320 GB Serial ATA driver. Multiprecision Integer and Rational Arithmetic C/C++ Library (MIRACL) version 5.3 was used. The simulation result is the mean of ten trials.

    (1) Cost of Distributing Shares of Secret and Signature by Data Owners
    We assess the performance of distributing shares according to two criteria: CPU time and the number of shares distributed. As shown in Fig.2, when the total number of service providers increases (based on different threshold values), the time cost increases. When the threshold value increases, the time cost also increases. So when a data owner distributes shares of database entry and signature, the total number of service providers, as well as the threshold value, needs to be considered. Moreover, in order to guarantee protection against collusion from service providers, the range of the threshold should be considered. A threshold value of half the total number of service providers is a good choice for balancing security and efficiency.

    (2) Comparison of the Time Costs of Distribution, Verification, and Reconstruction by Data Users
    The time cost of reconstruction and of verification are similar at the same threshold level regardless of the total number of service providers, as shown in Figs. 3 and 4. In the proposed protocol, verification and reconstruction are run by the primary service providers delegated by data users. So the primary service provider can save communication cost by gathering k-1 shares. The figures show that efficiency in verification and reconstruction is greater than that in distribution.

4 Conclusion
    In this paper, we propose a privacy-preserving protocol for data storage in the cloud. We focus on stopping data being disclosed by untrusted service providers when data owners distribute their database entries. By using IBE algorithm and a secret-sharing scheme, the protocol protects against collusion by multiple service providers. The simulations show that regardless of network environment, the proposed protocol is correct and efficient.

References
[1] W. Zeng, Y. Zhao, O. Kairi, and W. Song, "Research on cloud storage architecture and key technologies," in Proc. 2nd Int. Conf. Interaction Sciences, Seoul, 2009, pp.1044-1048.
[2] Q. Wang, C. Wang, K. Ren, and W. Lou, "Privacy-preserving public auditing for data storage security in cloud computing," in Proc. IEEE INFOCOM, San Diego, CA, 2010,  pp.1-9.
[3] D. Boneh, B. Lynn, and H. Shacham, "Short signatures from the weil pairing," J. Cryptology, vol.17, no.4, pp. 297-319, 2004.
[4] J. Baek, and Y. Zheng, "Identity-based threshold decryption," in Proc. 7th Int. Workshop on Public Key Cryptography (PCK 2004), Singapore, pp.262-276.
[5] L. Yan,  C. Rong, and G. Zhao, "Strengthen cloud computing security with federal identity management using hierarchical identity-based cryptography," in Proc. 1st Int. Conf. Cloud Comput. (CloudCom’09), Beijing, pp. 167-177.
[6] B. Thompson, S. Haber, W.G. Horne, and T. Sander, D. Yao, "Privacy-preserving computation and verification of aggregate queries on outsourced databases," in Proc. 9th Int. Symp. on Privacy Enhancing Tech.(PETS’09), Seattle, WA, pp.185-201.
[7] A. Shamir, "How to share a secret," in Commun. ACM, vol.22, no.11, pp.612-13, 1979.
[8] A. Shraer, C. Cachin, A. Cidon, I. Keidar, Y. Michalevsky, and D. Shaket, "Venus: Verification for untrusted cloud storage," in Proc. ACM Workshop on Cloud Comput. Security (CCSW’10), Chicago, Ill., pp.19-30.
[9] E. Bertino, F. Paci, and R. Ferrini, "Privacy-preserving digital identity management for cloud computing," IEEE Comput. Soc. Data Engineering Bulletin, pp. 1-4, 2009.
[10] W. Itani, A. Kayssi, and A. Chehab, "Privacy as a Service: Privacy-Aware Data Storage and Processing in Cloud Computing Architectures," in Proc. 8th IEEE Int. Conf. on Dependable, Autonomic and Secure Comput., Chengdu, China, 2009, pp.711-716.

    First, a master key s is chosen to compute system public key Ppub=sP. Broadcast system parameters {G, q, P, e, H1, H2, Ppub} are also set for data owners, data users, and service providers.

    (2) Distribution
    The data owner distributes m shares of the entry E of the database to m service providers along with the verification key. Let E  be the entry of database, and use IBE to produce plaintext(c,u ), where

    (2) Distribution
    The data owner distributes m shares of the entry E of the database to m service providers along with the verification key. Let E  be the entry of database, and use IBE to produce plaintext(c,u ), where

[Abstract] Data storage is an important application of cloud computing. With a cloud computing platform, the burden of local data storage can be reduced. However, services and applications in a cloud may come from different providers, and creating an efficient protocol to protect privacy is critical. We propose a verification protocol for cloud database entries that protects against untrusted service providers. Based on identity-based encryption (IBE) for cloud storage, this protocol guards against breaches of privacy in cloud storage. It prevents service providers from easily constructing cloud storage and forging the signature of data owners by secret sharing. Simulation results confirm the availability and efficiency of the proposed protocol.

[Keywords] privacy; cloud storage; IBE; secret sharing