# Improved Efficient Privacy-Preserving Certificateless Provable Data Possession Scheme for Cloud Storage

Authors: Xiuguang Li; Ruifeng Li; Xu An Wang; Ke Niu; Hui Li; Xiaoyuan Yang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Cloud storage technology is evolving at a high speed; effectively auditing the cloud data’s integrity has become a focal point. Recently, Ming and Shi proposed a certificateless integrity auditing scheme with a privacy protection function. The scheme used the certificateless cryptosystem to solve the certificate management problem of the auditing schemes based on public key infrastructure and the key escrow problem of the identity-based auditing schemes. Although their scheme is novel and efficient, we found that their scheme was not secure and could not achieve integrity auditing of cloud data. The malicious cloud server can generate the proof through the blocks and tags sent by the user. On the basis of the original scheme, we propose an improved auditing scheme; our new scheme is more secure and effective. In addition, for the problem of idle tags in the existing cloud data integrity auditing scheme, we propose the idea of intermediate tags and we applied the idea to the improved scheme to improve audit efficiency.


---

## Body

## 1. Introduction

Users are increasingly inclined to store data in the cloud to obtain more convenient data management services. Cloud service providers (CSP) centrally hold massive amounts of users’ data. For an attacker, a successful attack on the cloud server will gain a great deal. Therefore, it is easy for CSPs to become the targets of centralized attacks. The dishonest CSPs may also deliberately delete users’ data to reduce their own storage burden or deliberately conceal security incidents that damage data integrity to maintain their own reputation. Therefore, the cloud data integrity audit schemes are proposed to effectively solve problems [1].Motivation: We note that the existing audit schemes require users to calculate data tags corresponding to all data blocks when preprocessing data blocks and upload them to the CSP for storage. However, in the auditing process, generally few tags are used to generate the proof. Once the proof is verified, it can ensure that each data block specified by the auditor is complete and guarantee all original data’s integrity with a high confidence probability. For 1,000,000 data blocks with a size of 4 kB, assuming that the server deletes or is tampered with1% of the data blocks, the auditor only needs to audit 460 data blocks, which can be higher than 99% confidence probability [2] to judge the integrity of all the data. Therefore, most of the data tags are idle during the audit process. Suppose it is an application scenario where data blocks are frequently updated [3]; a large number of tags are calculated and stored in the cloud, but they will be updated as the data blocks are updated before they are used, resulting in larger computing and storage resources waste. To solve the idle tags problem, we propose the idea of intermediate tags. Before uploading the data, when processing the data, users only generate the key intermediate tags and then upload them to CSP. When the third-party auditor (TPA) challenges the cloud data, CSP generates complete certification tags for the challenged data block. Then they enter the normal audit process.Recently, Ming and Shi [4] proposed a certificateless auditing scheme called CLPDP that supports privacy protection. In their scheme, CSP can use tags to easily forge the proof. Even if all outsourced data are deleted by CSP, it can still give the correct proof to pass the audit. So we point out the security problem in their scheme. In addition, we find that the original scheme is one that can apply the idea of intermediate tags. Therefore, we also improved the original scheme.Our contributions are as follows:(1)
We analyze Ming and Shi’s scheme and find the security problem. CSP can forge the proof to pass the audit. Then we described the attack method in detail.(2)
We propose the idea of intermediate tags, which can reduce the computing overhead of users in audit schemes. After improving the safety of the original scheme, we use the idea of intermediate tags to promote the original scheme.(3)
We performed security analysis on the improved scheme, and we proved that the improved scheme is secure. The efficiency of the improved scheme is also analyzed and compared with that of the original scheme. The improved scheme is more efficient, which proves the applicability of intermediate tags.


## 2. Related Works

Early data integrity audit schemes required users to download all their stored data and verify the downloaded data locally. However, most users store a large amount of data, so it requires high communication, storage, and computing costs for users to download all data for verification, and users generally cannot meet such requirements. Ateniese et al. [2] formally defined the Provable Data Possession (PDP) scheme. When verifying the integrity, users divide data files into blocks, and only partial data blocks are downloaded. Finally, the integrity of all data can be verified with a very high confidence rate. This method enables users to complete the audit task without downloading complete files, reducing the huge communication cost in the process of a data integrity audit. In 2013, Wang et al. [5] introduced TPA into the data integrity audit system. Users can further reduce their own expenses by outsourcing audit tasks to TPA. At present, scholars add various functions to the basic data integrity audit scheme [2] to meet the requirements of different application scenarios.Users will inevitably need to change their data after uploading data files. Therefore, the cloud data’s content should be allowed to change dynamically. Considering the urgent need for data integrity audit schemes in the dynamic update, scholars put forward audit schemes with dynamic update functions. Dynamic data update has gradually become the basic function in cloud data integrity audit schemes, which is indispensable in the application of real scenarios. Existing data structures applied to dynamic data updates mainly include Index Switcher, Index Hash Table, Merkle Hash Tree, Skip List, Dynamic Hash Table, Red-Black Tree, etc. In the construction of a data integrity verification scheme supporting dynamic data updates, the difficulty lies in solving the problem of extra computation costs caused by index change.Jin et al. [6] constructed the mapping from the data block index to the tag index and designed the Index Switcher data structure to avoid the extra computational overhead caused by tag recalculation. In addition, the dispute arbitration function is added to the proposed audit scheme to ensure that users or the cloud will not commit improper acts during the audit process. Tian et al. [7] proposed the audit scheme supporting dynamic updates, privacy protection, and batch audit. The dynamic hash table data structure is designed to realize fast audit and efficient data updates by recording the attributes of files and data blocks at the audit ends. Shen et al. [8] proposed the whole/sampling audit method to solve the problem of distrust between users and the cloud and designed a double-linked information table to achieve efficient data update. Their scheme also supported the batch audit function. Guo et al. [9] constructed a multileaf authentication method based on the Merkle tree, which can simultaneously authenticate multiple leaf nodes and corresponding indexes and realize batch data updates. The scheme supports log auditing. By checking the log files generated by auditors, users can verify whether the auditors perform their audit work honestly. The public audit protocol designed by Hou et al. [10] supports blockless verification and batch verification. The scheme uses the chameleon authentication tree to realize the efficient and dynamic operation of outsourced data and reduces computing costs and improves the audit efficiency. Mishra et al. [11] used a binomial binary tree and indexed hash table data structure to construct an audit scheme supporting batch audit and efficient dynamic update based on BLS signature.The reliability of data is the basis of its value and benefit. After the reliability of data is solved, other problems of data such as consistency, practicality, and availability are meaningful. Multicopy storage is the most straightforward and simple way to improve reliability. CSP provides storage services at low prices. Users can use the massive storage space it provides. More and more users choose multicopy storage to obtain more availability of data. The audit schemes supporting dynamic manipulation of multiple replicas while ensuring data integrity remain to be explored and further investigated. Curtmola et al. [12] constructed the first multicopy audit scheme, in which each copy can generate a corresponding integrity proof against challenges, and storing multiple copies is more efficient than storing each copy individually. Liu et al. [13] constructed the multiple-copy audit scheme supporting data dynamic updating. The Merkle hash tree node used in their scheme contains the node level parameters, which are allocated to each data block. It is more efficient when verifying multiple replica updates. The audit scheme of Guo et al. [14] reduces the storage burden of CSP by sharing an authenticated identity tree among multiple copies. The scheme supports multicopy and batch auditing, which also reduces the computational cost. Yaling and Li [15] proposed a flexible multicopy PDP scheme based on the characteristics of a multibranch tree. Their scheme ensures the integrity and reliability of multiple copies and implements the verification of any copy and supports dynamic update operation and privacy protection.In recent years, in order to optimize audit performance and improve update efficiency, batch audit and batch update have become indispensable functions of cloud data integrity audit schemes. Qi et al. [16] applied the rank-based Merkle hash balanced tree to integrity verification and improved the dynamic update’s efficiency. Deng et al. [17] implemented batch auditing using BLS signature and rank-based Merkle hash tree.Later, scholars introduce TPA to perform a public audit on behalf of users to reduce the computation cost. However, TPAs are often not fully trusted [18], which can lead to the disclosure of users’ privacy [19]. Li et al. [20] solved the key management problem based on fuzzy identity. The scheme took the user’s biometrics as the identity and designed a corresponding audit protocol to protect the data content. Wang et al. [21] scheme uses a ring signature to calculate the metadata required for verification. The authenticator and random mask technology are used to protect data privacy; the scheme can also realize batch audits. The audit scheme of Wang et al. [22] is based on an algebraic signature and integrates forward error correction codes to enhance data possession assurance and recover data when a small number of blocks are deleted, thus significantly reducing communication complexity.With the development of blockchain technology, many scholars apply blockchain technology to cloud data integrity audits [23]. The certificateless audit scheme proposed by Zhang et al. [24] can resist malicious TPA; the scheme uses Bitcoin as the source of pseudorandom numbers to help generate challenging information. Li et al. [25] proposed a lightweight audit scheme with blockchain technology for integrity audit. In their scheme, the user and CSP are set as two mutually untrustworthy entities, and the TPA is removed. After the user stores the lightweight verification tags into the blockchain, the Merkle hash tree is constructed through the tags to generate the proof, so as to save computational power. Yang et al. [26] provided the mutual blockchain for outsourced cloud data and proposed an incentive mechanism based on credit, so that CSPs can supervise each other, which prevents collusion and realizes public audit efficiently. Yang et al. [27] proposed a certificateless multicopy and multicloud data public audit scheme based on blockchain technology. Their scheme leverages the unpredictability of blocks in the blockchain to build fair challenge information, preventing malicious auditors from colluding with CSP to deceive users. Wang et al. [28] used blockchain to replace TPAs and designed a blockchain-based fair payment smart contract for a cloud data audit. In their scheme, users and CSP will run blockchain-based smart contracts to ensure that the cloud periodically submits data to the cloud with proof of possession. Only after verification can the CSP be paid. Wei et al. [29] built a blockchain integrity protection mechanism. The scheme deploys the distributed virtual machine agent model on the cloud allowing multitenant collaboration and achieving reliable storage, monitoring, and verification tasks. Reference [30] proposed a protection model based on a private chain, which synchronously uploads modification records of files and hash values of files to blockchain for storage and judges whether the data is complete by comparing hash values.Quantum computers use qubits to represent many possible states of 1 and 0 at the same time and have more processing power than standard computers. Most cloud storage data auditing schemes are based on a traditional cryptosystem. However, with the introduction of algorithms such as quantum large number decomposition, the traditional cryptosystem loses its security. Lattice-based cryptography is generally considered to be effective against the quantum attack. Xu et al. [31] designed the first lattice-based cloud data audit scheme based on the small integer solution problem. The audit scheme designed by Liu and Cao [32] supports public verification but does not provide strict security certification. Zhang et al. [33] designed an ID-based public audit protocol based on lattice by using ID-based signature technology and further provided a solution to solve the key exposure problem [34], which protected user data’s privacy. In addition, TPA cannot obtain information about users’ data during audit verification. Sasikala and Shoba Bindu [35] designed a lattice-based certificateless public auditing protocol for the first time, but it was pointed out by [36] that the scheme had security problems.Organization: We organize our paper as follows. In Section3, we reviewed the certificateless privacy protection secure cloud storage scheme of Ming and Shi. Section 4 describes the attack against the original scheme. In Section 5, we propose the concept of intermediate tags and give an improved audit protocol. In Section 6, the security and performance of the improved scheme are analyzed to prove that it is safer and more efficient. Finally, in Section 7, we summarize our work.


## 3. Review of Ming and Shi’s Scheme

The system model of Ming and Shi is shown in Figure1, including a key generation center (KGC), a data owner (DO), CSP, a data user (DU), and TPA. Figure 1 shows their system model. To facilitate understanding, we define and explain the various symbols and variables that appear in our paper in Table 1.Figure 1
The system model.Table 1
Notations.
NotationsDescriptionsEThe elliptic curveFpThe finite fieldGThe cyclic groupPGenerator ofGH1,2,3,4Secure hash functionH·:0,1∗⟶Zq∗PpubPublic key of the systemID∈Zq∗DO’s real identityPIDDO’s virtual identityλ, u, d, ri, viRandom numbersx,yDO’s secret keyD,XDO’s public keyidiThe identifier of the data blockmimiThe data blockωj, ϕj, τIntermediate parametersRi, siThe tags ofmiQThe collection of challenged indexesα,βThe proofHThe computational cost of one hashAZThe computational cost of one addition onZq∗MZThe computational cost of one multiplication onZq∗AGThe computational cost of one point addition onGMGThe computational cost of one point multiplication onGSpecifically, the following is the operation process of the original scheme:(1)
Setup: KGC first selects the cyclic groupG on the elliptic curve E, defines the large prime number q with the order of G, and selects the generator P∈G. Then it selects the secure hash function H1,2,3,4:0,1∗⟶Zq∗, selects a random λ∈Zq∗ as the system master key, and calculates Ppub=λ⋅P∈G. Finally, KGC keeps the master key in secret and exposes the parameters.(2)
PartialKeyGen: DO sends the real identity informationID∈Zq∗ to KGC. After KGC receives ID∈Zq∗, it selects a random number u∈Zq∗ and calculates PID1=u⋅P, PID2=ID⊕H1u⋅Ppub‖PID1.Then KGC sends DO’s virtual identityPID=PID1,PID2 to DO and randomly selects d∈Zq∗.alculatesD=d⋅P, τ=H2PID‖D, y=d+λ⋅τ. Finally, KGC sends DO’s partial keys D,y to DO.(3)
SecretValueGen: DO randomly choosesx∈Zq∗ and obtains complete private key x,y.(4)
PublicKeyGen: DO calculatesX=x⋅P and obtains the complete public key D,X.(5)
TagGen: the data fileM is divided into n blocks by DO as M=m1,m2,…,mn, where mi1≤i≤n∈Zq∗. DO selects a random number ri∈Zq∗ and calculates Ri=riP, wi=H3XRiidi, ϕi=H4DRiidi, and si=ri⋅mi+wi⋅x+ϕi⋅y for i∈1,2,…,n, where idi is the identifier of mi. Thus the tags σ=R1,R2,…,Rn,s1,s2,…,sn are generated by DO; they are sent with the data blocks to CSP. DO deletes the local data and tags.(6)
Challenge: after receiving DU’s audit request, TPA generates the challenge message. It first selects a random subsetQ in 1,2,…,n. The subset Q includes c elements. For j∈Q, TPA randomly selects vj∈Zq∗; then it sends chal=j,vjj∈Q as the challenge message to CSP.(7)
ProofGen: CSP calculatesα=∑j∈Qvj⋅sj⋅P and β=∑j∈Qvj⋅mj⋅Rj after it receives chal=j,vjj∈Q; then it sends α,β as the proof to TPA.(8)
Verify: after receivingα,β, TPA calculates τ=H2PID‖D. Then it calculates ωj=H3XRjidj and ϕj=H4DRjidj for j∈Q and verifies(1)α=?β+∑j∈Qωj⋅vj⋅X+∑j∈Qϕj⋅vj⋅D+τ⋅Ppub.If equation (1) holds, DO’s data is complete.The proof of the correctness of equation (1) is as follows:(2)α=∑j∈QvjsjP=∑j∈Qvjrjmj+ωjx+ϕjyP=∑j∈QvjrjmjP+∑j∈QvjωjxP+∑j∈QvjϕjyP=∑j∈QvjmjRj+∑j∈QvjωjX+∑j∈QvjϕjD+τPpub=β+∑j∈QωjvjX+∑j∈QϕjvjD+τPpub.


## 4. Our Attack

In the scheme of Ming and Shi, we find that the CSP can calculate the value of the aggregated data blocks needed at theProofgen stage. In this way, even if the CSP deletes DO’s cloud data, the correct data possession proof can be generated by it at the Proofgen stage and passed the audit. In this section, we show two types of attacks; the process by which CSP forges the “correct” blocks is also introduced.


### 4.1. The First Type of Attack

The first attack is caused by a design error in the verification equation; the detailed description is as follows:Assume that the entities in the scenario run the audit scheme following the process described above; when the scheme progresses to the ProofGen stage, CSP needs to generate the proofα,β. We note that, in equation (1), CSP can obtain all values except α and β, so CSP just needs to randomly select α∈G; it can obtain β by calculating equation (1). Similarly, CSP can also calculate the value of α by calculating equation (1) when it randomly selects β∈G. Thus, CSP does not need to store DO’s data to generate the proof α,β that satisfies equation (1).


### 4.2. The Second Type of Attack

At the TagGen stage, the CSP receives blocks and tags. CSP first calculatessi'=si⋅P, so it gets the following equations:(3)s1′=r1m1⋅P+w1⋅X+ϕ1⋅D+τ⋅Ppub,s2′=r2m2⋅P+w2⋅X+ϕ2⋅D+τ⋅Ppub,⋮sn′=rnmn⋅P+wn⋅X+ϕn⋅D+τ⋅Ppub.X and D are DO’s public keys, CSP knows the values of X, D, and Ppub, it can also calculate the value of wi and ϕi for 1≤i≤n, and then it obtains rimi for 1≤i≤n to calculate the following equations:(4)r1m1⋅P=s1′−w1⋅X−ϕ1⋅D+τ⋅Ppub,r2m2⋅P=s2′−w2⋅X−ϕ2⋅D+τ⋅Ppub,rnmn⋅P=sn′−wn⋅X−ϕn⋅D+τ⋅Ppub.At the ProofGen stage, the CSP needs to calculate(5)β=∑j∈Qvj⋅mj⋅Rj=∑j∈Qvj⋅mjrjP.Even if CSP deletesm1,m2,…,mn, it can calculate the value of β with r1m1⋅P, r2m2⋅P…… rnmn⋅P, which can pass the audit.


## 4.1. The First Type of Attack

The first attack is caused by a design error in the verification equation; the detailed description is as follows:Assume that the entities in the scenario run the audit scheme following the process described above; when the scheme progresses to the ProofGen stage, CSP needs to generate the proofα,β. We note that, in equation (1), CSP can obtain all values except α and β, so CSP just needs to randomly select α∈G; it can obtain β by calculating equation (1). Similarly, CSP can also calculate the value of α by calculating equation (1) when it randomly selects β∈G. Thus, CSP does not need to store DO’s data to generate the proof α,β that satisfies equation (1).


## 4.2. The Second Type of Attack

At the TagGen stage, the CSP receives blocks and tags. CSP first calculatessi'=si⋅P, so it gets the following equations:(3)s1′=r1m1⋅P+w1⋅X+ϕ1⋅D+τ⋅Ppub,s2′=r2m2⋅P+w2⋅X+ϕ2⋅D+τ⋅Ppub,⋮sn′=rnmn⋅P+wn⋅X+ϕn⋅D+τ⋅Ppub.X and D are DO’s public keys, CSP knows the values of X, D, and Ppub, it can also calculate the value of wi and ϕi for 1≤i≤n, and then it obtains rimi for 1≤i≤n to calculate the following equations:(4)r1m1⋅P=s1′−w1⋅X−ϕ1⋅D+τ⋅Ppub,r2m2⋅P=s2′−w2⋅X−ϕ2⋅D+τ⋅Ppub,rnmn⋅P=sn′−wn⋅X−ϕn⋅D+τ⋅Ppub.At the ProofGen stage, the CSP needs to calculate(5)β=∑j∈Qvj⋅mj⋅Rj=∑j∈Qvj⋅mjrjP.Even if CSP deletesm1,m2,…,mn, it can calculate the value of β with r1m1⋅P, r2m2⋅P…… rnmn⋅P, which can pass the audit.


## 5. The Improved Auditing Scheme

In this section, we first explain what an intermediate tag is and how to set an intermediate tag; then we give an improved secure auditing scheme.We first analyze the probability of misbehavior detection in existing PDP schemes. Forn=1000000 4 KB data blocks, we assume that 1% of the data blocks’ integrity is damaged; TPA can specify 460 data blocks to obtain a confidence probability higher than 99%. We set n as the data blocks’ total number, c1 as damaged data blocks’ number, and c2 as randomly challenged data blocks’ number during the audit. We set a random variable X representing the number of corrupted blocks in the challenged blocks; PX represents the corresponding probability. We have the deduction as follows:(6)PX=PX≥1=1−PX=0=1−n−c1n⋅n−1−c1n−1⋯n−c2+1−c1n−c2+1.Becausen−c1/n>n−1−c1/n−1, so:(7)PX≥1−n−c1nc2.In the case ofc1/n=1%, when c2 is 300, 460, and 688, PX is greater than 95%, 99%, and 99.9%, respectively. Therefore, in an audit process, few data blocks are challenged, and the relevant tags are used to generate the proof. Most of the other data blocks and relevant tags are idle.Assuming that there are totaln=1000000 data blocks and tags stored in the cloud, 460 of them are challenged in each audit, and the challenged data blocks are different in multiple audits. Then it takes about 2173 audit times to use all the data blocks and corresponding tags. In practical applications, due to the user’s demand for data update, many idle blocks and corresponding tags are modified and updated before they can be used, resulting in a large waste of computing overhead.Therefore, we propose the idea of intermediate tags: at the TagGen stage, users only generate intermediate tags composed of the private key and data blocks, instead of calculating mature tags used by CSP when generating evidence, which reduces the calculation overhead of users. At the ProofGen stage, CSP calculates mature tags of only a few challenged data blocks according to the challenge information from the TPA and uses them to generate the proof. The idea of intermediate tags is applied to the following improved scheme:(1)
Setup: KGC first selects the cyclic groupG on the elliptic curve E, defines the large prime number q with the order of G, selects P∈G as the generator, H1,2,3,4:0,1∗⟶Zq∗ as hash functions, and a random λ∈Zq∗ as the system master key, and calculates Ppub=λ⋅P∈G. Finally, KGC keeps λ in secret and exposes the public parameters.(2)
PartialKeyGen: DO sends the real identity informationID∈Zq∗ to KGC. After KGC receives ID∈Zq∗, it selects a random number u∈Zq∗ and calculates PID1=u⋅P, PID2=ID⊕H1u⋅Ppub‖PID1. Then KGC sends DO’s virtual identity PID=PID1,PID2 to DO and randomly selects d∈Zq∗ and calculates D=d⋅P, τ=H2PID‖D, y=d+λ⋅τ. Finally, KGC sends DO’s partial keys D,y to DO.(3)
SecretValueGen: DO randomly choosesx∈Zq∗ and obtains complete private key x,y.(4)
PublicKeyGen: DO calculatesX=x⋅P and obtains the complete public key D,X.(5)
TagGen: the data fileM is divided into n blocks by DO as M=m1,m2,…,mn, where mi1≤i≤n∈Zq∗. DO randomly selects ri∈Zq∗, k∈Zq∗ and calculates Ri=riP, si=rimi+k. Note that here we have simplified the formula for calculating si, and the intermediate tag si in the improved scheme is different from the mature tag si in the original scheme. Thus the tags σ=R1,R2,…,Rn,s1,s2,…,sn are generated by DO; they are sent with the data blocks to CSP. DO sends k to TPA and deletes the local data and tags.(6)
Challenge: after receiving DU’s audit request, TPA generates the challenge message. It first selects a random subsetQ in 1,2,…,n. The subset Q includes c elements. For j∈Q, TPA randomly chooses vj∈Zq∗; then it sends chal=j,vjj∈Q to CSP as the challenge message.(7)
ProofGen: CSP calculateswj=H3XRjidj and ϕj=H4DRjidj for j∈Q after receiving chal=j,vjj∈Q. Then it calculates α=∑j∈Qvj⋅sj⋅P+wjX+ϕjY , β=∑j∈Qvj⋅mj⋅Rj as the proof and sends α,β to TPA.(8)
Verify: after receiving the proofα,β, TPA calculates τ=H2PID‖D and calculates wj=H3XRjidj, ϕj=H4DRjidj for j∈Q. Then, it verifies(8)α=?β+∑j∈QvjkP+∑j∈QwjvjX+∑j∈QϕjvjD+τPpub.If equation (8) holds, DO’s cloud data is complete.The correctness of equation (8) is as follows:(9)α=∑j∈Qvj⋅sj⋅P+wjX+ϕjD+τPpub+∑j∈QvjkP=∑j∈Qvjrj⋅mj+wjx+ϕj⋅y⋅P+∑j∈QvjkP=∑j∈QvjrjmjP+∑j∈QvjwjxP+∑j∈QvjϕjyP+∑j∈QvjkP=∑j∈QvjmjRj+∑j∈QvjwjX+∑j∈QvjϕjD+τPpub+∑j∈QvjkP=β+∑j∈QvjkP+∑j∈QwjvjX+∑j∈QϕjvjD+τPpub.


## 6. Analysis of the Improved Protocol

In this section, we first demonstrate that the improved scheme can resist the above attacks. Then the improved scheme’s performance is analyzed. We also compare the computation overhead in two schemes, so as to prove that our improved scheme is more efficient.


### 6.1. Security Analysis

CSP holds the following equations in the improved scheme:(10)s1=r1m1+k,s2=r2m2+k,⋮si=rimi+k.In equation (10), ri and k are unknown to CSP; it always has more unknowns than equations, so CSP cannot solve the equations to calculate the values of ri and k. At the ProofGen stage, CSP cannot know r1m1,r2m2,…,rnmn. When CSP uses the second of the above attacks, it can list the following equations:(11)m1⋅R1=s1⋅P+k⋅P,m2⋅R2=s2⋅P+k⋅P,⋮mi⋅Ri=si⋅P+k⋅P.Since CSP does not know the value ofk, it cannot compute the value of mi⋅Ri. When generating β=∑j∈Qvj⋅mj⋅Rj, CSP can not calculate the value of β with the tag uploaded by DO. Only when the m1,m2,…,mn are stored correctly and completely by CSP, can CSP generate the correct β and pass the TPA audit.When CSP uses the first of the above attacks, after randomly selecting one of the values ofα and β, it attempts to obtain the value of the other variable by calculating equation (1). But in equation (9), k is unknown to CSP, and CSP cannot compute β from α and equation (1) or compute α from β and equation (1).


### 6.2. Performance Analysis

The idea of intermediate tags is to save computing overhead for DO. The difference of storage and communication costs between two schemes is small, so we mainly analyze the computing costs of the two schemes.In the original scheme, at the TagGen stage, DO needs to calculateRi=riP, wj=H3XRjidj, ϕj=H4DRjidj, si=ri⋅mi+wi⋅x+ϕi⋅y, and the calculation cost is nMG+2nH+3nMZ+2nAZ. At the ProofGen stage, CSP calculates α=∑j∈Qvj⋅sj⋅P and β=∑j∈Qvj⋅mj⋅Rj, set c as the number of elements in Q, and the calculation cost is c−1AG+2cMZ+c−1AZ+cMG. At the Verify stage, TPA calculates τ=H2PID‖D, for j∈Q, calculate wj=H3XRjidj, ϕj=H4DRjidj and equation (1), the and calculation cost is 2c+1H+3AG+2cMZ+2c−2AZ+3MG.In the improved scheme, at the TagGen stage, DO only needs to calculateRi=riP, si=rimi+k, and the computational cost is nMG+nMZ+nAZ. At the ProofGen stage, CSP calculates wj=H3XRjidj, ϕj=H4DRjidj for each challenged block. Then, it calculates α=∑j∈Qvj⋅sj⋅P+wjX+ϕjD+τPpub , β=∑j∈Qvj⋅mj⋅Rj , and the calculation cost is 2cH+c−1AG+5c+1MZ+4c−4AZ+c+4MG. At the Verify stage, TPA calculates τ=H2PID‖D, calculate wj=H3XRjidj, ϕj=H4DRjidj for j∈Q, and equation (1) is also calculated. The calculation cost is 2c+1H+4AG+3c+1MZ+3c−3AZ+4MG. The computational costs of the two schemes at each stage are compared as Table 2.Table 2
The computational costs of the two schemes at each stage.
The original schemeThe improved schemeTagGennMG+2nH+3nMZ+2nAZnMG+nMZ+nAZProofGenc−1AG+2cMZ+c−1AZ+cMG2cH+c−1AG+5c+1MZ+4c−4AZ+c+4MGVerify2c+1H+3AG+2cMZ+2c−2AZ+3MG2c+1H+4AG+3c+1MZ+3c−3AZ+4MGAs we can see from Table2, in the improved scheme, DO reduces the computational overhead of 2nH+2nMZ at the TagGen phase. At the ProofGen phase, CSP needs to bear the extra computation overhead of 2cH+3c+1MZ+3c−3AZ+4MG. At the Verify phase, TPA needs to bear the extra computation overhead of AG+c+1MZ+c−1AZ+MG. Notice that the value of n is much larger than the value of c, the extra computing overhead borne by CSP and TPA is far less than the reduced computing overhead by DO, and the improved solution is more user-friendly and more efficient.


## 6.1. Security Analysis

CSP holds the following equations in the improved scheme:(10)s1=r1m1+k,s2=r2m2+k,⋮si=rimi+k.In equation (10), ri and k are unknown to CSP; it always has more unknowns than equations, so CSP cannot solve the equations to calculate the values of ri and k. At the ProofGen stage, CSP cannot know r1m1,r2m2,…,rnmn. When CSP uses the second of the above attacks, it can list the following equations:(11)m1⋅R1=s1⋅P+k⋅P,m2⋅R2=s2⋅P+k⋅P,⋮mi⋅Ri=si⋅P+k⋅P.Since CSP does not know the value ofk, it cannot compute the value of mi⋅Ri. When generating β=∑j∈Qvj⋅mj⋅Rj, CSP can not calculate the value of β with the tag uploaded by DO. Only when the m1,m2,…,mn are stored correctly and completely by CSP, can CSP generate the correct β and pass the TPA audit.When CSP uses the first of the above attacks, after randomly selecting one of the values ofα and β, it attempts to obtain the value of the other variable by calculating equation (1). But in equation (9), k is unknown to CSP, and CSP cannot compute β from α and equation (1) or compute α from β and equation (1).


## 6.2. Performance Analysis

The idea of intermediate tags is to save computing overhead for DO. The difference of storage and communication costs between two schemes is small, so we mainly analyze the computing costs of the two schemes.In the original scheme, at the TagGen stage, DO needs to calculateRi=riP, wj=H3XRjidj, ϕj=H4DRjidj, si=ri⋅mi+wi⋅x+ϕi⋅y, and the calculation cost is nMG+2nH+3nMZ+2nAZ. At the ProofGen stage, CSP calculates α=∑j∈Qvj⋅sj⋅P and β=∑j∈Qvj⋅mj⋅Rj, set c as the number of elements in Q, and the calculation cost is c−1AG+2cMZ+c−1AZ+cMG. At the Verify stage, TPA calculates τ=H2PID‖D, for j∈Q, calculate wj=H3XRjidj, ϕj=H4DRjidj and equation (1), the and calculation cost is 2c+1H+3AG+2cMZ+2c−2AZ+3MG.In the improved scheme, at the TagGen stage, DO only needs to calculateRi=riP, si=rimi+k, and the computational cost is nMG+nMZ+nAZ. At the ProofGen stage, CSP calculates wj=H3XRjidj, ϕj=H4DRjidj for each challenged block. Then, it calculates α=∑j∈Qvj⋅sj⋅P+wjX+ϕjD+τPpub , β=∑j∈Qvj⋅mj⋅Rj , and the calculation cost is 2cH+c−1AG+5c+1MZ+4c−4AZ+c+4MG. At the Verify stage, TPA calculates τ=H2PID‖D, calculate wj=H3XRjidj, ϕj=H4DRjidj for j∈Q, and equation (1) is also calculated. The calculation cost is 2c+1H+4AG+3c+1MZ+3c−3AZ+4MG. The computational costs of the two schemes at each stage are compared as Table 2.Table 2
The computational costs of the two schemes at each stage.
The original schemeThe improved schemeTagGennMG+2nH+3nMZ+2nAZnMG+nMZ+nAZProofGenc−1AG+2cMZ+c−1AZ+cMG2cH+c−1AG+5c+1MZ+4c−4AZ+c+4MGVerify2c+1H+3AG+2cMZ+2c−2AZ+3MG2c+1H+4AG+3c+1MZ+3c−3AZ+4MGAs we can see from Table2, in the improved scheme, DO reduces the computational overhead of 2nH+2nMZ at the TagGen phase. At the ProofGen phase, CSP needs to bear the extra computation overhead of 2cH+3c+1MZ+3c−3AZ+4MG. At the Verify phase, TPA needs to bear the extra computation overhead of AG+c+1MZ+c−1AZ+MG. Notice that the value of n is much larger than the value of c, the extra computing overhead borne by CSP and TPA is far less than the reduced computing overhead by DO, and the improved solution is more user-friendly and more efficient.


## 7. Conclusion

In this paper, we point out that Ming and Shi’s scheme is insecure. The aggregated data blocks required for the audit are easy to forge. CSP can provide the correct integrity proof after modifying or deleting the data, and TPA will give the correct integrity audit results. In addition, to solve the idle tags problem in the existing audit schemes, we propose the idea of intermediate tags, which can save computing power for users. Finally, we apply the idea to the improved scheme and upgrade the original scheme on security to solve the security problems of the Ming and Shi’s scheme and improve the audit efficiency. We hope that our idea of intermediate tags can be used by more scholars to construct more efficient audit solutions and the security issue pointed by us can be avoided when they design the scheme.



---

*Source: 7302767-2022-08-30.xml*