# A Certificate-Based Provable Data Possession Scheme in the Standard Model

Authors: Caixue Zhou
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Certificate-based cryptosystem can not only resolve the private key escrow problem inherent in the identity-based cryptosystem but also reduce the cost of public key certificate management in the public key infrastructure-(PKI-) based cryptosystem. Provable data possession (PDP) can ensure the integrity of users’ data stored in the cloud at a very high probability. By combining these two concepts, we propose a certificate-based PDP scheme. We prove that our scheme is secure in the standard model assuming that the Squ-CDH problem is hard. Based on the index logic table, our scheme can be extended to support dynamic operations easily. Efficiency analysis shows that our scheme has high efficiency.


---

## Body

## 1. Introduction

With the rapid development of the cloud storage technology, more and more users and companies store their data in the cloud. However, a new problem has emerged, that is, how users can ensure the integrity of their data if they no longer physically hold them. Luckily, provable data possession (PDP) [1] can resolve this problem. PDP is a lightweight probabilistic integrity checking model of cloud data. It can ensure the integrity of data stored in the cloud at a high probability even if users save no data or only a small amount of data locally. It is one of the core technologies to support cloud storage security.The certificate-based cryptosystem [2] was proposed to reduce the high cost of public key certificate management in the public key infrastructure- (PKI-) based cryptosystem [3] and to eliminate the private key escrow problem inherent in the identity-based cryptosystem [4]. Just like in the PKI-based cryptosystem, a user’s public key in the certificate-based cryptosystem needs a certificate generated by the certificate authority (CA), except that in the latter case, the certificate should participate in the decryption or signing process along with the private key. Therefore, the certificate is verified implicitly. In this way, in the process of encryption or signature verification, the user need not care about whether the certificate has been revoked or out of date, and as a result, the cost of certificate management is reduced. In addition, the private key is produced by the user himself, so the private key escrow problem is also eliminated.By combining the certificate-based cryptosystem and the concept of PDP, we propose a certificate-based PDP scheme. Based on the assumption that the Squ-CDH problem is hard, we prove the security of our scheme in the standard model. Based on the index logical table [5], our scheme can be extended to support dynamic operations easily. At last, we evaluate the efficiency of our scheme, which shows that it is efficient.


### 1.1. Related Work

Ateniese et al. [1] first introduced the notion of PDP in 2007. Afterwards, Erway et al. [6] and Wang et al. [7] proposed dynamic PDP schemes, where users can modify, insert, or delete their data stored in the cloud. In addition, Wang et al.’s scheme [7] also supports public verification, that is, users themselves need not check whether their data are stored intact in the cloud; instead, they can delegate a third party auditor (TPA) to do it. Therefore, the users’ burden is reduced, and furthermore, TPA or users can afford evidence when a dispute occurs. Afterwards, Wang et al. [8] pointed out that TPAs should not obtain users’ data to protect users’ privacy when they audit data in public auditing schemes and proposed a privacy-preserving public PDP scheme. Meanwhile, in their paper, Wang et al. [8] also considered batch auditing so that even if there are multiple tasks from different users to be carried out simultaneously, TPA just needs to do one auditing task, which improves efficiency.All the above schemes were proposed in the PKI-based cryptosystem. The main drawback in the PKI-based cryptosystem is the high cost of certificate management, which hinders its application on a large-scale. To reduce the cost of certificate management, identity-based PDP schemes [9, 10] were proposed. However, what is inherent in it is the private key escrow problem.The certificate-based cryptosystem can not only resolve the private key escrow problem but also reduce the cost of public key certificate management, making it much superior. In 2015, Wang and Li [11] first proposed a certificate-based PDP scheme, but it supports neither public verification nor dynamic operations. In 2020, Wang et al. [12] proposed a lightweight certificate-based PDP scheme, which supports both private and public audits, but it does not support dynamic operations. Both of the above certificate-based PDP schemes rely on the random oracle model. Canetti et al. [13] showed that the random oracle is just an ideal model and that those schemes that are secure under the random oracle model will not be still secure when the random oracle is replaced by some concrete hash functions. Therefore, it is necessary to design certificate-based PDP schemes in the standard model. To the best of our knowledge, so far there have only been two certificate-based PDP schemes proposed in the literature, as mentioned above.In terms of PDP schemes in the standard model, Zhang et al. [14] proposed an identity-based public PDP scheme, but Shen et al. [15] pointed out that the scheme [14] is insecure. A malicious cloud server can modify or delete users’ data arbitrarily, while still being able to produce a proof passing the verification equation as long as it keeps just one data block and its corresponding tag valid. Wang et al. [16] proposed a public and dynamic PDP scheme, but it is based on the PKI technology, which thus requires high cost of certificate management. Zhu et al. [17] proposed a shared data PDP scheme, where a group of users share the data stored in the cloud. It also supports malicious member revocation. Thokchom and Saikia [18] proposed an efficient privacy preserving public dynamic PDP scheme and also extended their scheme to support batch auditing in multiuser and multicloud scenarios, but they did not give security proof of their scheme. Yang et al. [19] proposed a quantum resistant lattice-based PDP scheme, which supports privacy preserving public auditing, dynamic operations, and batch auditing.The rest of this work is organized as follows. In Section2, we introduce the bilinear pairing and some complexity assumptions. In Section 3, we introduce the system model, the formal definition, and the security model of certificate-based PDP. In Section 4, we propose a concrete certificate-based PDP scheme in the standard model. In Section 5, we extend our scheme to support dynamic operations by using the index logic table. In Section 6, we prove the security of the proposed scheme. In Section 7, we evaluate the efficiency of the proposed scheme. We conclude the work in Section 8.


## 1.1. Related Work

Ateniese et al. [1] first introduced the notion of PDP in 2007. Afterwards, Erway et al. [6] and Wang et al. [7] proposed dynamic PDP schemes, where users can modify, insert, or delete their data stored in the cloud. In addition, Wang et al.’s scheme [7] also supports public verification, that is, users themselves need not check whether their data are stored intact in the cloud; instead, they can delegate a third party auditor (TPA) to do it. Therefore, the users’ burden is reduced, and furthermore, TPA or users can afford evidence when a dispute occurs. Afterwards, Wang et al. [8] pointed out that TPAs should not obtain users’ data to protect users’ privacy when they audit data in public auditing schemes and proposed a privacy-preserving public PDP scheme. Meanwhile, in their paper, Wang et al. [8] also considered batch auditing so that even if there are multiple tasks from different users to be carried out simultaneously, TPA just needs to do one auditing task, which improves efficiency.All the above schemes were proposed in the PKI-based cryptosystem. The main drawback in the PKI-based cryptosystem is the high cost of certificate management, which hinders its application on a large-scale. To reduce the cost of certificate management, identity-based PDP schemes [9, 10] were proposed. However, what is inherent in it is the private key escrow problem.The certificate-based cryptosystem can not only resolve the private key escrow problem but also reduce the cost of public key certificate management, making it much superior. In 2015, Wang and Li [11] first proposed a certificate-based PDP scheme, but it supports neither public verification nor dynamic operations. In 2020, Wang et al. [12] proposed a lightweight certificate-based PDP scheme, which supports both private and public audits, but it does not support dynamic operations. Both of the above certificate-based PDP schemes rely on the random oracle model. Canetti et al. [13] showed that the random oracle is just an ideal model and that those schemes that are secure under the random oracle model will not be still secure when the random oracle is replaced by some concrete hash functions. Therefore, it is necessary to design certificate-based PDP schemes in the standard model. To the best of our knowledge, so far there have only been two certificate-based PDP schemes proposed in the literature, as mentioned above.In terms of PDP schemes in the standard model, Zhang et al. [14] proposed an identity-based public PDP scheme, but Shen et al. [15] pointed out that the scheme [14] is insecure. A malicious cloud server can modify or delete users’ data arbitrarily, while still being able to produce a proof passing the verification equation as long as it keeps just one data block and its corresponding tag valid. Wang et al. [16] proposed a public and dynamic PDP scheme, but it is based on the PKI technology, which thus requires high cost of certificate management. Zhu et al. [17] proposed a shared data PDP scheme, where a group of users share the data stored in the cloud. It also supports malicious member revocation. Thokchom and Saikia [18] proposed an efficient privacy preserving public dynamic PDP scheme and also extended their scheme to support batch auditing in multiuser and multicloud scenarios, but they did not give security proof of their scheme. Yang et al. [19] proposed a quantum resistant lattice-based PDP scheme, which supports privacy preserving public auditing, dynamic operations, and batch auditing.The rest of this work is organized as follows. In Section2, we introduce the bilinear pairing and some complexity assumptions. In Section 3, we introduce the system model, the formal definition, and the security model of certificate-based PDP. In Section 4, we propose a concrete certificate-based PDP scheme in the standard model. In Section 5, we extend our scheme to support dynamic operations by using the index logic table. In Section 6, we prove the security of the proposed scheme. In Section 7, we evaluate the efficiency of the proposed scheme. We conclude the work in Section 8.


## 2. Preliminaries

### 2.1. Bilinear Pairing

LetG1andG2 be two multiplicative cyclic groups of prime order q and g be a generator of G1. If the following conditions hold, then it is deemed that the map e:G1×G1⟶G2 is a bilinear pairing.(1)
Bilinearity: for anyaandb∈Zq and PandQ∈G1, the equation ePa,Qb=eP,Qab holds(2)
Nondegeneracy:eg,g≠1G2(3)
Computability: for anyPandQ∈G1, eP,Q can be calculated efficiently


### 2.2. Complexity Assumption

Square Computational Diffie–Hellman (Squ-CDH) problem: givengandga∈G1, where a∈Zq is selected randomly, one does not know the value of a and needs to calculate ga2.LetA be a probabilistic polynomial time (PPT) algorithm, and the advantage of A in solving the Squ-CDH problem on G1 is defined to be AdvASqu−CDH=PrAg,ga=ga2,a∈Zq.Squ-CDH assumption: for everyA, AdvASqu−CDH is negligible.


## 2.1. Bilinear Pairing

LetG1andG2 be two multiplicative cyclic groups of prime order q and g be a generator of G1. If the following conditions hold, then it is deemed that the map e:G1×G1⟶G2 is a bilinear pairing.(1)
Bilinearity: for anyaandb∈Zq and PandQ∈G1, the equation ePa,Qb=eP,Qab holds(2)
Nondegeneracy:eg,g≠1G2(3)
Computability: for anyPandQ∈G1, eP,Q can be calculated efficiently


## 2.2. Complexity Assumption

Square Computational Diffie–Hellman (Squ-CDH) problem: givengandga∈G1, where a∈Zq is selected randomly, one does not know the value of a and needs to calculate ga2.LetA be a probabilistic polynomial time (PPT) algorithm, and the advantage of A in solving the Squ-CDH problem on G1 is defined to be AdvASqu−CDH=PrAg,ga=ga2,a∈Zq.Squ-CDH assumption: for everyA, AdvASqu−CDH is negligible.


## 3. System Model, Definition, and Security Model of the Certificate-Based PDP

### 3.1. System Model

There are four entities involved in a certificate-based PDP scheme as illustrated in Figure1.CA: it is a trusted third party who initializes the system and issues certificates for users.Users: they have a large amount of data to be stored in the cloud. When they decide to store their data in the cloud, they divide their data into file blocks and produce a tag for each file block. Then, they store their data along with these tags in the cloud and delete them locally.TPA: TPA is delegated by users to audit the data in the cloud. It periodically audits the data. When TPA plans to audit the data, it will launch a challenge to the cloud by randomly selecting a subset of the index numbers of file blocks to the cloud. After getting a proof from the cloud server, it checks if the proof can pass an equation in advance. If it can, then it is highly probable that the data stored in the cloud are intact.Cloud server: it provides cloud storage service. When it receives a challenge from TPA, it generates a proof by using the data blocks selected by TPA and their corresponding tags and sends the proof to TPA.Figure 1
System model.


### 3.2. Definition of the Certificate-Based PDP

A certificate-based PDP scheme consists of the following seven algorithms.(1)
Setup: given a security parameter1k, it outputs the system’s public parameters params and a master private key s. It is run by CA.(2)
User-Key-Generation: given the system’s public parametersparams, it outputs a public/private key pair pk,sk. It is run by the user.(3)
Certificate-Gen: given a user’s public keypk, the system’s public parameters params, and the master private key s, it outputs a certificate cert for the user. It is run by CA.(4)
Tag-Gen: Givenn blocks mi∈Zq∗i=1,...,n of a file F, the user’s private key sk, and the system’s public parameters params, it outputs a tag tagi for each file block mi. It is run by the user. Then, the user stores all mi and tagi to the cloud and deletes them locally.(5)
Proof-Gen: given a subset of the index numbers of file blocks selected by TPA, the corresponding tagstagi, and the system’s public parameters Params, it outputs a proof of data. It is run by CSP and CSP sends the proof to TPA.(6)
Proof-Verify: given the system’s public parametersparams and the proof, it outputs TRUE or FALSE. It is run by TPA.(7)
Update-Op: It is run by CSP.Inserting: given the system’s public parametersParams, the index number i, and a file block mi, it does the updating and outputs TRUE or FALSE.Modifying: given the system’s public parametersParams, the index number i, and a new file block mi′, it does the updating and outputs TRUE or FALSE.Deleting: given the system’s public parametersParams and the index number i, it does the updating and outputs TRUE or FALSE.


### 3.3. Security Model of the Certificate-Based PDP

There are two types of adversaries in the certificate-based cryptosystem [2]. The first type of adversary AI does not know the master private key, but he can replace anyone’s public key, as it models any adversary except CA. On the contrary, the second type of adversary AII knows the master private key, but he cannot replace anyone’s public key, as it models the honest-but-curious CA. The honest-but-curious CA means that CA will honestly execute the system protocol, but then he can attack the system. In 2009, Wu et al. [20] introduced the malicious-but-passive CA AII adversary in the certificate-based cryptosystem. This type of AII adversary may be malicious in the system protocol execution. In our security model, this type of adversary AII is considered.Definition 1.
(type I adversary). A certificate-based PDP scheme is secure if for any PPT adversaryAI, the probability that AI wins the following game is negligible.
Setup. Given a security parameter k, challenge C runs the setup algorithm to generate a master private key s and a common parameter Params. Params are given to AI and C keeps s private.
Queries. AI can make the following queries adaptively.(1)
User-Creation queries: AI supplies an identity ID. If the key pair of identity ID has not been created, C runs the User-Key-Generation algorithm to create a private/public key pair SKID,PKID of that user and returns PKID to AI; otherwise, C returns PKID to AI directly.(2)
User-PrivateKey queries: AI supplies an already created identity ID. C returns ID’s private key SKID to AI.(3)
PublicKey-Replacement queries: AI supplies an already created identity ID and a new public/private key pair PKID′,SKID′. C replaces the current public/private key pair PKID,SKID with the new pair PKID′,SKID′.(4)
Certificate queries: AI supplies an already created identity ID and the corresponding public key PKID. C runs the Certificate-Gen algorithm to produce ID’s certificate CertID and sends it to AI.(5)
Tag-Gen queries: AI supplies an already created identity ID and a file block mi. C runs the Tag-Gen algorithm to generate a tag of ID,mi and sends it back to AI.(6)
Update-Op queries: AI supplies an already created identity ID and a request for a dynamic operation. C makes the corresponding dynamic operation.
Challenge. C generates a challenge ID∗,I∗,W∗and sends it to AI, where I∗ is a subset of the index numbers of file blocks and W∗ is a set of random numbers.
Forge.AI generates a proof P∗ for ID∗,I∗,W∗ and sends it to C.
AI wins the game if the following conditions hold.(1)
True=ProofVerifyID∗,P∗(2)
AI has not made a certificate query on ID∗(3)
At least one query of Tag-Gen onID∗,i∗,mi∗ does not happen, where i∗∈I∗Definition 2.
(type II adversary). A certificate-based PDP scheme is secure if for any PPT adversaryAII, the probability that AII wins the following game is negligible.
Setup. Given a security parameter k, adversary AII runs the setup algorithm to generate a master private key s and a common parameter Params. Params and s are given to C.
Queries. AII can make User-Creation, User-PrivateKey, Tag-Gen, and Update-Op queries adaptively, and these queries are the same as in Definition 1. Other queries are not needed for AII.
Challenge. Same as in Definition 1.
Forge.AII generates a proof P∗ for ID∗,I∗,W∗ and sends it to C.
AII wins the game if the following conditions hold.(1)
True=ProofVerifyID∗,P∗(2)
AII has not made a User-PrivateKey query on ID∗(3)
At least one query of Tag-Gen onID∗,i∗,mi∗ does not happen, where i∗∈I∗
Note. In order to resist the malicious-but-passive CA AII adversary, it must let adversary AII run the setup algorithm rather than challenger C.


## 3.1. System Model

There are four entities involved in a certificate-based PDP scheme as illustrated in Figure1.CA: it is a trusted third party who initializes the system and issues certificates for users.Users: they have a large amount of data to be stored in the cloud. When they decide to store their data in the cloud, they divide their data into file blocks and produce a tag for each file block. Then, they store their data along with these tags in the cloud and delete them locally.TPA: TPA is delegated by users to audit the data in the cloud. It periodically audits the data. When TPA plans to audit the data, it will launch a challenge to the cloud by randomly selecting a subset of the index numbers of file blocks to the cloud. After getting a proof from the cloud server, it checks if the proof can pass an equation in advance. If it can, then it is highly probable that the data stored in the cloud are intact.Cloud server: it provides cloud storage service. When it receives a challenge from TPA, it generates a proof by using the data blocks selected by TPA and their corresponding tags and sends the proof to TPA.Figure 1
System model.


## 3.2. Definition of the Certificate-Based PDP

A certificate-based PDP scheme consists of the following seven algorithms.(1)
Setup: given a security parameter1k, it outputs the system’s public parameters params and a master private key s. It is run by CA.(2)
User-Key-Generation: given the system’s public parametersparams, it outputs a public/private key pair pk,sk. It is run by the user.(3)
Certificate-Gen: given a user’s public keypk, the system’s public parameters params, and the master private key s, it outputs a certificate cert for the user. It is run by CA.(4)
Tag-Gen: Givenn blocks mi∈Zq∗i=1,...,n of a file F, the user’s private key sk, and the system’s public parameters params, it outputs a tag tagi for each file block mi. It is run by the user. Then, the user stores all mi and tagi to the cloud and deletes them locally.(5)
Proof-Gen: given a subset of the index numbers of file blocks selected by TPA, the corresponding tagstagi, and the system’s public parameters Params, it outputs a proof of data. It is run by CSP and CSP sends the proof to TPA.(6)
Proof-Verify: given the system’s public parametersparams and the proof, it outputs TRUE or FALSE. It is run by TPA.(7)
Update-Op: It is run by CSP.Inserting: given the system’s public parametersParams, the index number i, and a file block mi, it does the updating and outputs TRUE or FALSE.Modifying: given the system’s public parametersParams, the index number i, and a new file block mi′, it does the updating and outputs TRUE or FALSE.Deleting: given the system’s public parametersParams and the index number i, it does the updating and outputs TRUE or FALSE.


## 3.3. Security Model of the Certificate-Based PDP

There are two types of adversaries in the certificate-based cryptosystem [2]. The first type of adversary AI does not know the master private key, but he can replace anyone’s public key, as it models any adversary except CA. On the contrary, the second type of adversary AII knows the master private key, but he cannot replace anyone’s public key, as it models the honest-but-curious CA. The honest-but-curious CA means that CA will honestly execute the system protocol, but then he can attack the system. In 2009, Wu et al. [20] introduced the malicious-but-passive CA AII adversary in the certificate-based cryptosystem. This type of AII adversary may be malicious in the system protocol execution. In our security model, this type of adversary AII is considered.Definition 1.
(type I adversary). A certificate-based PDP scheme is secure if for any PPT adversaryAI, the probability that AI wins the following game is negligible.
Setup. Given a security parameter k, challenge C runs the setup algorithm to generate a master private key s and a common parameter Params. Params are given to AI and C keeps s private.
Queries. AI can make the following queries adaptively.(1)
User-Creation queries: AI supplies an identity ID. If the key pair of identity ID has not been created, C runs the User-Key-Generation algorithm to create a private/public key pair SKID,PKID of that user and returns PKID to AI; otherwise, C returns PKID to AI directly.(2)
User-PrivateKey queries: AI supplies an already created identity ID. C returns ID’s private key SKID to AI.(3)
PublicKey-Replacement queries: AI supplies an already created identity ID and a new public/private key pair PKID′,SKID′. C replaces the current public/private key pair PKID,SKID with the new pair PKID′,SKID′.(4)
Certificate queries: AI supplies an already created identity ID and the corresponding public key PKID. C runs the Certificate-Gen algorithm to produce ID’s certificate CertID and sends it to AI.(5)
Tag-Gen queries: AI supplies an already created identity ID and a file block mi. C runs the Tag-Gen algorithm to generate a tag of ID,mi and sends it back to AI.(6)
Update-Op queries: AI supplies an already created identity ID and a request for a dynamic operation. C makes the corresponding dynamic operation.
Challenge. C generates a challenge ID∗,I∗,W∗and sends it to AI, where I∗ is a subset of the index numbers of file blocks and W∗ is a set of random numbers.
Forge.AI generates a proof P∗ for ID∗,I∗,W∗ and sends it to C.
AI wins the game if the following conditions hold.(1)
True=ProofVerifyID∗,P∗(2)
AI has not made a certificate query on ID∗(3)
At least one query of Tag-Gen onID∗,i∗,mi∗ does not happen, where i∗∈I∗Definition 2.
(type II adversary). A certificate-based PDP scheme is secure if for any PPT adversaryAII, the probability that AII wins the following game is negligible.
Setup. Given a security parameter k, adversary AII runs the setup algorithm to generate a master private key s and a common parameter Params. Params and s are given to C.
Queries. AII can make User-Creation, User-PrivateKey, Tag-Gen, and Update-Op queries adaptively, and these queries are the same as in Definition 1. Other queries are not needed for AII.
Challenge. Same as in Definition 1.
Forge.AII generates a proof P∗ for ID∗,I∗,W∗ and sends it to C.
AII wins the game if the following conditions hold.(1)
True=ProofVerifyID∗,P∗(2)
AII has not made a User-PrivateKey query on ID∗(3)
At least one query of Tag-Gen onID∗,i∗,mi∗ does not happen, where i∗∈I∗
Note. In order to resist the malicious-but-passive CA AII adversary, it must let adversary AII run the setup algorithm rather than challenger C.


## 4. A Concrete Certificate-Based PDP Scheme

### 4.1. Concrete Scheme

Hu:0,1∗⟶0,1nu denotes a collision-resistant cryptographic hash function for some nu∈Zq∗, which is used to create identities of the desired length.(1)
Setup: given a security parameter1k, CA chooses two cyclic groups G1 and G2 of prime order q, a random generator g of G1, a bilinear map e:G1×G1⟶G2, three hash functions H:0,1∗⟶Zq∗, H1:0,1∗⟶0,1nu, and H2:0,1∗⟶G1, a pseudorandom function f:Zq∗×1,2,…,n⟶Zq∗, and a pseudorandom permutation π:Zq∗×1,2,…,n⟶1,2,…,n. He randomly selects s,v′,v1,v2,…,vnu∈Zq∗ and sets g1=gs, u′=gv′, ui=gvii=1,2,…,nu, and U=ui∈G1nu. CA defines a function FuID=u′∏j=1nuujij, where ID=i1i2…inu is a bit string. The public parameters are Params=G1,G2,e,g,g1,u′,U,Fu,H,H1,H2,f,π, and the master secret key is msk=s,v′,v1,v2,...,vnu.(2)
User-Key-Generation: the userID randomly selects xIDandyID∈Zq∗ as his secret keys and computes his public key as UPKID=UPKID,1,UPKID,2,UPKID,3=gxID,gyID,gσID, where σID=yID+xIDHUPKID,1,UPKID,2,Paramsmodq is a Schnorr one-time signature. The signature can be generated using the technique of Fiat–Shamir transform without random oracles as described in [21].(3)
Certificate-Gen: given a user’s identity ID and his public keyUPKID, CA randomly selects rID∈Zq∗ and computes the user’s certificate as CertID=CertID,1,CertID,2=gs2FuidrID,grID, where id=H1ID,UPKID,1,UPKID,2,UPKID,3.(4)
Tag-Gen: let a fileF be divided into n blocks mi∈Zq∗, i=1,2,...,n. User ID computes tID,1=CertID,2xID2, WID,i=H2ID,UPKID,1,UPKID,2,UPKID,3,tID,1,i, and tID,i,2=WID,iCertID,1xID2mi. Finally, the tags are σ=tID,1,tID,i,2i=1,2,...,n.(5)
Proof-Gen: TPA selects a random integerc and two random elements k1andk2∈Zq∗. TPA sends the challenge ID,c,k1,k2 to CSP. CSP computes ij=πk1j, and wj=fk2j, where j=1,2,...,c. Let I=i1,i2,...,ic, and CSP computes S=∏i∈ItID,i,2wi and δ=∑i∈Iwimi and sends the proof tID,1,S,δ to TPA.(6)
Proof-Verify: TPA computesij=πk1j, and wj=fk2j, where j=1,2,...,c. Let I=i1,i2,...,ic, and TPA computes c1=HUPKID,1,UPKID,2,Paramsmodq, id=H1ID,UPKID,1,UPKID,2,UPKID,3, and WID,i=H2ID,UPKID,1,UPKID,2,UPKID,3,tID,1,i. TPA verifies whether eUPKID,3,g=eUPKID,2,geUPKID,1,gc1 and eS,g=e∏i∈IWID,iwi,geUPKID,1,UPKID,1δeFuid,tID,1δ hold. If they do, he accepts it.


### 4.2. Correctness

(1)eS,g=e∏i∈ItID,i,2wi,g=e∏i∈IWID,iwiCertID,1xID2miwi,g=e∏i∈IWID,iwi,geCertID,1xID2δ,g=e∏i∈IWID,iwi,gegs2xID2δFuidrIDxID2δ,g=e∏i∈IWID,iwi,geUPKID,1,UPKID,1δeFuidrIDxID2δ,g=e∏i∈IWID,iwi,geUPKID,1,UPKID,1δeFuid,tID,1δ.


## 4.1. Concrete Scheme

Hu:0,1∗⟶0,1nu denotes a collision-resistant cryptographic hash function for some nu∈Zq∗, which is used to create identities of the desired length.(1)
Setup: given a security parameter1k, CA chooses two cyclic groups G1 and G2 of prime order q, a random generator g of G1, a bilinear map e:G1×G1⟶G2, three hash functions H:0,1∗⟶Zq∗, H1:0,1∗⟶0,1nu, and H2:0,1∗⟶G1, a pseudorandom function f:Zq∗×1,2,…,n⟶Zq∗, and a pseudorandom permutation π:Zq∗×1,2,…,n⟶1,2,…,n. He randomly selects s,v′,v1,v2,…,vnu∈Zq∗ and sets g1=gs, u′=gv′, ui=gvii=1,2,…,nu, and U=ui∈G1nu. CA defines a function FuID=u′∏j=1nuujij, where ID=i1i2…inu is a bit string. The public parameters are Params=G1,G2,e,g,g1,u′,U,Fu,H,H1,H2,f,π, and the master secret key is msk=s,v′,v1,v2,...,vnu.(2)
User-Key-Generation: the userID randomly selects xIDandyID∈Zq∗ as his secret keys and computes his public key as UPKID=UPKID,1,UPKID,2,UPKID,3=gxID,gyID,gσID, where σID=yID+xIDHUPKID,1,UPKID,2,Paramsmodq is a Schnorr one-time signature. The signature can be generated using the technique of Fiat–Shamir transform without random oracles as described in [21].(3)
Certificate-Gen: given a user’s identity ID and his public keyUPKID, CA randomly selects rID∈Zq∗ and computes the user’s certificate as CertID=CertID,1,CertID,2=gs2FuidrID,grID, where id=H1ID,UPKID,1,UPKID,2,UPKID,3.(4)
Tag-Gen: let a fileF be divided into n blocks mi∈Zq∗, i=1,2,...,n. User ID computes tID,1=CertID,2xID2, WID,i=H2ID,UPKID,1,UPKID,2,UPKID,3,tID,1,i, and tID,i,2=WID,iCertID,1xID2mi. Finally, the tags are σ=tID,1,tID,i,2i=1,2,...,n.(5)
Proof-Gen: TPA selects a random integerc and two random elements k1andk2∈Zq∗. TPA sends the challenge ID,c,k1,k2 to CSP. CSP computes ij=πk1j, and wj=fk2j, where j=1,2,...,c. Let I=i1,i2,...,ic, and CSP computes S=∏i∈ItID,i,2wi and δ=∑i∈Iwimi and sends the proof tID,1,S,δ to TPA.(6)
Proof-Verify: TPA computesij=πk1j, and wj=fk2j, where j=1,2,...,c. Let I=i1,i2,...,ic, and TPA computes c1=HUPKID,1,UPKID,2,Paramsmodq, id=H1ID,UPKID,1,UPKID,2,UPKID,3, and WID,i=H2ID,UPKID,1,UPKID,2,UPKID,3,tID,1,i. TPA verifies whether eUPKID,3,g=eUPKID,2,geUPKID,1,gc1 and eS,g=e∏i∈IWID,iwi,geUPKID,1,UPKID,1δeFuid,tID,1δ hold. If they do, he accepts it.


## 4.2. Correctness

(1)eS,g=e∏i∈ItID,i,2wi,g=e∏i∈IWID,iwiCertID,1xID2miwi,g=e∏i∈IWID,iwi,geCertID,1xID2δ,g=e∏i∈IWID,iwi,gegs2xID2δFuidrIDxID2δ,g=e∏i∈IWID,iwi,geUPKID,1,UPKID,1δeFuidrIDxID2δ,g=e∏i∈IWID,iwi,geUPKID,1,UPKID,1δeFuid,tID,1δ.


## 5. Data Dynamic

### 5.1. Index Logic Table

Wang et al. [5] introduced the index logic table (ILT) to support dynamic operations in PDP schemes, as ILT can overcome the delete-insert attack [5] in the map version table [22] structure. An ILT includes two columns: the index number (the first column) and the logic number (the second column). In addition, one additional column (the third column) is used to explain the ILT and not appear in the ILT actually. Let “iin” denote the first column, “lln” denote the second one, “blocks” denote the third one, “inEF” denote the last line of column 1, and “lnEF” denote the last line of column 2.The ILT is illustrated in Table1. Please note that the last row of blocks does not include any file block in Table 1.Table 1
Index logic table.
iinllnblocks(a) Initial11M122M233M344M455M566M677null(b) Modify at 411M122M233M347M4’55M566M678null(c) Insert after 411M122M233M347M4’58M’’65M576M689Null(d) Delete at 211M123M337M4’48M’’55M566M679nullThere are four operations in ILT, namely, initializing, modifying, inserting, and deleting. We assume a fileF is divided into n blocks. The initializing operation is described in algorithm 1(a) of Table 2, with an example of n = 6 given in Table 1(a). The modifying operation is described in algorithm 1(b) of Table 2, with an example of modifying file block m4 to m4’ at i = 4 given in Table 1(b). The inserting operation is described in algorithm 1(c) of Table 2, with an example of inserting a file block m’’ after i = 4 given in Table 1(c). The deleting operation is described in algorithm 1(d) of Table 2, with an example of deleting i = 2 given in Table 1(d).Table 2
Algorithm 1.
Algorithm 1(a) Initial(b) Modify(c) Insert(d) DeleteFor (j = 1; j<=n; j++)lln[i] = lnEF;lnEF = lnEF+1;For (j = i;j < inEF;j++){ iin[j] = j;blocks[i] = mi’;inEF = inEF+1;{ lln[j] = lln[j+1];lln[j] = j;lnEF = lnEF+1;blocks[inEF] = null;blocks[j] = blocks[j+1];}blocks[j] = mj; }lln[inEF] = lnEF;lln[inEF] = lnEF;inEF = inEF-1;inEF = j;iin[inEF] = inEF;lnEF = j;For (j = inEF-1,j > i,j--)blocks[lnEF] = null;{lln[j] = lln[j-1];}iin[inEF]= inEF;blocks[j] = blocks[j-1];lln[inEF] = lnEF;}lln[i] = lnEF-1;blocks[i] = m’’;


### 5.2. Dynamic Operations

To make our scheme support dynamic operations, we must replaceWID,i=H2ID,UPKID,1,UPKID,2,UPKID,3,tID,1,i with WID,i=H2ID,UPKID,1,UPKID,2,UPKID,3,tID,1,llni in the Tag-Gen and the Proof-Verify algorithms; in other words, we must replace i with llni. The ILT must be stored in users and TPA locally.(1)
Data modifying: when a user wants to modify a file block mi to mi’ at iin = i, he runs algorithm 1(b) first. Then, he computes tag’ for mi’. He uploads mi’, tag’, iin, and ILT to the cloud and deletes mi’ and tag’ locally. CSP makes the corresponding modification.(2)
Data inserting: when a user wants to insert a file block m’’ after iin = i, he runs algorithm 1 (c) first. Then, he computes tag’’ for m’’. He uploads m’’, tag’’, iin, and ILT to the cloud and deletes m’’ and tag’’ locally. CSP makes the corresponding insertion.(3)
Data deleting: when a user wants to delete a file block mi at iin = i, he runs algorithm 1 (d) first. Then, he uploads iin and ILT to the cloud. CSP makes the corresponding deletion.


## 5.1. Index Logic Table

Wang et al. [5] introduced the index logic table (ILT) to support dynamic operations in PDP schemes, as ILT can overcome the delete-insert attack [5] in the map version table [22] structure. An ILT includes two columns: the index number (the first column) and the logic number (the second column). In addition, one additional column (the third column) is used to explain the ILT and not appear in the ILT actually. Let “iin” denote the first column, “lln” denote the second one, “blocks” denote the third one, “inEF” denote the last line of column 1, and “lnEF” denote the last line of column 2.The ILT is illustrated in Table1. Please note that the last row of blocks does not include any file block in Table 1.Table 1
Index logic table.
iinllnblocks(a) Initial11M122M233M344M455M566M677null(b) Modify at 411M122M233M347M4’55M566M678null(c) Insert after 411M122M233M347M4’58M’’65M576M689Null(d) Delete at 211M123M337M4’48M’’55M566M679nullThere are four operations in ILT, namely, initializing, modifying, inserting, and deleting. We assume a fileF is divided into n blocks. The initializing operation is described in algorithm 1(a) of Table 2, with an example of n = 6 given in Table 1(a). The modifying operation is described in algorithm 1(b) of Table 2, with an example of modifying file block m4 to m4’ at i = 4 given in Table 1(b). The inserting operation is described in algorithm 1(c) of Table 2, with an example of inserting a file block m’’ after i = 4 given in Table 1(c). The deleting operation is described in algorithm 1(d) of Table 2, with an example of deleting i = 2 given in Table 1(d).Table 2
Algorithm 1.
Algorithm 1(a) Initial(b) Modify(c) Insert(d) DeleteFor (j = 1; j<=n; j++)lln[i] = lnEF;lnEF = lnEF+1;For (j = i;j < inEF;j++){ iin[j] = j;blocks[i] = mi’;inEF = inEF+1;{ lln[j] = lln[j+1];lln[j] = j;lnEF = lnEF+1;blocks[inEF] = null;blocks[j] = blocks[j+1];}blocks[j] = mj; }lln[inEF] = lnEF;lln[inEF] = lnEF;inEF = inEF-1;inEF = j;iin[inEF] = inEF;lnEF = j;For (j = inEF-1,j > i,j--)blocks[lnEF] = null;{lln[j] = lln[j-1];}iin[inEF]= inEF;blocks[j] = blocks[j-1];lln[inEF] = lnEF;}lln[i] = lnEF-1;blocks[i] = m’’;


## 5.2. Dynamic Operations

To make our scheme support dynamic operations, we must replaceWID,i=H2ID,UPKID,1,UPKID,2,UPKID,3,tID,1,i with WID,i=H2ID,UPKID,1,UPKID,2,UPKID,3,tID,1,llni in the Tag-Gen and the Proof-Verify algorithms; in other words, we must replace i with llni. The ILT must be stored in users and TPA locally.(1)
Data modifying: when a user wants to modify a file block mi to mi’ at iin = i, he runs algorithm 1(b) first. Then, he computes tag’ for mi’. He uploads mi’, tag’, iin, and ILT to the cloud and deletes mi’ and tag’ locally. CSP makes the corresponding modification.(2)
Data inserting: when a user wants to insert a file block m’’ after iin = i, he runs algorithm 1 (c) first. Then, he computes tag’’ for m’’. He uploads m’’, tag’’, iin, and ILT to the cloud and deletes m’’ and tag’’ locally. CSP makes the corresponding insertion.(3)
Data deleting: when a user wants to delete a file block mi at iin = i, he runs algorithm 1 (d) first. Then, he uploads iin and ILT to the cloud. CSP makes the corresponding deletion.


## 6. Unforgeability

Theorem 1 (type I unforgeability).
In the standard model, if a PPT attackerAI has a nonnegligible advantage ε in winning the game of Definition 1, running for time t and performing at most qUCreation user creation queries, qCert certificate queries, and qtag Tag-Gen queries, then there is an algorithm C that solves the Squ-CDH problem with an advantage AdvCSqu−CDH≥ε/4qCert+qtagnu+1 for time t+OqCert⋅nu⋅tm+qUCreation+qCert+qtagte, where tm and te denote the time for a multiplication and an exponentiation on G1, respectively.Proof.
SupposeC is given g,B=gb∈G1 for randomly chosen b∈Zq. C does not know the value of b and is asked to compute gb2. To utilize adversary AI, challenger C will simulate all the oracles defined in Definition 1. C maintains a table tb=ID,CertID,xID,yID,UPKID,tag=0, which is initially empty. tag=0 means that the public key is not replaced.
Setup Let lu=2qCert+qtag. C randomly chooses the following elements:(1)
An integerku (0≤ku≤nu). We assume that lunu+1<q for the given values of qCert, qtag, and nu(2)
An integerxu′∈Zlu, and a vector Xu=xu,inuxu,i∈Zlu(3)
An integeryu′∈Zq, and a vector Yu=yu,inuyu,i∈Zq
For convenience, we define the following functions:(2)Juid=xu′−luku+∑j=1nuijxu,j,Kuid=yu′+∑j=1nuijyu,j,where id=i1i2...inu is a bit string.
Then,C randomly chooses two cyclic groups G1 and G2 of prime order q, a random generator g of G1, a bilinear map e:G1×G1⟶G2, and three hash functions H:0,1∗⟶Zq∗, H1:0,1∗⟶0,1nu, and H2:0,1∗⟶G1. He sets g1=B, u′=Bxu′−lukugyu′, ui=Bxu,igyu,i(0≤i≤nu), and U=ui∈G1nu. This assignment means Fuid=BJuidgKuid and that the master secret key s=b, which is not known to C. C chooses a pseudorandom function f:Zq∗×1,2,…,n⟶Zq∗ and a pseudorandom permutation π:Zq∗×1,2,…,n⟶1,2,…,n. C outputs the public parameters Params=G1,G2,e,g,g1,u′,U,Fu,H,H1,H2,f,π.
Queries.AI can adaptively make a polynomial bounded number of queries as follows.(1)
User-Creation queries:AI supplies an identity ID. C first checks the table tb to see whether it contains the item or not. If it does, C returns ID’s public key UPKID to AI; otherwise, C executes the User-Key-Generation algorithm to produce ID’s private/public key pair xID,yID,UPKID. C puts ID,−,xID,yID,UPKID,tag=0 into the table tb and returns UPKID to AI.(2)
User-PrivateKey queries:AI supplies an already created identity ID. C searches the table tb to find out the private keys xIDandyID and returns them to AI.(3)
PublicKey-Replacement queries:AI supplies an already created identity ID and a new public/private key pair UPKID′,xID′,yID′. C replaces the current public/private key pair UPKID,xID,yID with the new key pair UPKID′,xID′,yID′ in the table tb and sets tag=1.(4)
Certificate queries:AI supplies an already created identity ID and ID’s public key UPKID. C first checks table tb to see whether the certificate CertID is produced or not. If it does, C returns the certificate CertID to AI; otherwise, C computes id=H1ID,UPKID,1,UPKID,2,UPKID,3 and produces the certificate as follows (C does not know the master private key). Then, C returns the certificate CertID to AI and updates“−”with the CertID in table tb.(a)
Juid≠0modq. C randomly selects rID∈Zq∗ and computes the user’s certificate as CertID=CertID,1,CertID,2=B−Kuid/Juid⋅FuidrID,B−1/JuidgrID=gb2⋅FuidrID¯,grID¯, where rID¯=rID−b/Juid.(b)
Juid=0modq. C aborts.To make the analysis of the simulation easier, we will forceC to abort whenever Juid=0modlu. (Juid≠0modlu implies Juid≠0modq, given the assumption lunu+1<q).(5)
Tag-Gen queries:AI supplies an already created identity ID and a file block mi. C computes id=H1ID,UPKID,1,UPKID,2,UPKID,3.(a)
Juid≠0modq. C produces the tag as normal because C can get the certificate and private key of ID.(b)
Juid=0modq. C aborts.(6)
Update-Op queries:AI supplies an already created identity ID. For inserting operation, AI also supplies the “iin” number in the ILT table and a new file block m; for modifying operation, AI also supplies the “iin” number in the ILT table, the old file block mi and the new file block mi’; for deleting operation, AI also supplies the “iin” number in the ILT table. CSP makes the corresponding dynamic operations and returns ILT to the user.
Challenge:C generates a challenge ID∗,c,k1,k2 to AI. AI computes ij∗=πk1j and wj∗=fk2j, where j=1,2,...,c. Let I∗=i1∗,i2∗,...,ic∗.
Forge:AI generates a forged proof tID∗,1,S∗,δ∗ for ID∗,I∗,wi∗i∈I∗. According to Definition 1, at least one query of Tag-Gen on ID∗,i∗,mi∗, where i∗∈I∗, must not happen, that is, AI has generated a forged tag σ∗=tID∗,1,tID∗,i∗,2, i∗∈I∗, for file block mi∗. C computes id∗=H1ID∗,UPKID∗,1,UPKID∗,2,UPKID∗,3. If Juid∗≠0modq, then C aborts; otherwise, we have Fuid∗=gKuid∗. If tID∗,1,S∗,δ∗ can pass the Proof-Verify algorithm and AI does not violate the restrictions of Definition 1, then C retrieves the private key xID∗ of ID∗ and computes WID∗,i∗=H2ID∗,UPKID∗,1,UPKID∗,2,UPKID∗,3,tID∗,1,i∗ and tID∗,i∗,2/Wi∗t1∗Kuid∗mi∗=WID∗,i∗CertID∗,1xID∗2mi∗/WID∗,i∗CertID∗,2xID∗2Kuid∗mi∗=gb2⋅xID∗2mi∗⋅Fuid∗xID∗2⋅rID∗mi∗/grID∗xID∗2Kuid∗mi∗=gb2⋅xID∗2mi∗⋅gKuid∗xID∗2rID∗mi∗/grID∗xID∗2Kuid∗mi∗=gb2⋅xID∗2mi∗. Because C knows xID∗ and mi∗, he can compute gb2 from gb2⋅xID∗2mi∗. C solves the Squ-CDH problem.
Now, we assess the probability of success. If the simulation is not aborted, the following conditions must be met.(1)
In all certificate and signature queries,Juid≠0modq(2)
In the forgery stage,Juid∗=0modq
LetID1,ID2,…,IDqI be the identities appearing in these queries, but they do not involve any of the challenge identities. Clearly, we have qI≤qCert+qtag. Define the events A1∗,A2∗,andAi as A1∗:Juid∗=0modq and Ai:Juid≠0modq,i=1,2,…,qI.
Therefore, the probability ofC not aborting the simulation is Pr¬abort≥PrΛi=1qIAi∧A1∗. We have PrA1∗=1/lunu+1 and PrΛi=1qIAi∧A1∗≥1/lunu+11−qCert+qtag/lu. Therefore, AdvCSqu−CDH≥ε/4qCert+qtagnu+1.
The time complexity of challengerC depends on the exponentiations, multiplications, and pairing operations needed in all above queries. The user creation queries need O1 exponentiations. The certificate queries need Onu multiplications and O1 exponentiations. The Tag-Gen queries need O1 exponentiations. Therefore, the time complexity of C is t+OqCert⋅nu⋅tm+qUCreation+qCert+qtagte.Theorem 2 (type II unforgeability).
In the standard model, if a PPT attackerAII has a nonnegligible advantage ε in winning the game of Definition 2 running for time t and performing at most qUCreation user creation queries, qp private key queries, and qtag Tag-Gen queries, then there is an algorithm C that solves the Squ-CDH problem with an advantage AdvCSqu−CDH≥ε/qUCreation1−1/qp1−1/qtag for time t+OqUCreation+qtagte, where te denotes the time for an exponentiation on G1.Proof.
Let us supposeC is given g,B=gb∈G1 for randomly chosen b∈Zq. C does not know the value of b and is asked to compute gb2. To utilize the adversary AII, challenger C will simulate all the oracles defined in Definition 2. C maintains a table tb=ID,xID,yID,UPKID, which is initially empty.
Setup.AII randomly chooses two cyclic groups G1 and G2 of prime order q, a random generator h of G1, a bilinear map e:G1×G1⟶G2, and three hash functions H:0,1∗⟶Zq∗, H1:0,1∗⟶0,1nu, and H2:0,1∗⟶G1, and α,yu′,yu,1,yu,2,...,yu,nu∈Zq∗. He/she sets g1=hα, u′=hyu′, ui=hyu,i0≤i≤nu, and U=ui∈G1nu, where id=i1i2...inu is a bit string. Let Kuid=yu′+∑j=1nuij⋅yu,j, and this assignment means Fuid=hKuid. AII chooses a pseudorandom function f:Zq∗×1,2,…,n⟶Zq∗ and a pseudorandom permutation π:Zq∗×1,2,…,n⟶1,2,…,n. The master secret key is α,yu′,yu,1,yu,2,…,yu,nu. AII outputs the public parameters Params=G1,G2,e,h,g1,u′,U,Fu,H,H1,H2,f,π and α,yu′,yu,1,yu,2,…,yu,nu to C.
Ash is a generator of G1, there must be a b′∈Zq∗ to make the equation B=hb′ hold. Knowing h,B=hb′∈G1, now C’s goal becomes computing hb′2. C randomly selects an index π from 1,…,qUCreation.
Queries.AII can make the following queries adaptively.(1)
User-Creation queries:AII supplies an identity IDi. C first checks table tb to see whether it contains the item or not. If it does, C returns IDi’s public key UPKIDi to AII. Otherwise, C produces the public/private key pair as follows and returns UPKIDi to AII.(a)
IDi≠IDπ. C executes the User-Key-Generation algorithm as normal to produce IDi’s private/public key pair xIDi,yIDi,UPKIDi=hxIDi,hyIDi,hσIDi. C puts IDi,xIDi,yIDi,UPKIDi into table tb.(b)
IDi=IDπ. C randomly selects yIDi∈Zq∗ and computes IDi’s public key as UPKIDi=B,hyIDi,hyIDi⋅Bc, where c=HK,UPKIDi,1,UPKIDi,2,Params. C puts IDi,−,yIDi,UPKIDi into table tb (the implicitly defined private key xIDi=b′, which is not known to C).(2)
Private Key queries:AII supplies an already created identity IDi.(a)
IDi≠IDπ. C searches table tb to find out the private keys xIDiandyIDi and returns them to AII.(b)
IDi=IDπ. C aborts.(3)
Tag-Gen queries:AII supplies an already created identity IDi and a file block mi. C computes id=H1ID,UPKID,1,UPKID,2,UPKID,3.(a)
IDi≠IDπ. C produces the tag as normal because C can get the certificate and private key of IDi.(b)
IDi=IDπ. C aborts.(4)
Update-Op queries: same as in Theorem1.
Challenge:C generates a challenge ID∗,c,k1,k2 to AII. AII computes ij∗=πk1j and wj∗=fk2j, where j=1,2,...,c. Let I∗=i1∗,i2∗,...,ic∗.
Forge:AII generates a forged proof tID∗,1,S∗,δ∗ for ID∗,I∗,wi∗i∈I∗. According to Definition 2, at least one query of Tag-Gen on ID∗,i∗,mi∗, where i∗∈I∗, must not happen, that is, AII has generated a forged tag σ∗=tID∗,1,tID∗,i∗,2, i∗∈I∗ for file block mi∗. If ID∗≠IDπ, C aborts; otherwise, if tID∗,1,S∗,δ∗ can pass the Proof-Verify algorithm and AII does not violate the restrictions of Definition 2, then C can compute id∗=H1ID∗,UPKID∗,1,UPKID∗,2,UPKID∗,3, Kuid∗=yu′+∑j=1nuij∗⋅yu,jid∗=i1∗i2∗…inu∗, WID∗,i∗=H2ID∗,UPKID∗,1,UPKID∗,2,UPKID∗,3,tID∗,1,i∗, and tID∗,i∗,2/WID∗,i∗tID∗,1Kuid∗mi∗=WID∗,i∗CertID∗,1b′2mi∗/WID∗,i∗CertID∗,2b′2Kuid∗mi∗=hα2⋅b′2mi∗⋅Fuid∗b′2⋅rID∗mi∗/hrID∗b′2Kui∗mi∗=hα2⋅b′2mi∗⋅hKuid∗b′2rID∗mi∗/hrID∗b′2Kuid∗mi∗=hα2⋅b′2mi∗, from which C can compute hb′2.
Now, we assess the probability of success. If the simulation is not aborted, the following conditions must be met.(1)
In all private key queries,IDi≠IDπ(2)
In all Tag-Gen queries,IDi≠IDπ(3)
In the forgery stage,ID∗=IDπ
At a probability1/qUCreation, the adversary will output an identity IDπ with index π in the forgery stage. The probability of IDi≠IDπ in the private key queries is 1−1/qp. The probability of IDi≠IDπ in the Tag-Gen queries is 1−1/qtag. Thus, we can conclude that the advantage of C is AdvCSqu−CDH≥ε/qUCreation1−1/qp1−1/qtag.
The time complexity of challengerC depends on the exponentiations, multiplications, and pairings’ operations needed in all above queries. The user creation queries need O1 exponentiations. The Tag-Gen queries need O1 exponentiations. Therefore, the time complexity of C is t+OqUCreation+qtagte.
Note. The goal of C is to compute gb2. However, the initialization of system is run by AII, and therefore, there is a high probability that AII will not choose g as one of the system parameters. In this scenario, we change the goal of C from computing gb2 to computing hb′2.


## 7. Analysis of Efficiency

We analyse the efficiency of our scheme in terms of computational time, communication overhead, and storage cost. Leth, e1, e2, and p denote a map-to-point hash computation, an exponentiation computation on G1, an exponentiation computation on G2, and a bilinear pairing computation, respectively. We compare our scheme with those proposed also in the standard model, which include schemes [14, 16, 18]. To show a more direct comparison with these schemes, we also adopt the experiment results of the scheme [23]. The computation time of each operation is shown in Table 3 and that of each scheme is shown in Table 4. By combining Tables 3 and 4, we get Table 5. Since the scheme [14, 16] also divided a file block into s sectors, for the sake of fairness, we set s = 1 in Table 5. From Table 5, we can get Figure 2 for CSP’s running time and Figure 3 for TPA’s running time. From Table 5, we can see that the scheme [18] is the most efficient one in terms of the Tag-Gen algorithm. From Figure 2, we can see that our scheme is the most efficient one in terms of CSP’s running time (the Proof-Gen algorithm). From Figure 3, we can see that scheme [14] is the most efficient one in terms of TPA’s running time (the Proof-Verify algorithm). The communication overhead of each scheme is shown in Table 6. Based on the experiment results of the scheme [23], the size of q is 512 bits, and if the technique of point compression is used, the size of an element in G1 or G2 is 512 bits. An integer is represented by 64 bits. From this, we get Table 7. From Table 7 and by taking s = 1, we obtain Figure 4. From Table 7, we can see that our scheme is the most efficient one in terms of the Tag-Gen algorithm, and in summary, our scheme is the most efficient one in terms of both storage and communication of tags. From Figure 4, we can see that our scheme is the most efficient one in the communication of Proof-Gen.Table 3
Computational time (ms).
HE1E2p18.6737.7360.16015.500Table 4
Computational time.
SchemesTag-GenProof-GenProof-Verify[14](2n + s) e13ce13p + (s + 1) e1[16](s + 3) ne1 + 6e13p + 2 (c + 1) e1 + e16p + (c + s + 4) e1[18]ne1c (p + 3e1)c (p + e2)Ours(n + 1) e1 + nhce17p + ce1 + 3e2 + hn denotes the total number of file blocks, s means that a file block is divided into s sectors, and c denotes the total number of challenge blocks.Table 5
Computational time.
SchemesTag-GenProof-GenProof-Verify[14]15.472n + 7.73623.208c61.972[16]30.944n + 46.41615.472c + 69.7087.736c + 131.68[18]7.736n38.708c15.66cOurs26.409n + 7.7367.736c7.736c + 127.653Figure 2
Comparisons of CSP’s running time.Figure 3
Comparisons of TPA’s running time.Table 6
Communication overhead (bit).
SchemesTag-GenProof-Gen[14]2n|G1||N|c + |q| + 2|G1| + s|q|[16]2n|G1| + n|q| + 4|G1|(|N| + |q|) c + (s + 2)|q| + (c + 4)|G1|[18]n (|G1| + |q|)(|N| + |q|)c + |G2|Ours(n + 1)|G1||N| + 3|q| + |G1|Table 7
Communication overhead (bit).
SchemesTag-GenProof-Gen[14]1024n64c + 160s + 2284[16]1184n + 2048736c + 160s + 2368[18]672n224c + 512Ours512n + 5121056Figure 4
Comparisons of CSP’s communication overhead.We also compare our scheme with those certificate-based PDP schemes, which include schemes [11, 12]. The computation time of each scheme is shown in Table 8. By combining Tables 3 and 8, we get Table 9. From Table 9, we can get Figure 5 for CSP’s running time and Figure 6 for TPA’s running time. From Table 9, we can see that the scheme [11] is the most efficient one in terms of the Tag-Gen algorithm. From Figure 5, we can see that all schemes are the same in terms of the CSP’s running time (the Proof-Gen algorithm). From Figure 6, we can see that scheme [11] is the most efficient one in terms of TPA’s running time (the Proof-Verify algorithm). The communication overhead of each scheme is shown in Table 10. By using the concrete parameters, we get Table 11. From Table 11, we can see that the scheme [11] is the most efficient one in terms of the Tag-Gen algorithm, and thus, the scheme [11] is the most efficient one in terms of both storage and communication of tags. Also from Table 11, we can see that all schemes are almost the same in the communication of Proof-Gen. Therefore, it can be concluded that our scheme is an efficient scheme.Table 8
Computational time.
SchemesTag-GenProof-GenProof-Verify[11](n + 1) e1ce12p + (c + 3) e1[12](3n + s) e1 + (n + 2)hce12p + (c + 4) e1 + hOurs(n + 1) e1 + nhce17p + ce1 + 3e2 + hTable 9
Computational time.
SchemesTag-GenProof-GenProof-Verify[11]7.736n + 7.7367.736c7.736c + 54.208[12]41.881n + 7.736s + 37.3467.736c7.736c + 80.617Ours26.409n + 7.7367.736c7.736c + 127.653Figure 5
Comparisons of CSP’s running time.Figure 6
Comparisons of TPA’s running time.Table 10
Communication overhead (bit).
SchemesTag-GenProof-Gen[11]n|G1||N| + 3|q| + |G1|[12](n + s+2)|G1| + |q||N| + (s + 2)|q| + |G1|Ours(n + 1)|G1||N| + 3|q| + |G1|Table 11
Communication overhead (bit).
SchemesTag-GenProof-Gen[11]512n1056[12]512(n + s) + 672160s + 896Ours512n + 5121056In our system, the storage cost of ILT is linear to the size of the outsourced data and the file block is directly used as an exponent in the tag generation algorithm. Now, let us analyse how the file block size affects the efficiency. If the file block size is small, there will be a large number of blocks, and then, the storage cost of ILT will be high. Now, let us take a look at the calculation efficiency of tag. It is related to the number of tags and the computation cost of each tag. Since the block is directly used as an exponent in the tag generation algorithm andmi∈Zq∗, the size of block mi has no effect on the computation cost of each tag, that is, no matter what the block size is, the computation cost of each tag is one exponent computation. However, the smaller the file block size is, the more blocks there will be and the more tags there will be, leading to a higher computation cost of tags. Therefore, to reduce the storage cost of ILT and to improve the computation efficiency of tags, the file block size should be as large as possible. But, when the user is performing dynamic operations, the file block size should be as small as possible because in this case, the communication cost of each modification or insertion will be lower. Since how many blocks the file is divided into is decided by the users themselves, the users must make a tradeoff among storage efficiency, computation cost of tags, and efficiency of dynamic operations. The system can give a reference value. Take a 1 GB file for example. If a user divides it into blocks with a size of 16 KB each, then there will be a total of 62500 file blocks. Each entry of ILT contains just two integers iis and lln (total 8 bytes). Therefore, the total storage cost of ILT is 512 KB (<0.05% of the file size). In dynamic operations, the communication cost of inserting or modifying one block is the communication cost of regular tags plus the transmission cost of 16 KB file blocks. The users can refer to these values when they divide the file.In addition, the purpose of Ateniese et al. [1] proposing PDP is to realize probabilistic proofs of possession by sampling a small amount of data from the server. They concluded that if there are 1% of the file blocks deleted by the cloud, then the user or TPA just needs to randomly choose 460 blocks as a challenge to the cloud to detect the cloud’s misbehaviour with a probability of at least 99%. If there are 10000 file blocks, we just need to challenge 460/10000 = 4.6% of the blocks. In this view, it would be better if the number of file blocks is more than 10000.


## 8. Conclusions

To exploit the advantages of certificate-based cryptosystems, a certificate-based PDP scheme is proposed. Based on the index logic table, our scheme can be extended to support dynamic operations easily. We prove that our scheme is secure in the standard model under the Squ-CDH assumption. Efficiency evaluation shows that our scheme is efficient.



---

*Source: 9974485-2021-09-02.xml*