# A Lightweight Identity-Based Cloud Storage Auditing Supporting Proxy Update and Workload-Based Payment

Authors: Wenting Shen; Jing Qin; Jixin Ma
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Cloud storage auditing allows the users to store their data to the cloud with a guarantee that the data integrity can be efficiently checked. In order to release the user from the burden of generating data signatures, the proxy with a valid warrant is introduced to help the user process data in lightweight cloud storage auditing schemes. However, the proxy might be revoked or the proxy’s warrant might expire. These problems are common and essential in real-world applications, but they are not considered and solved in existing lightweight cloud storage auditing schemes. In this paper, we propose a lightweight identity-based cloud storage auditing scheme supporting proxy update, which not only reduces the user’s computation overhead but also makes the revoked proxy or the expired proxy unable to process data on behalf of the user any more. The signatures generated by the revoked proxy or the expired proxy can still be used to verify data integrity. Furthermore, our scheme also supports workload-based payment for the proxy. The security proof and the performance analysis indicate that our scheme is secure and efficient.


---

## Body

## 1. Introduction

Cloud storage enables users to store their data in the cloud without retaining a copy locally. It greatly reduces the burden of data storage management and maintenance and avoids the capital expenditure on software/hardware on the user side. Although cloud storage provides a lot of appealing benefits for users, it also incurs a number of security challenges [1]. Once the users upload their data to the cloud, they will lose the physical control of their data since they no longer keep their data locally. Thus, it is natural for users to worry whether their data stored in the cloud is intact or not due to the inevitable human errors or software/hardware bugs in the cloud. In order to guarantee the data integrity and reduce the user’s computation and communication burden, some public cloud storage auditing schemes [2–4] have been proposed to allow a public verifier, such as the Third Party Auditor (TPA), to perform periodical data integrity auditing tasks on behalf of users.In most existing public cloud storage auditing schemes, the user relieves the computation burden for verifying data integrity by introducing the TPA, but he still needs to perform heavy computation for generating data signatures before uploading data to the cloud. These data signatures are used to check the integrity of cloud data. In order to deal with the above problem, several lightweight cloud storage auditing schemes [5–8] have been proposed. Wang et al. [5] proposed a proxy-oriented data integrity auditing scheme. In this scheme, the proxy helps the user to generate data signatures, which obviously alleviates the user’s computation burden. Shen et al. [6] constructed a lightweight cloud storage auditing scheme, which introduces the Third Party Medium (TPM) to generate data signatures and verify the data integrity for users. These schemes introduced a proxy with powerful computation capabilities to execute time-consuming operation on behalf of users. Nevertheless, there are two critical problems not well solved in all existing lightweight cloud storage auditing schemes.Firstly, these lightweight cloud storage auditing schemes cannot support proxy update. In real-world applications, in order to designate a proxy, the user needs to issue a warrant with a valid time period to this proxy. The cloud will verify whether the proxy is valid based on this warrant. Furthermore, the proxy might be revoked before the expiration of this valid time period. For instance, a user with low computation capabilities delegates a proxy to help him process data. The proxy can be a legal organization which has significant computation resources. The user and the proxy sign a contract with a specific valid time period. Once the contract expires, the expired proxy should not be able to process data on behalf of the user any more. Another situation is that the user wants to change the proxy before the expiration of the contract’s valid time period due to the misbehaviour of the proxy. This revoked proxy also should not be able to process data for the user any more even if his warrant is still in a valid time period. Thus, how to design a lightweight cloud storage auditing supporting proxy update is worthwhile.Secondly, existing lightweight cloud storage auditing schemes do not consider the mechanism of paying for the proxy based on the workload. In the lightweight cloud storage auditing scenario, the user delegates a proxy to upload files to the cloud on his behalf. However, the number of these uploaded files might be greatly different in different time period. Obviously, it is unfair for the proxy if we pay for the proxy according to service time. It is more reasonable to pay for the proxy according to how many files he uploads to the cloud. Therefore, it is necessary to design an effective mechanism to pay for the proxy based on the workload in cloud storage auditing.Contribution. In order to deal with the above problems, we propose a novel lightweight identity-based cloud storage auditing scheme. In this scheme, we introduce a proxy to help the user generate data signatures, which remarkably releases the users’ burden on computation. Different from the previous lightweight cloud storage auditing schemes, our proposed scheme supports proxy update. In the detailed scheme, the user issues a warrant to the designated proxy. The proxy with the valid warrant can process data on behalf of the user. In order to realize effective proxy update, the valid time period and the proxy identity are embedded into the warrant and the cloud keeps a public revocation list. It makes the revoked proxy or the expired proxy unable to process and upload data to the cloud on behalf of the user any more. When the proxy is revoked or the proxy’s warrant expires, the signatures generated by this proxy can still be used to check data integrity according to this proxy identity, the corresponding time period, and some verification values. We also design an effective mechanism to achieve workload-based payment for the proxy. Our scheme relies on identity-based cryptography, which simplifies certificate management. We finally prove the security of the scheme and evaluate the performance of the scheme by concrete implementations.


### 1.1. Related Work

Ateniese et al. [2] firstly proposed the notion of Provable Data Possession (PDP), in which the techniques of homomorphic authenticators and random sample are utilized to verify the integrity of data in the cloud. To achieve the retrievability and the integrity guarantee of the cloud data, Juels and Kaliski [9] proposed the concept of Proof of Retrievability (PoR) and designed a concrete scheme by employing the techniques of the spot-checking and the error-correcting codes. Later, many variants of PDP and PoR schemes [10–13] were constructed to deal with different problems in cloud storage auditing.In order to protect data privacy, Wang et al. [13] proposed a cloud storage auditing scheme with data privacy preserving by using a random masking technique. Li et al. [14] presented a privacy preserving remote data integrity auditing scheme based on the zero-knowledge proof. To support data dynamic operations, Liu et al. [15] designed a dynamic data integrity auditing scheme with efficient fine-grained updates based on the Merkle hash tree. Tian et al. [16] proposed a cloud storage auditing scheme supporting data dynamics with the employment of dynamic hash table. By utilizing key update techniques [17], Yu et al. [18] solved the problem of key exposure in cloud storage auditing. The privacy preserving of authentication in cloud storage auditing was considered in [19]. The problem of users’ identity privacy in shared data auditing was taken into account in [20, 21].To eliminate the complex certificate management in PKI setting, Wang et al. [22] constructed the first identity-based remote data integrity auditing scheme. Based on identity-based cryptosystem, Yu et al. [23] designed a perfect data privacy-preserving cloud storage auditing scheme, which is able to achieve zero knowledge privacy against a third party auditor. Li et al. [24] proposed a fuzzy identity-based cloud storage auditing scheme, in which a set of descriptive attributes is used as a user’s identity. Zhang et al. [25] considered the problem of user revocation in the cloud storage auditing and presented an identity-based shared data integrity auditing scheme supporting real efficient user revocation. Shen et al. [26] proposed an identity-based cloud storage auditing scheme for shared data. In this scheme, the cloud file can be shared and used by others under the condition that the sensitive information is hidden.Most end users, such as smart phone, have constrained computation resources and computation capabilities. In order to alleviate the user’s computation burden, many lightweight cloud storage auditing schemes were proposed. Li. et al. [27] and Wang et al. [28], respectively, proposed cloud storage auditing schemes for low-performance end devices based on online/offline signatures. In these two schemes, most heavy computations are executed in the offline phase. Nonetheless, the user still needs to carry out lightweight computations for generating data signatures in the online phase. In order to deal with this problem, Wang et al. [5] proposed an identity-based cloud storage auditing scheme by introducing a proxy to help users generate data signatures. In this scheme, the user does not need to consume computation resources to generate data signatures. Shen et al. [6] designed a lightweight data integrity auditing scheme for cloud storage, in which the Third Party Medium (TPM) is introduced to process data on behalf of users. Wang et al. [8] constructed a comprehensive cloud storage auditing scheme. In this scheme, the user delegates the task of data signature generation to a dedicated proxy. However, all these schemes that introduce the proxy do not consider the problem of proxy update. In addition, the problem of workload-based payment was also not taken into account. Actually, these problems are common and essential in real-world applications as discussed above.


### 1.2. Organization

The rest of this paper is organized as follows. We present the system model and design goals in Section2. In Section 3, we give the notations and the definition and review several cryptographic knowledge. The proposed cloud storage auditing scheme is introduced in Section 4. The security proof and performance evaluation of the proposed scheme are given, respectively, in Section 5 and Section 6. Section 7 concludes the paper.


## 1.1. Related Work

Ateniese et al. [2] firstly proposed the notion of Provable Data Possession (PDP), in which the techniques of homomorphic authenticators and random sample are utilized to verify the integrity of data in the cloud. To achieve the retrievability and the integrity guarantee of the cloud data, Juels and Kaliski [9] proposed the concept of Proof of Retrievability (PoR) and designed a concrete scheme by employing the techniques of the spot-checking and the error-correcting codes. Later, many variants of PDP and PoR schemes [10–13] were constructed to deal with different problems in cloud storage auditing.In order to protect data privacy, Wang et al. [13] proposed a cloud storage auditing scheme with data privacy preserving by using a random masking technique. Li et al. [14] presented a privacy preserving remote data integrity auditing scheme based on the zero-knowledge proof. To support data dynamic operations, Liu et al. [15] designed a dynamic data integrity auditing scheme with efficient fine-grained updates based on the Merkle hash tree. Tian et al. [16] proposed a cloud storage auditing scheme supporting data dynamics with the employment of dynamic hash table. By utilizing key update techniques [17], Yu et al. [18] solved the problem of key exposure in cloud storage auditing. The privacy preserving of authentication in cloud storage auditing was considered in [19]. The problem of users’ identity privacy in shared data auditing was taken into account in [20, 21].To eliminate the complex certificate management in PKI setting, Wang et al. [22] constructed the first identity-based remote data integrity auditing scheme. Based on identity-based cryptosystem, Yu et al. [23] designed a perfect data privacy-preserving cloud storage auditing scheme, which is able to achieve zero knowledge privacy against a third party auditor. Li et al. [24] proposed a fuzzy identity-based cloud storage auditing scheme, in which a set of descriptive attributes is used as a user’s identity. Zhang et al. [25] considered the problem of user revocation in the cloud storage auditing and presented an identity-based shared data integrity auditing scheme supporting real efficient user revocation. Shen et al. [26] proposed an identity-based cloud storage auditing scheme for shared data. In this scheme, the cloud file can be shared and used by others under the condition that the sensitive information is hidden.Most end users, such as smart phone, have constrained computation resources and computation capabilities. In order to alleviate the user’s computation burden, many lightweight cloud storage auditing schemes were proposed. Li. et al. [27] and Wang et al. [28], respectively, proposed cloud storage auditing schemes for low-performance end devices based on online/offline signatures. In these two schemes, most heavy computations are executed in the offline phase. Nonetheless, the user still needs to carry out lightweight computations for generating data signatures in the online phase. In order to deal with this problem, Wang et al. [5] proposed an identity-based cloud storage auditing scheme by introducing a proxy to help users generate data signatures. In this scheme, the user does not need to consume computation resources to generate data signatures. Shen et al. [6] designed a lightweight data integrity auditing scheme for cloud storage, in which the Third Party Medium (TPM) is introduced to process data on behalf of users. Wang et al. [8] constructed a comprehensive cloud storage auditing scheme. In this scheme, the user delegates the task of data signature generation to a dedicated proxy. However, all these schemes that introduce the proxy do not consider the problem of proxy update. In addition, the problem of workload-based payment was also not taken into account. Actually, these problems are common and essential in real-world applications as discussed above.


## 1.2. Organization

The rest of this paper is organized as follows. We present the system model and design goals in Section2. In Section 3, we give the notations and the definition and review several cryptographic knowledge. The proposed cloud storage auditing scheme is introduced in Section 4. The security proof and performance evaluation of the proposed scheme are given, respectively, in Section 5 and Section 6. Section 7 concludes the paper.


## 2. System Model and Design Goals

### 2.1. System Model

As shown in Figure1, there are five types of entities in our system model, that is, the user, the cloud, the proxy, the Private Key Generator (PKG), and the TPA.(1)
User: The user is the data owner, who has massive data files to be stored to the cloud. Most end users, such as smart phone and PDAs, have limited computation resources and computation capabilities.(2)
Cloud: The cloud has enormous storage space and computation resources and offers data storage services for the user.(3)
Proxy: The proxy is authorized by the user and helps the user to process and upload data to the cloud.(4)
PKG: The PKG is responsible for generating global parameters, the partial private key, and the private keys for the proxy, the user, and the cloud, respectively, according to their identities.(5)
TPA: The TPA is in charge of executing cloud storage auditing on behalf of the user. The TPA can check whether the cloud stores the user’s data correctly by performing the challenge-response protocol with the cloud.Figure 1
System model of our cloud storage auditing.In our system model, when a user would like to store his data to the cloud, he will delegate a proxy to help him to process data. Meanwhile, the user generates the warrant-signature pair and the time private key and then sends them to the proxy. The proxy with a valid warrant can generate the signatures for data and upload these data blocks along with the signature set to the cloud on behalf of the user. When the proxy is revoked or the proxy’s warrant expires, this proxy cannot process data for the user any more. The user pays for the proxy based on the proxy’s workload. Same as the system mode in cloud storage schemes [5, 8, 12, 25, 29], we do not take any collusion into account in this system.


### 2.2. Design Goals

To support proxy update, workload-based payment, and lightweight identity-based cloud storage auditing, our designed scheme should achieve the following goals:(1)
Auditing correctness: to ensure that the auditing proof generated by the cloud can pass the TPA’s verification, if the cloud possesses the user’s intact data.(2)
Auditing soundness: to guarantee that the cloud cannot pass the validation of the TPA if it does not keep the user’s data correctly.(3)
Lightweight: to reduce the computation burden of generating data signatures and verifying data integrity for the user with constrained computation capabilities.(4)
Secure proxy update: to ensure that the revoked proxy or the expired proxy cannot process data on behalf of the user any more.(5)
Efficient proxy update: to guarantee that the data signatures generated by the proxy do not need to be recomputed even if this proxy is revoked or his warrant expires.(6)
Effective payment: to ensure that the user can pay for the proxy based on the workload of the proxy.


## 2.1. System Model

As shown in Figure1, there are five types of entities in our system model, that is, the user, the cloud, the proxy, the Private Key Generator (PKG), and the TPA.(1)
User: The user is the data owner, who has massive data files to be stored to the cloud. Most end users, such as smart phone and PDAs, have limited computation resources and computation capabilities.(2)
Cloud: The cloud has enormous storage space and computation resources and offers data storage services for the user.(3)
Proxy: The proxy is authorized by the user and helps the user to process and upload data to the cloud.(4)
PKG: The PKG is responsible for generating global parameters, the partial private key, and the private keys for the proxy, the user, and the cloud, respectively, according to their identities.(5)
TPA: The TPA is in charge of executing cloud storage auditing on behalf of the user. The TPA can check whether the cloud stores the user’s data correctly by performing the challenge-response protocol with the cloud.Figure 1
System model of our cloud storage auditing.In our system model, when a user would like to store his data to the cloud, he will delegate a proxy to help him to process data. Meanwhile, the user generates the warrant-signature pair and the time private key and then sends them to the proxy. The proxy with a valid warrant can generate the signatures for data and upload these data blocks along with the signature set to the cloud on behalf of the user. When the proxy is revoked or the proxy’s warrant expires, this proxy cannot process data for the user any more. The user pays for the proxy based on the proxy’s workload. Same as the system mode in cloud storage schemes [5, 8, 12, 25, 29], we do not take any collusion into account in this system.


## 2.2. Design Goals

To support proxy update, workload-based payment, and lightweight identity-based cloud storage auditing, our designed scheme should achieve the following goals:(1)
Auditing correctness: to ensure that the auditing proof generated by the cloud can pass the TPA’s verification, if the cloud possesses the user’s intact data.(2)
Auditing soundness: to guarantee that the cloud cannot pass the validation of the TPA if it does not keep the user’s data correctly.(3)
Lightweight: to reduce the computation burden of generating data signatures and verifying data integrity for the user with constrained computation capabilities.(4)
Secure proxy update: to ensure that the revoked proxy or the expired proxy cannot process data on behalf of the user any more.(5)
Efficient proxy update: to guarantee that the data signatures generated by the proxy do not need to be recomputed even if this proxy is revoked or his warrant expires.(6)
Effective payment: to ensure that the user can pay for the proxy based on the workload of the proxy.


## 3. Notations, Definition, and Cryptographic Knowledge

### 3.1. Notations

In Table1, we show the notations used in the description of our scheme.Table 1
Notations.
Notation Meaning G1,G2 Multiplicative cyclic groups with prime orderp  g,u Two generators of groupG1  e A bilinear pairing mape:G1×G1→G2  H A cryptographic hash function,H:{0,1}∗×G1→Zp∗  h A cryptographic hash function,h:{0,1}∗→G1  k The security parameter  x The master private key  IDu The user identity  IDp The proxy identity  IDc The cloud identity  skIDu The userIDu’s private key  skIDp The proxyIDp’s partial private key  skIDc The cloudIDc’s private key  mw The warrant  Ts,Te The warrant’s start time and end time  (RT,σT) The time private key  (RIDp,RT,σ) The proxy private key  F The file  n The number of data blocks of fileF  mi(i=1,2,…,n) Thei-th block of file F  σi The signature of data blockmi  Φ The signature set of data blocks  N The upload number  μ The linear combination of data blocks  σ An aggregated data signature


### 3.2. Definition

Definition 1.
A lightweight identity-based cloud storage auditing scheme supporting proxy update and workload-based payment is composed by the following eight algorithms:(1)
Setup: The setup algorithm is run by the PKG. It takes as input the security parameterk and outputs the master private key x and the public parameters pp.(2)
Extract: The extract algorithm is run by the PKG. It takes as input the public parameters pp, the user identity IDu, the cloud identity IDc, the proxy identity IDp, and the master private key x and generates the user IDu’s private key sku, the cloud IDc’s private key skc, and the proxy IDp’s partial private key skp. The user verifies the correctness of the private key sku. The cloud checks the correctness of the private key skc. The proxy verifies the correctness of the partial private key skp.(3)
ProxyKeyGen: The proxy private key generation algorithm is run by the user and the proxy. It takes as input the warrant’s start time Ts and end time Te, the user identity IDu, the proxy identity IDp, and the partial private key skp. The user generates the time private key skT and the warrant-signature pair (mw,(R1,σ1)). The proxy generates the proxy private key (RIDp,RT,σ) according to the time private key and the partial private key.(4)
SignGen: The signature generation algorithm is run by the proxy. It takes as input the file name name, the file F, the warrant’s start time Ts and end time Te, and the proxy private key (RIDp,RT,σ) and generates the set of signatures Φ and the file tag tag.(5)
ProofGen: The proof generation algorithm is run by the cloud. It takes as input the fileF, the corresponding signature set Φ, and the auditing challengechal and generates an auditing proofP that is used to prove the cloud stores the file correctly.(6)
ProofVerify: The proof verification algorithm is run by the TPA. It takes as input the public parameters pp, the auditing challengechal, and the auditing proofP and returns “1” if the verification passes or “0” if otherwise.(7)
ProxyUpdate: The proxy update algorithm is run by the user and the proxy. It takes as input the new warrant’s start time Ts and end time Te, the user identity IDu, the proxy identity IDp, and the partial private key skp. The user generates a new time private key and a new warrant-signature pair. The proxy generates the proxy private key according to the new time private key and the partial private key.(8)
Payment: The payment algorithm is run by the cloud, the proxy, and the user. It takes as input the upload number N and the cloud’s private key skc and generates the signature β corresponding to N. The proxy and the user check the validity of β.


### 3.3. Cryptographic Knowledge

(  1) Bilinear Maps. A bilinear map is a map e:G1×G1→G2, where G1 and G2 are two multiplicative cyclic groups of order p with the following properties:(a)
Computability: there exists an efficiently computable algorithm to calculate e(u,v) for u,v∈G1.(b)
Bilinearity: for all u,v∈G1 and x,y∈Zp∗, eux,vy=eu,vxy.(c)
Nondegeneracy: eg,g≠1, where g is the generator of G1.(  2) Computational Diffie-Hellman (CDH) Problem. Given gx and gy, where g is a generator of a multiplicative group G1 with the prime order p, and x,y∈Zp∗ are unknown, calculate gxy∈G1. The CDH assumption in G1 holds if it is computationally infeasible to solve the CDH problem in G1.(  3) Discrete Logarithm (DL) Problem. Given ga, where g is a generator of a multiplicative group G1 with the prime order p, and a∈Zp∗ is unknown, calculate a. The DL assumption in G1 holds if it is computationally infeasible to solve the DL problem in G1.


## 3.1. Notations

In Table1, we show the notations used in the description of our scheme.Table 1
Notations.
Notation Meaning G1,G2 Multiplicative cyclic groups with prime orderp  g,u Two generators of groupG1  e A bilinear pairing mape:G1×G1→G2  H A cryptographic hash function,H:{0,1}∗×G1→Zp∗  h A cryptographic hash function,h:{0,1}∗→G1  k The security parameter  x The master private key  IDu The user identity  IDp The proxy identity  IDc The cloud identity  skIDu The userIDu’s private key  skIDp The proxyIDp’s partial private key  skIDc The cloudIDc’s private key  mw The warrant  Ts,Te The warrant’s start time and end time  (RT,σT) The time private key  (RIDp,RT,σ) The proxy private key  F The file  n The number of data blocks of fileF  mi(i=1,2,…,n) Thei-th block of file F  σi The signature of data blockmi  Φ The signature set of data blocks  N The upload number  μ The linear combination of data blocks  σ An aggregated data signature


## 3.2. Definition

Definition 1.
A lightweight identity-based cloud storage auditing scheme supporting proxy update and workload-based payment is composed by the following eight algorithms:(1)
Setup: The setup algorithm is run by the PKG. It takes as input the security parameterk and outputs the master private key x and the public parameters pp.(2)
Extract: The extract algorithm is run by the PKG. It takes as input the public parameters pp, the user identity IDu, the cloud identity IDc, the proxy identity IDp, and the master private key x and generates the user IDu’s private key sku, the cloud IDc’s private key skc, and the proxy IDp’s partial private key skp. The user verifies the correctness of the private key sku. The cloud checks the correctness of the private key skc. The proxy verifies the correctness of the partial private key skp.(3)
ProxyKeyGen: The proxy private key generation algorithm is run by the user and the proxy. It takes as input the warrant’s start time Ts and end time Te, the user identity IDu, the proxy identity IDp, and the partial private key skp. The user generates the time private key skT and the warrant-signature pair (mw,(R1,σ1)). The proxy generates the proxy private key (RIDp,RT,σ) according to the time private key and the partial private key.(4)
SignGen: The signature generation algorithm is run by the proxy. It takes as input the file name name, the file F, the warrant’s start time Ts and end time Te, and the proxy private key (RIDp,RT,σ) and generates the set of signatures Φ and the file tag tag.(5)
ProofGen: The proof generation algorithm is run by the cloud. It takes as input the fileF, the corresponding signature set Φ, and the auditing challengechal and generates an auditing proofP that is used to prove the cloud stores the file correctly.(6)
ProofVerify: The proof verification algorithm is run by the TPA. It takes as input the public parameters pp, the auditing challengechal, and the auditing proofP and returns “1” if the verification passes or “0” if otherwise.(7)
ProxyUpdate: The proxy update algorithm is run by the user and the proxy. It takes as input the new warrant’s start time Ts and end time Te, the user identity IDu, the proxy identity IDp, and the partial private key skp. The user generates a new time private key and a new warrant-signature pair. The proxy generates the proxy private key according to the new time private key and the partial private key.(8)
Payment: The payment algorithm is run by the cloud, the proxy, and the user. It takes as input the upload number N and the cloud’s private key skc and generates the signature β corresponding to N. The proxy and the user check the validity of β.


## 3.3. Cryptographic Knowledge

(  1) Bilinear Maps. A bilinear map is a map e:G1×G1→G2, where G1 and G2 are two multiplicative cyclic groups of order p with the following properties:(a)
Computability: there exists an efficiently computable algorithm to calculate e(u,v) for u,v∈G1.(b)
Bilinearity: for all u,v∈G1 and x,y∈Zp∗, eux,vy=eu,vxy.(c)
Nondegeneracy: eg,g≠1, where g is the generator of G1.(  2) Computational Diffie-Hellman (CDH) Problem. Given gx and gy, where g is a generator of a multiplicative group G1 with the prime order p, and x,y∈Zp∗ are unknown, calculate gxy∈G1. The CDH assumption in G1 holds if it is computationally infeasible to solve the CDH problem in G1.(  3) Discrete Logarithm (DL) Problem. Given ga, where g is a generator of a multiplicative group G1 with the prime order p, and a∈Zp∗ is unknown, calculate a. The DL assumption in G1 holds if it is computationally infeasible to solve the DL problem in G1.


## 4. The Proposed Scheme

In our scheme, the fileF is divided into n blocks, i.e., F=(m1,m2,…,mn), where mi denotes the ith block of file F. In previous cloud storage auditing schemes [18, 32], there is a signature SSig that is used to guarantee the correctness of the file identifier name. Without loss of generality, we also utilize a similar identity-based signature SSig to ensure the correctness of the file identifier name, the warrant’s valid time period, the proxy identity, and the verification values in our scheme. We assume ssk is the secret key for the signature SSig. The proxy holds this secret key. In addition, we assume the upload number is N, which is used to record how many files are uploaded to the cloud by the proxy. The upload number is initialized to 0. The details of the proposed scheme are as follows.(  1) Setup (a)
The PKG randomly selects two multiplicative cyclic groupsG1, G2 with the prime orderp, a bilinear map e:G1×G1→G2, two generators g,u∈G1, and two cryptographic hash functions H:{0,1}∗×G1→Zp∗ and h:{0,1}∗→G1. (b)
The PKG randomly picksx∈Zp∗ as its master private key and computes Y=gx. (c)
The PKG publishes the global parameterspp=(G1,G2,p,g,e,u,Y,H,h) and keeps his master private key x.(  2) Extract.The PKG generates private keys for the user IDu and the cloud IDc, respectively, and generates the partial private key for the proxy IDp. The user IDu and the cloud IDc can verify the correctness of their private keys, respectively. The proxy IDp can check correctness of the partial private key.(a)
After receiving the user’s identityIDu, the PKG randomly chooses rIDu∈Zp∗, and calculates RIDu=grIDu and σIDu=rIDu+xH(IDu,RIDu). Set the user’s private key skIDu=(RIDu,σIDu). The PKG sends skIDu to the user IDu.Upon receiving the private key from the PKG, the userIDu validates the correctness of skIDu by checking whether the following equation holds or not:(1)gσIDu=RIDuYHIDu,RIDu.If (1) holds, the user IDu accepts the private key skIDu; otherwise, the user rejects it.(b)
Similarly, receiving the cloud’s identityIDc, the PKG calculates the cloud’s private key skIDc=(RIDc,σIDc), where RIDc=grIDc and σIDc=rIDc+xH(IDc,RIDc) and then sends it to the cloud. The cloud can verify the correctness of skIDc by checking the equation gσIDc=RIDcYH(IDc,RIDc).(c)
Receiving the proxy’s identityIDp, the PKG calculates the proxy’s private key, and the proxy can get its partial private key skIDp=(RIDp,σIDp), where RIDp=grIDp and σIDp=rIDp+xH(IDp,RIDp). The proxy can check the correctness of skIDp by checking the equation gσIDp=RIDpYH(IDp,RIDp).( 3) ProxyKeyGen. This process is illustrated in Figure 2. The user IDu firstly sets the warrant’s start time and end time, then generates the time private key and the warrant-signature pair, and finally sends all the above messages to the proxy IDp. The proxy IDp can verify the correctness of the above messages, respectively, and then computes the proxy private key based on the partial private key and the time private key.(a)
The userIDu executes the following steps.
(i)
The userIDu sets the warrant’s start time Ts and end time Te. The user IDu selects rT∈RZp∗ and computes RT=grT and σT=rT+σIDu·H(Ts∥Te,RT). Let skT=(RT,σT) be the time private key.(ii)
The userIDu generates a warrant mw, which is used to authorize a designated proxy. The warrant mw consists of the user’s identity IDu, the proxy’s identity IDp, and the warrant’s valid time period (start time Ts and end time Te). Let the warrant be denoted as mw=IDu∥IDp∥Ts∥Te. The user IDu picks r1∈RZp∗ and calculates the warrant mw’s signature as follows: R1=gr1 and σ1=r1+σIDu·H(mw,R1).(iii)
The userIDu sends the warrant’s valid time period (Ts,Te), the time private key (RT,σT), warrant-signature pair (mw,(R1,σ1)), and the verification value RIDu to the proxy IDp.(b)
Upon receiving the messages from the userIDu, the proxy IDp does the following steps:
(i)
The proxyIDp verifies the validity of warrant-signature pair (mw,(R1,σ1)) by checking whether the following equation holds:(2)gσ1=R1RIDuHmw,R1YHIDu,RIDu·Hmw,R1.If (2) does not hold, the proxy IDp rejects the warrant mw from the user IDu; otherwise, he accepts the warrant and then does step (ii).(ii)
The proxyIDp checks the correctness of time private key (RT,σT) by validating the following equation:(3)gσT=RTRIDuHTs∥Te,RTYHIDu,RIDu·HTs∥Te,RT.If (3) holds, the proxy IDp computes σ=(σIDp+σT)(modp) and sets the proxy private key as (RIDp,RT,σ).Figure 2
The process of proxy private key generation.(  4) SignGen.This process is illustrated in Figure 3. The proxy IDp calculates the signatures for data blocks with the proxy private key and then generates the file tag which is used to guarantee the correctness of the file name, the warrant’s valid time period, the proxy identity, and some verification values. Finally, the proxy IDp sends the file F, its corresponding signature set, the file tag, the warrant’s valid time period, and the warrant-signature pair to the cloud. The cloud firstly checks whether the proxy is in the public revocation list, then verifies the validity of the warrant-signature pair and the file tag, and finally generates a signature for the upload number.(a)
The proxyIDp performs the following operations.
(i)
The proxyIDp computes the signature βi of the data block mi with the proxy private key σ as follows:(4)βi=hnameiIDpumiσ,wherename∈Zp∗ is the identifier of the fileF. Denote the set of signatures as Φ={βi}i∈[1,n].(ii)
The proxyIDp calculates the file tag tag=name∥Ts∥Te∥RIDp∥RT∥IDp∥SSigssk(name∥Ts∥Te∥RIDp∥RT∥IDp).(iii)
The proxyIDp sends the file F, its corresponding signatures set Φ, the file tag tag, the warrant’s valid time period (Ts,Te), and the warrant-signature pair (mw,(R1,σ1)) to the cloud.(iv)
The proxyIDp sets the upload number N=N+1, which is used to record how many files are uploaded to the cloud.(b)
After receiving the above messages, the cloud executes the following operations.
(i)
The cloud verifies whether the proxyIDp is in the public revocation list. If the proxy IDp is not in the revocation list, the cloud does the following step (ii); otherwise, the cloud regards the proxy IDp as a revoked proxy and refuses his request.(ii)
The cloud checks the validity of the warrant-signature pairmw,R1,σ1 based on (2). If the current time period is not in the valid time period (Ts,Te), then the warrant mw can be regarded as an invalid warrant and the cloud refuses the request of the proxy; otherwise, the cloud continues to perform the following step (iii).(iii)
The cloud checks the validity of the file tag by verifying whether the signatureSSigssk(name∥Ts∥Te∥RIDp∥RT∥IDp) is a valid signature or not based on the proxy identity IDp. If it is not, the cloud believes this signature is invalid; otherwise, the cloud does the last step.(iv)
The cloud stores the data uploaded by the proxyIDp and increases the upload number he stores to keep pace with the number N stored by the proxy. Then the cloud generates a signature β=SSigskc′(N) with its private key skc for the upload number N.Figure 3
The process of signature generation.Remark 2.
The proxy usually uploads data in bulk to the cloud. Thus, the cloud may only need to generate a signature for the newest upload number rather than every upload number.(  5) ProofGen.The TPA firstly verifies the validity of file tag and then generates and sends an auditing challenge to the cloud. The cloud responds to an auditing proof to the TPA.(a)
The TPA firstly verifies the correctness of the file tagtag by checking whether SSigssk(name∥Ts∥Te∥RIDp∥RT∥IDp) is a valid signature. If it is not, the TPA does not execute the auditing task; otherwise, he parses name∥Ts∥Te∥RIDp∥RT∥IDp to obtain the file name name, the warrant’s valid time period (start time Ts and end time Te), the verification values RIDp,RT, and the proxy identity IDp. Then the TPA randomly picks ac-element subsetI from the set [1,n] and selects a random vi∈Zp∗ for each i∈I. The TPA sends the auditing challenge chal={i,vi}i∈I to the cloud.(b)
After receiving the auditing challenge, the cloud calculatesμ=∑i∈I‍mivi and Ω=∏i∈I‍βivi. Next, the cloud returns P={μ,Ω} as the auditing proof to the TPA.(  6) ProofVerify.The TPA verifies whether the following equation holds or not:(5)eΩ,g=e∏i∈IhnameIDpivi·uμ,RIDp·RT·RIDuHTs∥Te,RT·YHIDp,RIDp+HIDu,RIDuHTs,Te,RTIf (5) holds, output “1”; otherwise, output “0.”(  7) ProxyUpdate (a)
When the proxyIDp is revoked by the user IDu before the expiration of the valid time period, the cloud will put this revoked proxy’s identity IDp in a public revocation list. Then, the user IDu authorizes a new proxy IDp′ and sets the warrant’s valid time period for this proxy IDp′and then computes the time private key based on the warrant’s valid time period and generates a warrant-signature pair for the new proxy IDp′. Finally, the user IDu sends all the above messages to the new proxy IDp′. The proxy IDp′ can validate the correctness of the messages he received and next compute the proxy private key based on the partial private key generated by the PKG and the time private key.
(i)
The userIDu sets the warrant’s start time Ts and end time Te. The user IDu selects rT∈RZp and computes RT=grT and σT=rT+σIDu·H(Ts,Te,RT). Let (RT,σT) be the time private key. (ii)
The userIDu generates a warrant mw, which is used to authorize a new proxy IDp′. The warrant mw consists of the user’s identity IDu, the proxy’s identity IDp′, and the warrant’s start time Ts and end time Te. Let the warrant be denoted as mw=IDu∥IDp′∥Ts∥Te. The user IDu picks r1∈RZp∗ and computes the warrant mw’s signature as follows: R1=gr1 and σ1=r1+σIDu·H(mw,R1). (iii)
The userIDu sends the warrant’s valid time period (Ts,Te), the time private key (RT,σT), and the warrant-signature pair (mw,(R1,σ1)) to the proxy IDp′. (iv)
The proxyIDp′ verifies the validity of warrant-signature pair (mw,(R1,σ1)) by (2). Then, the proxy IDp′ checks the correctness of time private key (RT,σT) by (3) and calculates the proxy private key (RIDp′,RT,σ) based on the time private key (RT,σT) and the partial private key (RIDp′,σIDp′), where σ=(σIDp′+σT)(modp). (b)
When the proxyIDp’s warrant expires, the user IDu can select to continue employing this proxy. The user IDu generates a new warrant for the proxy IDp by updating the warrant’s start time and end time. The operations are similar to the above case (a) in ProxyUpdate algorithm.When the proxy is revoked, the cloud will put this revoked proxy’s identity in a public revocation list. It makes the revoked proxy unable upload new file to the cloud any more. In addition, when the proxy’s warrant expires, he does not have the new valid warrant and the expired warrant he keeps cannot pass the verification of (2) in ProxyKeyGen algorithm. Therefore, neither the revoked proxy nor the expired proxy can upload a new file to the cloud any more.Remark 3.
If a proxy is in the public revocation list, he can be deleted from this revocation list when his warrant expires. Thus, the size of public revocation list will not increase unlimitedly.(  8) Payment. When the proxy IDp’s warrant expires or the proxy IDp is revoked, the user IDu will pay for the proxy IDp based on his workload.(a)
The proxyIDp requests the cloud to send him the signature of the newest upload number N.(b)
Upon receiving the request, the cloud computes the signature of the newest upload number asβ=SSigskc′(N∥IDp) and returns β to the proxy IDp.(c)
The proxyIDp uses the cloud identity to check the validity of signature β by inputting his identity IDp and the upload number N he records and then shows the signature β from the cloud and the newest upload number N to the user IDu.(d)
The userIDu verifies whether the signature β is valid or not via the cloud identity IDc. When this signature is valid, the user IDu pays for the proxy IDp based on the newest upload number N.


## 5. Security Analysis

Theorem 4 (correctness).
Our proposed scheme satisfies the following properties:(1)
Private key correctness: If the private keys and the partial private key generated by the PKG are correct, then these private keys and the partial private key are able to pass the checking of the user, the cloud, and the proxy, respectively.(2)
Warrant-signature pair correctness: If the warrant-signature pair generated by the user is valid, then this warrant-signature pair is able to pass the proxy’s checking.(3)
Time private key correctness: If the time private key generated by the user is correct, then this time private key is able to pass the proxy’s verification.(4)
Auditing correctness: If the auditing proof generated by the cloud is valid, this proof is able to pass the TPA’s verification.Proof.
(1)
Given a correct private keyskIDu=(RIDu,σIDu) generated by the PKG, the verification equation (1) inExtract algorithm can be presented as follows: (6)gσIDu=grIDu+xHIDu,RIDu=grIDu·gxHIDu,RIDu=RIDuYHIDu,RIDu Similarly, if the private keyskIDc=(RIDc,σIDc) and the partial private key skIDp=(RIDp,σIDp) generated by the PKG are correct, we can ensure that the private key skIDc and the partial private key skIDp are able to pass the verification of the cloud and the proxy, respectively. (2)
Given a valid warrant-signature pair(mw,(R1,σ1)) generated by the user IDu, the verification equation (2) inProxyKeyGen algorithm holds. (7)gσ1=gr1+σIDu·Hmw,R1=gr1·gσIDu·Hmw,R1=R1·grIDu+xHIDu,RIDu·Hmw,R1=R1·grIDu·Hmw,R1·gxHIDu,RIDu·Hmw,R1=R1RIDuHmw,R1YHIDu,RIDu·Hmw,R1 (3)
Given a time private keyskIDc=(RIDc,σIDc) generated by the user IDu, the verification equation (3) inProxyKeyGen algorithm can be presented as follows: (8)gσT=grT+σIDu·HTs∥Te,RT=grT·gσIDu·HTs∥Te,RT=RT·grIDu+xHIDu,RIDu·HTs∥Te,RT=RT·grIDu·HTs∥Te,RT·gxHIDu,RIDu·HTs∥Te,RT=RTRIDuHTs∥Te,RTYHIDu,RIDu·HTs∥Te,RT (4)
Given a valid proofP={μ,Ω} generated by the cloud, the verification equation (5) inProofVerify algorithm can be proved as follows: (9)eΩ,g=e∏i∈Iβivi,g=e∏i∈IhnameIDpi·umiσ·vi,g=e∏i∈IhnameIDpi·umivi,gσ=e∏i∈IhnameIDpivi·∏i∈Iumi·vi,gσ=e∏i∈IhnameIDpivi·u∑i∈Ivi·mi,gσ=e∏i∈IhnameIDpivi·uμ,gσIDp+σT=e∏i∈IhnameIDpivi·uμ,grIDp+xHIDp,RIDp+rT+σIDuHTs∥Te,RT=e∏i∈IhnameIDpivi·uμ,RIDp·YHIDp,RIDp·RT·gσIDu·HTs∥Te,RT=e∏i∈IhnameIDpivi·uμ,RIDp·YHIDp,RIDp·RT·grIDu+xHIDu,RIDu·HTs∥Te,RT=e∏i∈IhnameIDpivi·uμ,RIDp·YHIDp,RIDp·RT·RIDuHTs∥Te,RT·YHIDu,RIDuHTs∥Te,RT=e∏i∈IhnameIDpivi·uμ,RIDp·RT·RIDuHTs∥Te,RT·YHIDp,RIDp+HIDu,RIDuHTs∥Te,RTTheorem 5 (auditing soundness).
In our proposed scheme, the cloud cannot pass the validation of the TPA if it does not keep the user’s data correctly.Proof.
We construct a knowledge extractor and utilize the method of knowledge proof to accomplish the following proof. If the cloud does not keep the user’s data correctly but can pass the validation of the TPA, then we can repeatedly interact between the proposed scheme and the knowledge extractor to extract the intact challenged data blocks. We will prove this theorem by a sequence of games.
Game 1. The adversary sends a query to the challenger for obtaining the signatures of a series of data blocks. The challenger generates the corresponding signatures for these data blocks and sends them to the adversary. Then the challenger submits an auditing challenge chal={i,vi}i∈I to the adversary. The adversary generates the auditing proof P={μ,Ω} and sends it to the challenger.
Game 2. Game 2 is identical to Game 1, with one difference. That is the challenger keeps a list of responses to the queries from the adversary. The challenger observes each instance of the challenge-respond process with the adversary. If the challenger finds the aggregated signature Ω is not equal to ∏i∈I‍βivi, he declares failure and aborts.
Analysis. Assume that the auditing proof {μ,Ω} is generated by the honest prover based on the correct file F. From the correctness of our scheme, we get(10)eΩ,g=e∏i∈IhnameIDpivi·uμ,RIDp·RT·RIDuHTs∥Te,RT·YHIDp,RIDp+HIDu,RIDuHTs∥Te,RT
Assume that the forged auditing proof{μ′,Ω′} is generated by the adversary based on the corrupted file F′, where F′≠F. Because the forgery is successful, we get(11)eΩ′,g=e∏i∈IhnameIDpivi·uμ′,RIDp·RT·RIDuHTs∥Te,RT·YHIDp,RIDp+HIDu,RIDuHTs∥Te,RT
Obviously,μ′≠μ; otherwise Ω′=Ω, which contradicts our above assumption. We define Δμ=μ-μ′ and show a simulator that could break the challenge CDH instance with this adversary as follows.
Given(g,gε,φ)∈G1, the simulator outputs φε. Set u=gaφb, where a,b∈Zp∗ are two random elements chosen by the simulator. Meanwhile, the verification value is set as Y=gε.
The simulator selects a random elementri∈Zp∗ for each i(1≤i≤n) in the challenge and programs the random oracle at i as(12)HnameIDpi=grigami·φbmi
The simulator can computeβi, since we get (13)HnameIDpi·umi=grigami·φbmi·umi=grigami·φbmi·gaφbmi=grigami·φbmi·gami·φbmi=gri
The simulator calculatesβi=(h(nameiIDp)umi)σ=(gri)σ.
Dividing (10) by (11), we have (14)eΩΩ′,g=euΔμ,RIDp·YHIDp,RIDp+HIDu,RIDuHTs∥Te,RT·RT·RIDuHTs∥Te,RT=egaφbΔμ,grIDp+rT+rIDuHTs∥Te,RT·YHIDp,RIDp+HIDu,RIDuHTs∥Te,RT=egaΔμ,grIDp+rT+rIDuHTs∥Te,RT·YHIDp,RIDp+HIDu,RIDuHTs∥Te,RT·eφbΔμ,grIDp+rT+rIDuHTs∥Te,RT·YHIDp,RIDp+HIDu,RIDuHTs∥Te,RT=egaΔμ·rIDp+rT+rIDuHTs∥Te,RT·YaΔμ·HIDp,RIDp+HIDu,RIDuHTs∥Te,RT,g·eφbΔμ·rIDp+rT+rIDuHTs∥Te,RT,g·eφbΔμ,YHIDp,RIDp+HIDu,RIDuHTs∥Te,RT. So, we obtain (15)eΩΩ′·g-aΔμ·rIDp+rT+rIDuHTs∥Te,RT·Y-aΔμ·HIDp,RIDp+HIDu,RIDuHTs∥Te,RT·φ-bΔμ·rIDp+rT+rIDuHTs∥Te,RT,g=eφbΔμ,YHIDp,RIDp+HIDu,RIDuHTs∥Te,RT=eφ,YbΔμHIDp,RIDp+HIDu,RIDuHTs∥Te,RT=eφ,gεbΔμHIDp,RIDp+HIDu,RIDuHTs∥Te,RT=eφε,gbΔμHIDp,RIDp+HIDu,RIDuHTs∥Te,RT.
Then, we can learn that(16)φε=eΩΩ′·g-aΔμ·rIDp+rT+rIDuHTs∥Te,RT·Y-aΔμ·HIDp,RIDp+HIDu,RIDuHTs∥Te,RT·φ-bΔμ·rIDp+rT+rIDuHTs∥Te,RT1/bΔμHIDp,RIDp+HIDu,RIDuHTs∥Te,RT. Note that the probability we can find a solution to CDH problem is the same as the probability bΔμ(H(IDp,RIDp) + H(IDu,RIDu)H(Ts∥Te,RT)) ≠ 0modp. The probability of bΔμ(H(IDp,RIDp) + H(IDu,RIDu)H(Ts∥Te,RT)) ≠ 0modp is 1-1/p. Then, we can find a solution to CDH problem with a probability 1-1/p, which contradicts the assumption that the CDH problem in G1 is hard.
Therefore, if the difference between the adversary’s probabilities of success in Game 1 and Game 2 is nonnegligible, we can construct a simulator that utilizes the adversary to solve the CDH problem.
Game 3. Game 3 is identical to Game 2, with one difference. The challenger still maintains and observes each instance of the proposed scheme. For one of these instances, if the challenger finds a linear combination μ′ of data blocks is not equal to the expected μ, the challenger declares failure and aborts.
Analysis. Assume that the honest prover generates a corret auditing proof {μ,Ω} based on the correct file F. From the correctness of our scheme, we get(17)eΩ,g=e∏i∈IhnameIDpivi·uμ,RIDp·RT·RIDuHTs∥Te,RT·YHIDp,RIDp+HIDu,RIDuHTs∥Te,RT
Assume that the adversary generates a forged auditing proof{μ′,Ω′} based on the corrupted file F′, where F′≠F. Because the forgery is successful, we get(18)eΩ′,g=e∏i∈IhnameIDpivi·uμ′,RIDp·RT·RIDuHTs∥Te,RT·YHIDp,RIDp+HIDu,RIDuHTs∥Te,RT
According to Game 2, we learn thatΩ′=Ω. Define Δμ=μ-μ′, and we show a simulator that could solve the challenge DL instance with this adversary as follows.
Given(g,φ)∈G1, the simulator would like to calculate a value x which satisfies φ=gx. The simulator randomly selects two elements a,b∈Zp∗ and sets u=gaφb.
Based on the above two verification equations, we get(19)e∏i∈IhnameIDpivi·uμ,RIDp·RT·RIDuHTs∥Te,RT·YHIDp,RIDp+HIDu,RIDuHTs∥Te,RT=eΩ,g=eΩ′,g=e∏i∈IhnameIDpivi·uμ′,RIDp·RT·RIDuHTs∥Te,RT·YHIDp,RIDp+HIDu,RIDuHTs∥Te,RT
Therefore, we obtain(20)uμ=uμ′,
and therefore that(21)1=uΔμ=gaφbΔμ=gaΔμ·φbΔμ.
Sinceφ=gx, we can find the solution to the DL problem by calculating(22)φ=g-aΔμ/bΔμ, and then x=-aΔμ/bΔμ. As defined above, Δμ≠0. However, b is zero with the probability 1/p, which is negligible. Then, we can solve the DL problem with a probability of 1-1/p, which contradicts the assumption that the DL problem in G1 is hard.
Therefore, if the difference between the adversary’s probabilities of success in Game 2 and Game 3 is nonnegligible, we can construct a simulator that utilizes the adversary to solve the DL problem.
From the above analysis, we can know that the malicious cloud cannot pass the validation of the TPA if it does not keep the user’s data correctly.Theorem 6 (the security of proxy update).
In our proposed scheme, the revoked proxy or the expired proxy cannot process data on behalf of the user any more.Proof.
When the revoked proxy or the expired proxy uploads the file and its corresponding signatures to the cloud, the cloud firstly checks whether this proxy is in the public revocation list and then verifies the validity of the warrant-signature pair(mw,(R1,σ1)) and the file tag tag.
Firstly, if this proxy is in the public revocation list, the cloud rejects this file and signatures from this proxy. Secondly, the cloud checks the validity of the warrant-signature pair(mw,(R1,σ1)) by the verification equation (2). If the current time period is not in the valid time period (Ts,Te), then the warrant-signature pair cannot pass the verification. The cloud regards this proxy as a revoked proxy or an expired proxy and refuses this proxy’s request. Finally, the cloud checks the validity of the file tag by verifying whether SSigssk(name∥Ts∥Te∥RIDp∥RT∥IDp) is a valid signature or not. If it is not, the cloud considers that this file tag is generated by a revoked proxy or an expired proxy and then rejects the request of this proxy.
Therefore, only the proxy, who is not in the public revocation list and possess a valid warrant, is able to process data on behalf of the user.Theorem 7 (the soundness of payment).
In our proposed scheme, the user will pay for the proxy based on the proxy’s real workload assuming the cloud does not collude with the proxy.Proof.
Firstly, when the cloud receives the data uploaded by the proxy, it will set the upload numberN and generate the signature β with its private key for this upload number N. Therefore, the signature β that the proxy sends to the user is generated by the cloud according to the real upload number N. The proxy cannot forge this signature.
Secondly, the proxy can verify whether the signatureβ from the cloud is valid according to his real upload number N. Thus, the signature β that the proxy sends to the user is recognized by the proxy.
In conclusion, the user believes the signatureβ sent by the proxy is valid. The payment that the user pays for the proxy is based on the proxy’s real workload in the absence of collusion.


## 6. Performance Evaluation

In this section, we first present the functionality comparison of our scheme with different cloud storage auditing schemes and then compare the computation overhead and the communication overhead of our scheme with that of Wang et al. scheme [5]. At last, we show the experimental results of our scheme.


### 6.1. Functionality Comparison

Table2 shows a functionality comparison of our scheme with different cloud storage auditing schemes [5, 6, 18, 25, 30, 31] in terms of public verifiability, lightweight computation, proxy update, certificate management simplification, and workload-based payment. Our scheme is the only scheme that meets all of the aforementioned properties.Table 2
Functionality comparison of different cloud storage auditing schemes.
Schemes Public verifiability Lightweight computation Proxy update Certificate management simplification Workload-based payment Wang et al. [5] Yes Yes No Yes No Shen et al. [6] Yes Yes No No No Yu et al. [18] Yes No No No No Zhang et al. [25] Yes No No Yes No Shacham et al. [30] Yes No No No No Wang et al. [31] No No No No No Ours Yes Yes Yes Yes Yes


### 6.2. Performance Analysis and Comparison

(  1) Computation Overhead. Since the scheme of [5] is the lightweight cloud storage auditing scheme which achieves public verifiability and certificates management simplification, we compare our scheme with it with regard to the computation overhead of different entities in Table 3. In our scheme, the main cost of the PKG is generating global parameters, the partial private key and private keys for the proxy, the user, and the cloud, respectively. Therefore, the computation overhead of the PKG is 4EG1+3(AG1+MZp∗+HZp∗), where EG1 and AG1, respectively, denote one exponentiation operation and one addition operation in G1, and MZp∗ and HZp∗, respectively, denote one multiplication operation and one hashing operation in Zp∗. The dominated computation overhead of the proxy for computing proxy private key and data signatures is AZp∗+n(MG1+2EG1+HG1), where AZp∗ denotes one addition operation in Zp∗, MG1 and HG1, respectively, denote one multiplication operation and hash operation in G1, andn is the total number of data blocks. When generating a warrant-signature pair and the time private key, the cost of the user is 2(AZp∗+MZp∗+HZp∗), which can be done offline. The computation overhead of the cloud for generating an auditing proof is (c-1)MulG1+cExpG1+cMulZp∗+(c-1)AddZp∗, wherec is the number of challenged data blocks. The computation overhead of the TPA mainly comes from verifying the correctness of the auditing proof, which needs 2P+cHG1+(c+4)EG1+(c+4)MG1+MZp∗+4HZp∗. P denotes one pairing operation.Table 3
The computation overhead of our scheme and Wang et al. scheme [5] for different entities.
Entity Computation overhead (Our scheme) Computation overhead (Wang et al.[5]) PKG 4EG1+3(AG1+MZp∗+HZp∗) 3EG1+2(AG1+MZp∗+HZp∗) Proxy AZp∗+n(MG1+2EG1+HG1) A Z p ∗ + M Z p ∗ + H Z p ∗ + n ( M G 1 + 2 E G 1 + H G 1 ) User 2(AZp∗+MZp∗+HZp∗) AZp∗+MZp∗+HZp∗ Cloud (c-1)MulG1+cExpG1+cMulZp∗+c-1AddZp∗ (c-1)MulG1+cExpG1+cMulZp∗+(c-1)AddZp∗ TPA 2P+cHG1+(c+4)EG1+(c+4)MG1+MZp∗+4HZp∗ 2 P + ( c + 2 ) H G 1 + ( c + 3 ) E G 1 + ( c + 3 ) M G 1 + 3 H Z p ∗ + 2 A Z p ∗When the scheme is built from the bilinear parings, the computation overhead of the scheme mainly comes from the exponentiation operation, the pairing operation, and the multiplication operation inG1. The other operations, such as the operation in Zp∗ and hashing operation, cost less computation overhead. Thus, comparing with the scheme of [5], our scheme and the scheme of [5] cost almost the same computation overhead on the proxy, the user, and the cloud sides. In order to generate the cloud private key and perform the auditing task, our scheme needs to cost more computation overhead than the scheme of [5] on the PKG and the cloud sides. What is more, our scheme supports proxy update and workload-based payment, while the scheme of [5] cannot support that.(  2) Communication Overhead. As introduced in Section 4, the communication overhead of the proposed scheme mainly comes from the TPA and the cloud. We can see from Table 4, for an auditing challenge chal={i,vi}i∈I, the communication overhead of the TPA in our scheme is c·(|n|+|p|) bits, where n is the size of an element of set [1,n], and |p| is the size of an element in Zp∗. In the scheme of [5], the communication overhead of the TPA is |c|+2|p| bits for an auditing challenge chal={c,k1,k2}, where k1,k2∈Zp∗ are random values. For generating an auditing proof P={λ,σ}, the communication overhead of the cloud in our scheme and the scheme of [5] both are |p|+|q| bits, where |q| is the size of an element in G1.Table 4
The communication overhead of our scheme and Wang et al. scheme [5].
Entity Phase Communication overhead (Our scheme) Communication overhead (Wang et al. [5]) TPA Auditing challenge c ⋅ ( | n | + | p | ) | c | + 2 | p | Cloud Auditing proof |p|+|q| |p|+|q|


### 6.3. Experimental Results

In this subsection, we conduct experiments on the proposed scheme by utilizing the GNU Multiple Precision Arithmetic (GMP) [33] and the Pairing-Based Cryptography (PBC) Library [34]. These experiments are implemented on a Linux machine with an Intel Pentium 2.30GHz processor and 8GB memory and coded based on C programming language. In experiments, we set the size of an element in Zp∗ to be p =160 bits, the base field size to be 512 bits, and the size of data file to be 20MB composed by 1,000,000 blocks.(  1) Performance of Signature Generation. In our scheme, the proxy helps the user to generate data signatures. To evaluate the performance of signature generation, we implement the experiment by increasing the number of data blocks n from 100 to 1000. From Figure 4, it is easily observed that the time of generation signatures linearly increases with the number of data blocks. Thus, we can conclude that our scheme greatly alleviates the user’s computation burden for generating data signatures.Figure 4
The computation overhead for generating data signatures.(  2) Performance of Auditing. The performance of auditing on the TPA side and that on the cloud side are, respectively, shown in Figure 5 and Figure 6. In these experiments, we select to challenge different data blocks from 100 to 1000 increased by an interval of 100. As shown in Figure 5, the TPA’s computation overhead for generating challenge and verifying proof both grow linearly as the number of challenged data blocks. The computation overhead for verifying proof ranges from 1.512s to 11.931s, while the computation overhead for generating challenge grows slowly, just ranging from 0.043s to 0.422s. In Figure 6, it can be seen that the cloud’s computation overhead for generating proof ranges from 0.371s to 3.958s. From the above analysis, we can conclude that the more data blocks are challenged, the more computation overhead need to be spent on the TPA and the cloud sides.Figure 5
The computation overhead of the TPA in the phase of auditing.Figure 6
The computation overhead of the cloud in the phase of auditing.


## 6.1. Functionality Comparison

Table2 shows a functionality comparison of our scheme with different cloud storage auditing schemes [5, 6, 18, 25, 30, 31] in terms of public verifiability, lightweight computation, proxy update, certificate management simplification, and workload-based payment. Our scheme is the only scheme that meets all of the aforementioned properties.Table 2
Functionality comparison of different cloud storage auditing schemes.
Schemes Public verifiability Lightweight computation Proxy update Certificate management simplification Workload-based payment Wang et al. [5] Yes Yes No Yes No Shen et al. [6] Yes Yes No No No Yu et al. [18] Yes No No No No Zhang et al. [25] Yes No No Yes No Shacham et al. [30] Yes No No No No Wang et al. [31] No No No No No Ours Yes Yes Yes Yes Yes


## 6.2. Performance Analysis and Comparison

(  1) Computation Overhead. Since the scheme of [5] is the lightweight cloud storage auditing scheme which achieves public verifiability and certificates management simplification, we compare our scheme with it with regard to the computation overhead of different entities in Table 3. In our scheme, the main cost of the PKG is generating global parameters, the partial private key and private keys for the proxy, the user, and the cloud, respectively. Therefore, the computation overhead of the PKG is 4EG1+3(AG1+MZp∗+HZp∗), where EG1 and AG1, respectively, denote one exponentiation operation and one addition operation in G1, and MZp∗ and HZp∗, respectively, denote one multiplication operation and one hashing operation in Zp∗. The dominated computation overhead of the proxy for computing proxy private key and data signatures is AZp∗+n(MG1+2EG1+HG1), where AZp∗ denotes one addition operation in Zp∗, MG1 and HG1, respectively, denote one multiplication operation and hash operation in G1, andn is the total number of data blocks. When generating a warrant-signature pair and the time private key, the cost of the user is 2(AZp∗+MZp∗+HZp∗), which can be done offline. The computation overhead of the cloud for generating an auditing proof is (c-1)MulG1+cExpG1+cMulZp∗+(c-1)AddZp∗, wherec is the number of challenged data blocks. The computation overhead of the TPA mainly comes from verifying the correctness of the auditing proof, which needs 2P+cHG1+(c+4)EG1+(c+4)MG1+MZp∗+4HZp∗. P denotes one pairing operation.Table 3
The computation overhead of our scheme and Wang et al. scheme [5] for different entities.
Entity Computation overhead (Our scheme) Computation overhead (Wang et al.[5]) PKG 4EG1+3(AG1+MZp∗+HZp∗) 3EG1+2(AG1+MZp∗+HZp∗) Proxy AZp∗+n(MG1+2EG1+HG1) A Z p ∗ + M Z p ∗ + H Z p ∗ + n ( M G 1 + 2 E G 1 + H G 1 ) User 2(AZp∗+MZp∗+HZp∗) AZp∗+MZp∗+HZp∗ Cloud (c-1)MulG1+cExpG1+cMulZp∗+c-1AddZp∗ (c-1)MulG1+cExpG1+cMulZp∗+(c-1)AddZp∗ TPA 2P+cHG1+(c+4)EG1+(c+4)MG1+MZp∗+4HZp∗ 2 P + ( c + 2 ) H G 1 + ( c + 3 ) E G 1 + ( c + 3 ) M G 1 + 3 H Z p ∗ + 2 A Z p ∗When the scheme is built from the bilinear parings, the computation overhead of the scheme mainly comes from the exponentiation operation, the pairing operation, and the multiplication operation inG1. The other operations, such as the operation in Zp∗ and hashing operation, cost less computation overhead. Thus, comparing with the scheme of [5], our scheme and the scheme of [5] cost almost the same computation overhead on the proxy, the user, and the cloud sides. In order to generate the cloud private key and perform the auditing task, our scheme needs to cost more computation overhead than the scheme of [5] on the PKG and the cloud sides. What is more, our scheme supports proxy update and workload-based payment, while the scheme of [5] cannot support that.(  2) Communication Overhead. As introduced in Section 4, the communication overhead of the proposed scheme mainly comes from the TPA and the cloud. We can see from Table 4, for an auditing challenge chal={i,vi}i∈I, the communication overhead of the TPA in our scheme is c·(|n|+|p|) bits, where n is the size of an element of set [1,n], and |p| is the size of an element in Zp∗. In the scheme of [5], the communication overhead of the TPA is |c|+2|p| bits for an auditing challenge chal={c,k1,k2}, where k1,k2∈Zp∗ are random values. For generating an auditing proof P={λ,σ}, the communication overhead of the cloud in our scheme and the scheme of [5] both are |p|+|q| bits, where |q| is the size of an element in G1.Table 4
The communication overhead of our scheme and Wang et al. scheme [5].
Entity Phase Communication overhead (Our scheme) Communication overhead (Wang et al. [5]) TPA Auditing challenge c ⋅ ( | n | + | p | ) | c | + 2 | p | Cloud Auditing proof |p|+|q| |p|+|q|


## 6.3. Experimental Results

In this subsection, we conduct experiments on the proposed scheme by utilizing the GNU Multiple Precision Arithmetic (GMP) [33] and the Pairing-Based Cryptography (PBC) Library [34]. These experiments are implemented on a Linux machine with an Intel Pentium 2.30GHz processor and 8GB memory and coded based on C programming language. In experiments, we set the size of an element in Zp∗ to be p =160 bits, the base field size to be 512 bits, and the size of data file to be 20MB composed by 1,000,000 blocks.(  1) Performance of Signature Generation. In our scheme, the proxy helps the user to generate data signatures. To evaluate the performance of signature generation, we implement the experiment by increasing the number of data blocks n from 100 to 1000. From Figure 4, it is easily observed that the time of generation signatures linearly increases with the number of data blocks. Thus, we can conclude that our scheme greatly alleviates the user’s computation burden for generating data signatures.Figure 4
The computation overhead for generating data signatures.(  2) Performance of Auditing. The performance of auditing on the TPA side and that on the cloud side are, respectively, shown in Figure 5 and Figure 6. In these experiments, we select to challenge different data blocks from 100 to 1000 increased by an interval of 100. As shown in Figure 5, the TPA’s computation overhead for generating challenge and verifying proof both grow linearly as the number of challenged data blocks. The computation overhead for verifying proof ranges from 1.512s to 11.931s, while the computation overhead for generating challenge grows slowly, just ranging from 0.043s to 0.422s. In Figure 6, it can be seen that the cloud’s computation overhead for generating proof ranges from 0.371s to 3.958s. From the above analysis, we can conclude that the more data blocks are challenged, the more computation overhead need to be spent on the TPA and the cloud sides.Figure 5
The computation overhead of the TPA in the phase of auditing.Figure 6
The computation overhead of the cloud in the phase of auditing.


## 7. Conclusion

In this paper, we propose an identity-based cloud storage auditing scheme, which achieves lightweight computation on the user side by introducing a proxy and supports proxy update and workload-based payment for the proxy. In our scheme, the task of generating data signatures is executed by the proxy with a valid warrant. The revoked proxy and the proxy with expired warrant cannot help the user process data any more. We pay for the proxy based on the workload in cloud storage auditing. The security analysis and the experiment results show that our scheme provides strong security with desirable efficient efficiency.



---

*Source: 8275074-2019-03-03.xml*