# Privacy-Preserving Outsourced Auditing Scheme for Dynamic Data Storage in Cloud

Authors: Tengfei Tu; Lu Rao; Hua Zhang; Qiaoyan Wen; Jia Xiao
Journal: Security and Communication Networks
 (2017)

---

## Abstract

As information technology develops, cloud storage has been widely accepted for keeping volumes of data. Remote data auditing scheme enables cloud user to confirm the integrity of her outsourced file via the auditing against cloud storage, without downloading the file from cloud. In view of the significant computational cost caused by the auditing process, outsourced auditing model is proposed to make user outsource the heavy auditing task to third party auditor (TPA). Although the first outsourced auditing scheme can protect against the malicious TPA, this scheme enables TPA to have read access right over user’s outsourced data, which is a potential risk for user data privacy. In this paper, we introduce the notion of User Focus for outsourced auditing, which emphasizes the idea that lets user dominate her own data. Based on User Focus, our proposed scheme not only can prevent user’s data from leaking to TPA without depending on data encryption but also can avoid the use of additional independent random source that is very difficult to meet in practice. We also describe how to make our scheme support dynamic updates. According to the security analysis and experimental evaluations, our proposed scheme is provably secure and significantly efficient.


---

## Body

## 1. Introduction

In recent years, cloud computing has triggered profound technology changes in the field of information industry, promoting the rapid development of IoT (Internet of things) and big data that have gained so much attention in our daily social and economic activities [1]. As one of the vital services of cloud computing, cloud storage offers many attractive advantages, including the location-independent resources, ubiquitous network access, and on-demand storage space [2], motivating more and more enterprises and individuals to outsource their own data to cloud. Benefiting from the big data that is gathered together into the cloud, all kinds of data-driven techniques, such as data mining [3, 4] and data signal processing [5, 6], can be deployed upon the cloud storage environment to play their effective roles for creating more information wealth.Despite that fact that many potential gains can be achieved based on the cloud storage, there also exists new threats from the cloud user’s point of view. After user uploads all of her own data to cloud, one of the most pressing issues for user is how to verify the integrity of outsourced data stored at remote cloud side. Note that user loses the physical possession over her data in the context of data outsourcing, so it is clearly not feasible to directly apply traditional local data verification techniques that require access to the entire data, since both user and cloud servers cannot afford the heavy communication cost of frequently transferring all the outsourced data across a network to perform the data integrity verification. In this case, a variety of remote data auditing schemes [7–23] are designed, which can support the periodic integrity verifications upon outsourced data and simultaneously avoid transferring all these data for the minimum communication overhead. In addition, as an important feature to further reduce the burden on the user, public auditing is first proposed by Ateniese et al. [7] and has been adopted extensively by the subsequent improved schemes [13–22], which enables a third party auditor (TPA) to audit cloud servers on behalf of user for ensuring the outsourced data integrity. Nonetheless, happiness will not come so easily. When TPA is introduced, the following security risk arises.Malicious TPA. TPA is considered as a trusted (or semitrusted, i.e., honest but curious) entity who cannot violate the auditing protocols in existing public auditing schemes [13–22]. But actually TPA might be untrusted [23]. Obviously, if the irresponsible TPA is lazy and does nothing, there is no difference between entrusting a malicious TPA and casting away all prior public auditing schemes for user.In order to protect against the above malicious TPA, Armknecht et al. [23] first presented the outsourced auditing scheme Fortress to achieve this goal. Meanwhile, Fortress can protect the honest TPA from a malicious user, which is also a potential security issue that has not been considered in existing public auditing models. However, during the data preprocessing step, Fortress enables TPA to have read access right over the whole user’s outsourced data in cloud, which is a significant limitation for practical applications. On the one hand, since Fortress exposes all outsourced data to TPA, in Fortress the only way for data privacy protection against curious TPA is to encrypt user’s files before outsourcing. Nevertheless, as shown in [13, 14], although data encryption alone is an approach to relieve the privacy concern in cloud storage, encryption itself is often not enough to prevent user’s data from leaking to TPA during the auditing process. On the other hand, in the era of big data, user’s outsourced data is one kind of core business assets of CSP [15], which means the wealth and the future for CSP. Thus, CSP is selfish and has no incentives to reveal user’s outsourced data to TPA under any circumstance. Besides, user is also often reluctant to expose her data to a third party [24]. In this case, for the various online cloud storage applications (e.g., online videos) where user cannot encrypt her data prior to outsourcing and only resorts to CSP to protect against outsourced data leakage, it is clearly that the direct extension of Fortress upon these online applications is impractical, since the design of revealing outsourced data to TPA is inevitable in Fortress. Therefore, it is necessary for an outsourced auditing scheme to include the privacy-preserving mechanism that is independent of data encryption to defend against curious TPA.Furthermore, Fortress argues that the challenges for auditing cannot depend on any of the involved three entities since they might be malicious. So Fortress requires the aid of additional independent random source to produce the secure challenges for protecting against any malicious entity. However, as shown in [25], under the environment of cloud storage, the requirement of additional independent servers is already a strong assumption that is very difficult to meet in commercial contexts, and thus the similar assumption of requiring additional independent random source in Fortress is the same situation.To address the above problems, in this paper, we introduce for outsourced auditing model a novel notion User Focus, which emphasizes the idea of restoring user’s data autonomy lost in cloud storage setting. As shown in Sections2.2 and 2.3, User Focus means to let user control all challenges throughout the process of outsourced auditing, avoiding the limitation of introducing the additional bitcoin pseudo-random source for generating challenges as in existing Fortress scheme. Furthermore, the user’s autonomy enabled by User Focus is also reflected in that the data only needs to be preprocessed by user herself, avoiding the unfavorable situation in Fortress that TPA must fetch all user’s data from cloud for initialization. With introducing User Focus, we propose an efficient and secure outsourced auditing scheme, which not only can defend against any malicious entity but also can protect user’s outsourced data from curious TPA without depending on data encryption. In general, the contributions of this paper can be summarized as follows.(
1
) By empowering user to play the leading role, we propose a formal User Focus outsourced auditing model along with the security definitions, which do not depend on any additional pseudo-random source. Our model extends the model of Fortress and takes into account the problem of preserving user’s data privacy when introducing TPA, which is not covered in Fortress.(
2
) Based on our proposed model, we design a concrete User Focus outsourced auditing scheme, the security of which is analyzed. Although the notion of User Focus empowers user to generate the challenges, it does not mean that a malicious user can do whatever she wants to do, since our scheme can also defend against the malicious user. In addition, under the environment of outsourced auditing, our scheme can enable user to predefine enough challenges for avoiding keeping user online all the time and also support the dynamic data updates by relying on the MHT authenticated data structure.(
3
) Our scheme applies the RSA public key cryptography rather than the symmetric cryptography technology as utilized in Fortress and thus enables TPA to complete his preparatory work for auditing without requiring access to user’s outsourced data at cloud side, which solves the significant performance problem faced by Fortress. We evaluate the run time of our scheme through concrete implementation when compared to Fortress. The evaluation results show that our solution is promising according to the improved performance.The rest of this paper is organized as follows: Section2 introduces the notion of User Focus and extends the outsourced auditing model along with the security definitions. In Section 3, we propose the User Focus outsourced auditing scheme, followed by the security analysis. In Section 4, the concrete algorithms for supporting dynamic updates are described. Section 5 gives the implementation results with the performance evaluation. Section 6 overviews the related work. Finally, Section 7 gives the concluding remark of this paper.


## 2. Problem Statement

In this section, we introduce the notion of User Focus, which should be an important requirement for user in the setting of storage outsourcing. Then we propose a formal User Focus outsourced auditing model and the corresponding security definitions.


### 2.1. Outsourced Auditing for Cloud Storage

Various remote data auditing schemes [7–23] provide a cloud user the ability of confirming that her outsourced data is intact at the cloud, with the advantage that it is no need to fetch the data from cloud. The private auditing schemes [8, 12] only include two entities: a user and CSP, where user has to audit CSP regularly by herself to ascertain that CSP holds the stored data all the time. In view of user’s limited resources and the expensive computation cost incurred by the frequent audits, the public auditing schemes are proposed [13–22], which introduce a trusted TPA to perform the above auditing task. By employing TPA, user is alleviated from the auditing burden. However, trusted TPA is just an ideal hypothesis in real world.Based on the prior auditing solutions, the first outsourced auditing scheme [23] is proposed to defend against the malicious TPA. Compared with the public auditing model, although there are also three entities included in outsourced auditing setting, the major difference is that anyone of the three entities might be dishonest, as described as follows:(i)
User might be a dishonest entity, who uploads her data to the cloud servers. User needs to remotely update outsourced data as necessary. And user might maliciously deny the fact that the auditing work performed by TPA against CSP is correct for claiming compensations from TPA.(ii)
CSP might be a dishonest entity, who is the owner of cloud servers (so CSP and the cloud servers are not distinguished in our paper), holding a large amount of resources to store and maintain outsourced data. CSP might try to cheat on auditor when data loss or data corruption occurs in cloud.(iii)
TPA might be a dishonest entity, who has capabilities and expertise, on behalf of user, to regularly audit CSP for confirming the intactness of user’s data in cloud. But TPA might be lazy and fail to perform the auditing task required by user. In addition, TPA might be curious and try to deduce user’s outsourced data during performing his auditing task against CSP.


### 2.2. User Focus

“Customer Focus” is a marketing term that means keeping customer in mind and bringing customer the good experience of services. Clearly, “The customer is a God” is not only the truth in business, but also a similar situation in our cloud storage environment, where the user is the targeted customer of CSP and all kinds of auditing solutions. User experience is a determining factor signifying whether an auditing scheme is accepted or not in practice. If user experience of a scheme is poor, no matter whatever sophisticated technology is adopted, it is impossible for this scheme to get a practical application widely.In spite of various auditing schemes that are proposed to cover many critical issues, but user experience is ignored. On the one hand, whichever of the private auditing schemes is based on the design that the auditing protocol needs to be frequently executed by user, resulting in the nonnegligible computation overhead at user side. Obviously, this is a terrible experience for user who just holds limited resources, such as smartphone. On the other hand, within public auditing schemes, the assumption of a “trusted” TPA is also a bad experience for user, since it is impractical for every ordinary user to find an idealistic “trusted” TPA.Note that the purpose of remote data auditing is to provide user with a mechanism for confirming the security of her outsourced data. Here, user is regarded as the demander. Therefore, user ought to be put at the center when designing the auditing scheme, and her experience should not be ignored. For this reason, we introduce the notion ofUser Focus, which is defined as follows:User is the initiator of the auditing protocols and controls all the challenges, who can timely receive the exception message of her outsourced data without frequently working, since both CSP and TPA have to frequently provide all proofs around user’s needs.We stress that User Focus does not mean a malicious user can do whatever she wants. As shown in Section3.2.5, although user controls all the challenges, our scheme can still ensure the security for honest TPA to defend against the malicious user.Actually, the essential concept of cloud services is the centralized management of user’s data in cloud, which casts a psychological shadow on user. To save the storage space or availably access data without restriction of time and location, user is required to outsource her data to cloud, which means that user is no longer able to physically possess all her data. In other words, data outsourcing makes user lose the physical ownership and autonomy of her data, which is one of the main obstacles for the application and promotion of cloud storage.When outsourcing data to cloud is inevitable, the notion of User Focus can make user step out of the psychological shadow brought by cloud storage, enabling user to enjoy cloud services more confidently. User Focus expresses the idea that let user dominate her own data, which is realized in our model by the way that “the gain offsets the loss.” By empowering user to gain the control right of challenges, user gets back the autonomy that is lost after data outsourcing and is able to proactively check the intactness of the specific data just by adjusting challenges, which can bring user the feeling that there is really no difference for intactness assurance between her data stored in local disks and outsourced in cloud, since everything is under control from the user’s perspective. Apparently, User Focus will be an attractive property for user. Especially when our proposed scheme is implemented as a cloud service and CSP hopes that this service can be broadly accepted by potential customers, User Focus will be a fascinating feature to persuade every customer to try this cloud service.


### 2.3. User Focus Outsourced Auditing Model

Now, we begin with the description of User Focus outsourced auditing model, as shown in Figure1. To avoid the considerable user online direct interactions during the frequent TPA’s auditing against CSP, user will pregenerate enough challenges which can support running the auditing protocol for ages. Since the size of a challenge can be very small (e.g., only 88 bytes for a challenge as shown in Section 5), all these pregenerated challenges can be stored in user’s email box (e.g., only 8.5 MB email box memory is required for storing 100,000 pregenerated challenges). In this case, after user uploads her data to cloud and delegates the auditing work to TPA, based on the built-in timer of email box, each challenge will be periodically issued from user’s email box to automatically trigger TPA’s auditing against CSP without involving user herself. Furthermore, TPA must produce the corresponding log when he finishes each auditing against CSP. Based on the contract established by three entities, TPA has to immediately inform user (e.g., gives user a phone call) as soon as any exceptional situation about user’s outsourced data is detected. If TPA is lazy and hence does not find out the data corruption happening upon the challenged data blocks, once user launches her auditing to TPA by checking TPA’s logs, the lazy TPA will be identified with deterministic evidence. Finally, when all the pregenerated challenges are exhausted, user will add the new challenges to her email box. However, note that such operation for adding challenges and the auditing against TPA’s logs are only rarely executed by user, so user can go offline most of the time throughout our model.Figure 1
User Focus outsourced auditing architecture.In contrast to existing outsourced auditing model of [23], one major difference in our model is that the notion of User Focus is introduced, enabling user to play the leading role on her outsourced data with minimal effort. So user is the only one who can possess the additional secret key, besides a signing key pair, to preprocess the data. Based on the modern legal society with the spirit of contract, our model can achieve that not any honest entity will be wronged and that any malicious entity can be captured. More specifically, User Focus outsourced auditing model consists of five protocolsSetup,Preproccess,AuditCSP,AuditTPA, andIdentifyMalice, which are described as follows.(1) The Setup Protocol.For each involved entity, this randomized protocol produces a public-private key pair used for signing subsequently. For simplicity, we always imply that every entity uses as inputs its own private key and the public keys of the other entities. Moreover, user randomly generates the secret key SKTag, which will be used to preprocess the data before uploading it to cloud servers.(2) The Preproccess Protocol.This randomized protocol, launched by user, takes as input user’s secret key SKTag and a file F owned by user. The output F~∶=F,Ψ,τ marks the outsourced data that will be uploaded to CSP. Observe that F~ should include not only the file F, but also some metadata Ψ,τ. The role of metadata is reflected in three aspects which (i) enables TPA to frequently verify the response from CSP, (ii) prevents TPA from deducing any data information of the file F for privacy-preserving, and (iii) enables user to effectively audit the log files produced by TPA about his past auditing work. Formally, the following holds: (1)Preproccess:User:SKTag,F⟶User:F~.Furthermore, three entities need to agree on the financial contract that defines their respective liabilities and liquidated damage, as well as the system parameters setΓ that will be used throughout the outsourced auditing scheme. Let AgreeE1,E2,D denote that both entities E1 and E2 establish agreement on the data D. Then the contract consists of three agreements as follows. Formally,(2)Preproccess:ContractUser,CSP,TPA⟶AgreeUser,CSP,F~,Γ;AgreeCSP,TPA,Ψ,Γ;AgreeUser,TPA,Ψ,Γ.If all the above agreements succeed, thePreproccessprotocol runs to completion, meaning that F~ is outsourced and the contract is established by three entities. At last, user deletes F~ from local.(3) The AuditCSP Protocol. This protocol is launched by a challenge C, which is generated from user and sent to both CSP and TPA with user’s signature. After receiving C, CSP takes F~ as input and TPA takes Ψ,Γ as input, running this protocol, respectively. At the end, TPA must produce a binary value DTPA that expresses whether CSP’s running results pass his audit or not. If DTPA=NO, TPA must immediately report this exception to user. In addition, the auditing log⁡Θ corresponding to DTPA must be generated by TPA for each challenge. Formally, the following holds:(3)AuditCSP:User:C;CSP:F~;TPA:Ψ,Γ⟶TPA:DTPA,Θ.IfDTPA=YES, indicating that CSP passes TPA’s audit for the current challenge, so user will not receive the emergency report from TPA. Then after a certain time interval, thisAuditCSP protocol will be repeated again by a new challenge.(4) The AuditTPA Protocol.As long as user wants to check if TPA correctly executesAuditCSPprotocol for all past challenges, theAuditTPAprotocol can be launched by user. This protocol is a deterministic algorithm with one-time process, which takes as input user’s secret key SKTag, the metadata Ψ, and the log files Θ stored by TPA. The output for user is a binary value DUser that is either YES or NO. DUser=YES indicates thatTPA is honest. Otherwise,TPA is malicious. Formally,(4)AuditTPA:User:SKTag;TPA:Ψ,Θ⟶DUser.In practice,AuditTPA will be executed much less frequently. If TPA is lazy when data loss occurs, once user executesAuditTPA, the output DUser must be NO, which can be taken as evidence for user to claim compensations from TPA based on their financial contract. SinceAuditTPA can be launched without requiring the real-time output, user has enough time to execute this protocol. To avoid the breach of contract and financial penalties, TPA has to be honest all the time.(5) The IdentifyMalice Protocol.If all entities are honest, this protocol is not necessary. This protocol will not be invoked until any dishonest entity exists.IdentifyMalice is a deterministic algorithm that models the scenario of “forensic debate.” Variousproofs about all the malicious activities can be produced during the operations of previous protocols in our model. As a way for the honest entity to claim compensations or prove its innocence, all theproofs will be presented with nonrepudiation and taken as input by the lastIdentifyMalice.(5)IdentifyMalice:entity:proofs⟶Dent.The outputDent is a binary value either YES or NO, indicating whether the entity is honest or malicious. Obviously, the existing ofIdentifyMalicewill provide deterrence against all the possible misconducts. Since any malicious activity is bound to be identified, to avoid the financial penalties or even the legal liability, every involved entity has to be honest.


### 2.4. Security Definitions

For security, a User Focus outsourced auditing scheme should be correct and sound, simultaneously, supporting privacy protection against a curious TPA. The definitions are explained as below.Definition 1.
The correctness of User Focus outsourced auditing scheme requires that if all the involved entities are honest, for all keys output bySetupprotocol and for all files F∈0,1∗ and the corresponding F~ output byPreproccess protocol, TPA always accepts probability 1 at the end of eachAuditCSPprotocol run and likewise the user at the end of eachAuditTPAprotocol. In addition, the correctness can be defined from another aspect thatIdentifyMaliceprotocol will never (i.e., with probability 0) be invoked, since if everything goes well then none of the entities will abort for invoking the last protocol.To define the soundness of our model, we start by the notion of liability in [23]. In contrast to the traditional public auditing security models, providing security to TPA is also an important aspect that should not be ignored in outsourced auditing setting. Especially in situations where some problems occur (e.g., the outsourced data has been lost in CSP), TPA must not be blamed as long as he can prove that he has fulfilled the auditing obligation according to the protocols. Namely, by providing his log files, if TPA convinces user with a high probability that he is taking over guarantees about the service quality of user’s outsourced data, then TPA is actually honest to finish his auditing task for each past challenge against CSP. This is the definition of liability which is formalized in [23]. Although the security model of [23] splits the definition of soundness into two parts, extractability and liability, we stress that the soundness of our User Focus outsourced auditing model can be defined as a whole, since liability becomes an intrinsic property and implicitly exists in our model without having to be proved for each instantiation.More precisely, as shown in Section2.3, throughout theAuditCSP protocol, TPA does not use any secret key when he performs his auditing work, which means that all operations conducted by TPA are deterministic inAuditCSP protocol. Firstly, the metadata Ψ and the public parameters set Γ are confirmed by the contract afterPreproccessprotocol is over. Secondly, the challenge C is individually generated by user, which is incontestable for user because of her signature. Therefore, TPA has no influence on all the involved parameters that are applied to complete his auditing work. TheIdentifyMaliceprotocol can reconstruct the results that should have occurred for TPA during each execution ofAuditCSP protocol and compare these results with TPA’s logs to judge if TPA is lazy or not. Clearly, these results are destined to be the objective and incontestable proofs once theAuditCSP protocol is executed. For this reason, no matter whether any malicious entity exists, a User Focus outsourced auditing scheme is bound to produce the objective proofs to protect a honest TPA who correctly performs his work, while guaranteeing that any lazy TPA can be identified as long as TPA’s logs do not conform to the objective proofs as above.In conclusion, our model is naturally sound for TPA in the case that TPA is honest, since honest TPA has been implicitly protected from the malicious user. So in the following we can define the soundness for User Focus outsourced auditing scheme by excluding the situation that user is corrupted.Now, we start by using the similar game employed in [23]. Firstly, given an adversary A who corrupts any entity E∈CSP,TPA. Subsequently, the adversary A takes over the role of corrupted entity E and plays the training game with an environment as follows:(1)
By running theSetupprotocol, the environment generates all the public-private keys for the involved entities and the secret key for user. The adversary A obtains all the keys of the corrupted entity E.(2)
For learning the knowledge of various outputs provided to the corrupted entityE, adversary A adaptively interacts with the environment, which plays the role of the honest entity. Given any file F, A can request the execution ofPreproccess protocol which outputs the outsourced data F~. Afterwards, A can request the executions ofAuditCSP andAuditTPAprotocols upon any above F~ stored in cloud. All these protocol executions can be arbitrarily interleaved with each other.(3)
Finally, after finishing all the learning, adversaryA outputs a challenge file F that should be stored and the description of a cheating prover CP corresponding to this file F.The cheating proverCP is ε-admissible if the probability that the honest entity interacts with CP without aborting the protocols is at least ε. Here, the probability is over the coins of the honest and malicious entities. To formalize the definition of soundness, we adopt the notion ofextractoralgorithm EA(·), which takes as inputs all the information provided to the honest entity, and the description of the cheating prover CP. The output of EA(·) is the file F. In particular, EA(·) is given non-black-box access to the cheating prover CP and can rewind it. Formally we have the following.Definition 2.
A User Focus outsourced auditing scheme isε-sound with respect to any corrupted entity E∈CSP,TPA if there exists an extractor algorithm EA(·) such that, for any honest entity establishing the contract on a file F~=F,Ψ,τ and interacting with the ε-admissible cheating prover CP, if the whole system remains running without being aborted by honest entity, the extractor can recover F from CP with overwhelming probability.Based on the above definition, we can informally say that if theε-admissible prover CP convinces the honest entity with a sufficient level of probability, then the challenged data is actually intact and extractable.Moreover, since the user is often reluctant to reveal her outsourced data to TPA, privacy protection is necessary, as defined in the following.Definition 3.
A User Focus outsourced auditing scheme with privacy-preserving requires that no matter what running results are obtained by TPA during the operation of this scheme, TPA cannot deduce any privacy information of user’s outsourced fileF—except possibly with negligible probability.


## 2.1. Outsourced Auditing for Cloud Storage

Various remote data auditing schemes [7–23] provide a cloud user the ability of confirming that her outsourced data is intact at the cloud, with the advantage that it is no need to fetch the data from cloud. The private auditing schemes [8, 12] only include two entities: a user and CSP, where user has to audit CSP regularly by herself to ascertain that CSP holds the stored data all the time. In view of user’s limited resources and the expensive computation cost incurred by the frequent audits, the public auditing schemes are proposed [13–22], which introduce a trusted TPA to perform the above auditing task. By employing TPA, user is alleviated from the auditing burden. However, trusted TPA is just an ideal hypothesis in real world.Based on the prior auditing solutions, the first outsourced auditing scheme [23] is proposed to defend against the malicious TPA. Compared with the public auditing model, although there are also three entities included in outsourced auditing setting, the major difference is that anyone of the three entities might be dishonest, as described as follows:(i)
User might be a dishonest entity, who uploads her data to the cloud servers. User needs to remotely update outsourced data as necessary. And user might maliciously deny the fact that the auditing work performed by TPA against CSP is correct for claiming compensations from TPA.(ii)
CSP might be a dishonest entity, who is the owner of cloud servers (so CSP and the cloud servers are not distinguished in our paper), holding a large amount of resources to store and maintain outsourced data. CSP might try to cheat on auditor when data loss or data corruption occurs in cloud.(iii)
TPA might be a dishonest entity, who has capabilities and expertise, on behalf of user, to regularly audit CSP for confirming the intactness of user’s data in cloud. But TPA might be lazy and fail to perform the auditing task required by user. In addition, TPA might be curious and try to deduce user’s outsourced data during performing his auditing task against CSP.


## 2.2. User Focus

“Customer Focus” is a marketing term that means keeping customer in mind and bringing customer the good experience of services. Clearly, “The customer is a God” is not only the truth in business, but also a similar situation in our cloud storage environment, where the user is the targeted customer of CSP and all kinds of auditing solutions. User experience is a determining factor signifying whether an auditing scheme is accepted or not in practice. If user experience of a scheme is poor, no matter whatever sophisticated technology is adopted, it is impossible for this scheme to get a practical application widely.In spite of various auditing schemes that are proposed to cover many critical issues, but user experience is ignored. On the one hand, whichever of the private auditing schemes is based on the design that the auditing protocol needs to be frequently executed by user, resulting in the nonnegligible computation overhead at user side. Obviously, this is a terrible experience for user who just holds limited resources, such as smartphone. On the other hand, within public auditing schemes, the assumption of a “trusted” TPA is also a bad experience for user, since it is impractical for every ordinary user to find an idealistic “trusted” TPA.Note that the purpose of remote data auditing is to provide user with a mechanism for confirming the security of her outsourced data. Here, user is regarded as the demander. Therefore, user ought to be put at the center when designing the auditing scheme, and her experience should not be ignored. For this reason, we introduce the notion ofUser Focus, which is defined as follows:User is the initiator of the auditing protocols and controls all the challenges, who can timely receive the exception message of her outsourced data without frequently working, since both CSP and TPA have to frequently provide all proofs around user’s needs.We stress that User Focus does not mean a malicious user can do whatever she wants. As shown in Section3.2.5, although user controls all the challenges, our scheme can still ensure the security for honest TPA to defend against the malicious user.Actually, the essential concept of cloud services is the centralized management of user’s data in cloud, which casts a psychological shadow on user. To save the storage space or availably access data without restriction of time and location, user is required to outsource her data to cloud, which means that user is no longer able to physically possess all her data. In other words, data outsourcing makes user lose the physical ownership and autonomy of her data, which is one of the main obstacles for the application and promotion of cloud storage.When outsourcing data to cloud is inevitable, the notion of User Focus can make user step out of the psychological shadow brought by cloud storage, enabling user to enjoy cloud services more confidently. User Focus expresses the idea that let user dominate her own data, which is realized in our model by the way that “the gain offsets the loss.” By empowering user to gain the control right of challenges, user gets back the autonomy that is lost after data outsourcing and is able to proactively check the intactness of the specific data just by adjusting challenges, which can bring user the feeling that there is really no difference for intactness assurance between her data stored in local disks and outsourced in cloud, since everything is under control from the user’s perspective. Apparently, User Focus will be an attractive property for user. Especially when our proposed scheme is implemented as a cloud service and CSP hopes that this service can be broadly accepted by potential customers, User Focus will be a fascinating feature to persuade every customer to try this cloud service.


## 2.3. User Focus Outsourced Auditing Model

Now, we begin with the description of User Focus outsourced auditing model, as shown in Figure1. To avoid the considerable user online direct interactions during the frequent TPA’s auditing against CSP, user will pregenerate enough challenges which can support running the auditing protocol for ages. Since the size of a challenge can be very small (e.g., only 88 bytes for a challenge as shown in Section 5), all these pregenerated challenges can be stored in user’s email box (e.g., only 8.5 MB email box memory is required for storing 100,000 pregenerated challenges). In this case, after user uploads her data to cloud and delegates the auditing work to TPA, based on the built-in timer of email box, each challenge will be periodically issued from user’s email box to automatically trigger TPA’s auditing against CSP without involving user herself. Furthermore, TPA must produce the corresponding log when he finishes each auditing against CSP. Based on the contract established by three entities, TPA has to immediately inform user (e.g., gives user a phone call) as soon as any exceptional situation about user’s outsourced data is detected. If TPA is lazy and hence does not find out the data corruption happening upon the challenged data blocks, once user launches her auditing to TPA by checking TPA’s logs, the lazy TPA will be identified with deterministic evidence. Finally, when all the pregenerated challenges are exhausted, user will add the new challenges to her email box. However, note that such operation for adding challenges and the auditing against TPA’s logs are only rarely executed by user, so user can go offline most of the time throughout our model.Figure 1
User Focus outsourced auditing architecture.In contrast to existing outsourced auditing model of [23], one major difference in our model is that the notion of User Focus is introduced, enabling user to play the leading role on her outsourced data with minimal effort. So user is the only one who can possess the additional secret key, besides a signing key pair, to preprocess the data. Based on the modern legal society with the spirit of contract, our model can achieve that not any honest entity will be wronged and that any malicious entity can be captured. More specifically, User Focus outsourced auditing model consists of five protocolsSetup,Preproccess,AuditCSP,AuditTPA, andIdentifyMalice, which are described as follows.(1) The Setup Protocol.For each involved entity, this randomized protocol produces a public-private key pair used for signing subsequently. For simplicity, we always imply that every entity uses as inputs its own private key and the public keys of the other entities. Moreover, user randomly generates the secret key SKTag, which will be used to preprocess the data before uploading it to cloud servers.(2) The Preproccess Protocol.This randomized protocol, launched by user, takes as input user’s secret key SKTag and a file F owned by user. The output F~∶=F,Ψ,τ marks the outsourced data that will be uploaded to CSP. Observe that F~ should include not only the file F, but also some metadata Ψ,τ. The role of metadata is reflected in three aspects which (i) enables TPA to frequently verify the response from CSP, (ii) prevents TPA from deducing any data information of the file F for privacy-preserving, and (iii) enables user to effectively audit the log files produced by TPA about his past auditing work. Formally, the following holds: (1)Preproccess:User:SKTag,F⟶User:F~.Furthermore, three entities need to agree on the financial contract that defines their respective liabilities and liquidated damage, as well as the system parameters setΓ that will be used throughout the outsourced auditing scheme. Let AgreeE1,E2,D denote that both entities E1 and E2 establish agreement on the data D. Then the contract consists of three agreements as follows. Formally,(2)Preproccess:ContractUser,CSP,TPA⟶AgreeUser,CSP,F~,Γ;AgreeCSP,TPA,Ψ,Γ;AgreeUser,TPA,Ψ,Γ.If all the above agreements succeed, thePreproccessprotocol runs to completion, meaning that F~ is outsourced and the contract is established by three entities. At last, user deletes F~ from local.(3) The AuditCSP Protocol. This protocol is launched by a challenge C, which is generated from user and sent to both CSP and TPA with user’s signature. After receiving C, CSP takes F~ as input and TPA takes Ψ,Γ as input, running this protocol, respectively. At the end, TPA must produce a binary value DTPA that expresses whether CSP’s running results pass his audit or not. If DTPA=NO, TPA must immediately report this exception to user. In addition, the auditing log⁡Θ corresponding to DTPA must be generated by TPA for each challenge. Formally, the following holds:(3)AuditCSP:User:C;CSP:F~;TPA:Ψ,Γ⟶TPA:DTPA,Θ.IfDTPA=YES, indicating that CSP passes TPA’s audit for the current challenge, so user will not receive the emergency report from TPA. Then after a certain time interval, thisAuditCSP protocol will be repeated again by a new challenge.(4) The AuditTPA Protocol.As long as user wants to check if TPA correctly executesAuditCSPprotocol for all past challenges, theAuditTPAprotocol can be launched by user. This protocol is a deterministic algorithm with one-time process, which takes as input user’s secret key SKTag, the metadata Ψ, and the log files Θ stored by TPA. The output for user is a binary value DUser that is either YES or NO. DUser=YES indicates thatTPA is honest. Otherwise,TPA is malicious. Formally,(4)AuditTPA:User:SKTag;TPA:Ψ,Θ⟶DUser.In practice,AuditTPA will be executed much less frequently. If TPA is lazy when data loss occurs, once user executesAuditTPA, the output DUser must be NO, which can be taken as evidence for user to claim compensations from TPA based on their financial contract. SinceAuditTPA can be launched without requiring the real-time output, user has enough time to execute this protocol. To avoid the breach of contract and financial penalties, TPA has to be honest all the time.(5) The IdentifyMalice Protocol.If all entities are honest, this protocol is not necessary. This protocol will not be invoked until any dishonest entity exists.IdentifyMalice is a deterministic algorithm that models the scenario of “forensic debate.” Variousproofs about all the malicious activities can be produced during the operations of previous protocols in our model. As a way for the honest entity to claim compensations or prove its innocence, all theproofs will be presented with nonrepudiation and taken as input by the lastIdentifyMalice.(5)IdentifyMalice:entity:proofs⟶Dent.The outputDent is a binary value either YES or NO, indicating whether the entity is honest or malicious. Obviously, the existing ofIdentifyMalicewill provide deterrence against all the possible misconducts. Since any malicious activity is bound to be identified, to avoid the financial penalties or even the legal liability, every involved entity has to be honest.


## 2.4. Security Definitions

For security, a User Focus outsourced auditing scheme should be correct and sound, simultaneously, supporting privacy protection against a curious TPA. The definitions are explained as below.Definition 1.
The correctness of User Focus outsourced auditing scheme requires that if all the involved entities are honest, for all keys output bySetupprotocol and for all files F∈0,1∗ and the corresponding F~ output byPreproccess protocol, TPA always accepts probability 1 at the end of eachAuditCSPprotocol run and likewise the user at the end of eachAuditTPAprotocol. In addition, the correctness can be defined from another aspect thatIdentifyMaliceprotocol will never (i.e., with probability 0) be invoked, since if everything goes well then none of the entities will abort for invoking the last protocol.To define the soundness of our model, we start by the notion of liability in [23]. In contrast to the traditional public auditing security models, providing security to TPA is also an important aspect that should not be ignored in outsourced auditing setting. Especially in situations where some problems occur (e.g., the outsourced data has been lost in CSP), TPA must not be blamed as long as he can prove that he has fulfilled the auditing obligation according to the protocols. Namely, by providing his log files, if TPA convinces user with a high probability that he is taking over guarantees about the service quality of user’s outsourced data, then TPA is actually honest to finish his auditing task for each past challenge against CSP. This is the definition of liability which is formalized in [23]. Although the security model of [23] splits the definition of soundness into two parts, extractability and liability, we stress that the soundness of our User Focus outsourced auditing model can be defined as a whole, since liability becomes an intrinsic property and implicitly exists in our model without having to be proved for each instantiation.More precisely, as shown in Section2.3, throughout theAuditCSP protocol, TPA does not use any secret key when he performs his auditing work, which means that all operations conducted by TPA are deterministic inAuditCSP protocol. Firstly, the metadata Ψ and the public parameters set Γ are confirmed by the contract afterPreproccessprotocol is over. Secondly, the challenge C is individually generated by user, which is incontestable for user because of her signature. Therefore, TPA has no influence on all the involved parameters that are applied to complete his auditing work. TheIdentifyMaliceprotocol can reconstruct the results that should have occurred for TPA during each execution ofAuditCSP protocol and compare these results with TPA’s logs to judge if TPA is lazy or not. Clearly, these results are destined to be the objective and incontestable proofs once theAuditCSP protocol is executed. For this reason, no matter whether any malicious entity exists, a User Focus outsourced auditing scheme is bound to produce the objective proofs to protect a honest TPA who correctly performs his work, while guaranteeing that any lazy TPA can be identified as long as TPA’s logs do not conform to the objective proofs as above.In conclusion, our model is naturally sound for TPA in the case that TPA is honest, since honest TPA has been implicitly protected from the malicious user. So in the following we can define the soundness for User Focus outsourced auditing scheme by excluding the situation that user is corrupted.Now, we start by using the similar game employed in [23]. Firstly, given an adversary A who corrupts any entity E∈CSP,TPA. Subsequently, the adversary A takes over the role of corrupted entity E and plays the training game with an environment as follows:(1)
By running theSetupprotocol, the environment generates all the public-private keys for the involved entities and the secret key for user. The adversary A obtains all the keys of the corrupted entity E.(2)
For learning the knowledge of various outputs provided to the corrupted entityE, adversary A adaptively interacts with the environment, which plays the role of the honest entity. Given any file F, A can request the execution ofPreproccess protocol which outputs the outsourced data F~. Afterwards, A can request the executions ofAuditCSP andAuditTPAprotocols upon any above F~ stored in cloud. All these protocol executions can be arbitrarily interleaved with each other.(3)
Finally, after finishing all the learning, adversaryA outputs a challenge file F that should be stored and the description of a cheating prover CP corresponding to this file F.The cheating proverCP is ε-admissible if the probability that the honest entity interacts with CP without aborting the protocols is at least ε. Here, the probability is over the coins of the honest and malicious entities. To formalize the definition of soundness, we adopt the notion ofextractoralgorithm EA(·), which takes as inputs all the information provided to the honest entity, and the description of the cheating prover CP. The output of EA(·) is the file F. In particular, EA(·) is given non-black-box access to the cheating prover CP and can rewind it. Formally we have the following.Definition 2.
A User Focus outsourced auditing scheme isε-sound with respect to any corrupted entity E∈CSP,TPA if there exists an extractor algorithm EA(·) such that, for any honest entity establishing the contract on a file F~=F,Ψ,τ and interacting with the ε-admissible cheating prover CP, if the whole system remains running without being aborted by honest entity, the extractor can recover F from CP with overwhelming probability.Based on the above definition, we can informally say that if theε-admissible prover CP convinces the honest entity with a sufficient level of probability, then the challenged data is actually intact and extractable.Moreover, since the user is often reluctant to reveal her outsourced data to TPA, privacy protection is necessary, as defined in the following.Definition 3.
A User Focus outsourced auditing scheme with privacy-preserving requires that no matter what running results are obtained by TPA during the operation of this scheme, TPA cannot deduce any privacy information of user’s outsourced fileF—except possibly with negligible probability.


## 3. The Proposed Scheme

In this section, based on the proposed model, we present a concrete User Focus outsourced auditing scheme, the security of which is analyzed according to our security definitions.


### 3.1. Preliminaries

Given that the user wants to outsource her fileF to CSP. The file F can be seen as a set of n blocks: F=b1,b2,…,bn. We first introduce several necessary techniques, which are important under the environment of remote data auditing.Blockless Verification and Homomorphic Tags [7]. Blockless verification technique enables verifier to audit if the cloud servers possess certain file blocks, without having to retrieve these actual file blocks from the cloud. Blockless verification is essential since it is expensive and impracticable to retrieve all specified file blocks for frequent audits. Homomorphic tags can meet the requirement of blockless verification. Given two file blocks bi and bj, along with their corresponding homomorphic tags τi and τj, then the combination of τi and τj into a value τi+j will correspond to the tag of the sum of blocks bi and bj.Merkle Hash Tree (MHT) [26]. It is a kind of authenticated data structure, which can be used to efficiently and securely prove that, in a given set of elements, the value of each element and the order of all elements are both undamaged. Based on a collision-resistant cryptographic hash function H·, MHT can be constructed as a binary tree, by the rule that the value of each parent node is defined as Hleft_childvalue∥right_childvalue, where the leaf nodes are the hash values of authentic file blocks. In order to realize the authentication of each leaf node in MHT,Leaves Auxiliary Authentication Information (LAAI) is defined as the siblings of the nodes on the path from the leaf nodes to the MHT root. An example of MHT is shown in Figure 2. Assume that auditor possesses the root and wants to authenticate the appointed leaf nodes LN=h3,h6 provided by the adversary. According to the given LAAILN from adversary, auditor can compute hb,hc,he,hf in order and finally computes root∗=H(he∥hf). If root∗=root, auditor accepts all the leaf nodes of LN; otherwise, it rejects them. In our paper, the order of leaf nodes in MHT is treated from left to right. By following the given order, any leaf node can be located and authenticated by the root with its corresponding LAAI. Obviously, all the leaves ofMHT can be authenticated just by the root.Figure 2
The MHT based on 8 file blocks. For the appointed leaf nodes setLN={h3,h6}, the corresponding LAAILN=h4,h5,ha,hd.


### 3.2. Scheme Construction

Now, we detail the specifications of User Focus outsourced auditing scheme, comprising five protocolsSetup,Preproccess,AuditCSP,AuditTPA, andIdentifyMalice.


#### 3.2.1. Design ofSetup

For each entityE∈User,CSP,TPA, a corresponding public-private key pair (pkE,skE) is generated for signature by executing the signature key generation algorithm Sign_Key1k. Based on these key pairs, the secure communication links between any two entities can be established and authenticated in terms of the Transport Layer Security protocols.In order to construct the homomorphic tags, the user relies on the RSA algorithm to output the public keyPKTag=N,e, where N=pq is the product of two large primes p and q; e is a random large prime chosen by user. Let d=e-1mod⁡ϕN; then user obtains the private key SKTag=N,d. The PKTag will be sent to TPA, and SKTag is kept by user as her secret.


#### 3.2.2. Design ofPreproccess

This protocol, comprising the following four phases, is initiated and dominated by user who holds the fileF.(1) Generating Metadata
Ψ
,
τ
. Let H:0,1∗→ZN∗ be a full-domain hash. For each block {bi}1≤i≤n, user calculates hi←H(bi) as the corresponding leaf node of MHT. When the leaf nodes of all the blocks are generated, user can compute the root of MHT Ψ by iteratively hashing as shown in Section 3.1. Note that user just needs to compute the root, so it is not necessary for user to construct and store the whole MHT Ψ.Then user randomly chooses a public elementu←RZN∗ and a secret element x←RZϕN∗ and computes ω←uxmod⁡N. In terms of her secret key SKTag=N,d, for each block bi, user computes the corresponding tags τi←uhi·ωbidmod⁡N. Let F~ denote the processed file, described as follows:(6)F~≔F=bi,leaves=hi,τ=τi∣1≤i≤n.(2) Uploading
F
~
to CSP. After receiving F~ from user, for each bi∈F, CSP recomputes hi∗←H(bi) and compares hi∗ with the corresponding hi∈leaves. If hi∗≠hi, which signifies that there exists inconsistent data within F~, thus F~ will be rejected by CSP at once. If F~ passes CSP’s verification, based on all the hi∈leaves, CSP can reconstruct the whole MHT, denoted by ΨCSP with rootCSP. After this, CSP uses its signature signCSP to respond to user as follows:(7)responseCSP≔rootCSP,n∥signCSP.Upon receivingresponseCSP, user verifies CSP’s signature and then checks whether rootCSP is equal to root stored in her local. If rootCSP=root, indicating that the same MHT has been constructed at CSP side, then user stores responseCSP and sends out her acceptance to CSP. Otherwise, user aborts the protocol.(3) Authorizing TPA’s Auditing. When receiving the acceptance from user, CSP immediately sends all leaf nodes hi1≤i≤n to TPA. Similarly, TPA also reconstructs the whole MHT, denoted by ΨTPA with the rootTPA and sends his response to user:(8)responseTPA≔rootTPA,n∥signTPA.User executes the same verification process forresponseTPA as the way for responseCSP. If rootTPA=root, responseTPA is accepted and stored in local by user. At last, user sends the public key PKTag=N,e to TPA, meaning that the authorization of auditing CSP is provided to TPA.It is worth mentioning that we make CSP, on behalf of user, to transfer all leaf nodes of MHT to TPA in above process. This is in order to reduce bandwidth cost of user, who might have the limited bandwidth resource. We stress that user does not have to be worried about any security issue by this way. If malicious CSP tries to provide any false leaf node to TPA, as long as the hash functionH· preserves the collision-resistant property, then rootTPA will not be equal to the root at user side with overwhelming probability. Obviously, such unusual condition will be detected by user, who will terminate the auditing authorization immediately.(4) Agreeing on the Contract. A constant number lC needs to be assigned by user for denoting the amount of challenged blocks during each TPA’s auditing to CSP. Let Γ∶={root,lC,n,u,ω} denote the set of system parameters, which is signed by user and sent to both CSP and TPA. Afterwards, CSP and TPA must respond to user with their own signatures upon Γ, respectively, which means that all entities sign the contract for reaching an agreement. Note that CSP and TPA will store user’s signature signUser(Γ) in their locals, respectively, to protect themselves from a dishonest user.At lastF~ will be deleted from user side to complete this protocol. Different from the correspondingStore protocol of [23] that enables TPA to access the whole user’s outsourced data in cloud, throughout ourPreproccess protocol TPA can only obtain from CSP the hash values of file blocks, which contributes to protecting user’s data privacy from the curious TPA in the context of no encryption upon the outsourced data.


#### 3.2.3. Design ofAuditCSP

When each pregenerated challenge is released from user’s email box, this protocol will be launched, described as follows.(
1) User’s Challenge. Given a specific point-in-time t, the form of corresponding challenge Ct is defined as Ct  ≔  t∥(PRFt,PRPt,signuser), where PRFt is the key for public pseudo-random function F, PRPt is the key for public pseudo-random permutation P, and signUser is user’s signature.(i)
F: PRFt×{0,1}log2(n)→ZN∗.(ii)
P: PRPt×{0,1}log2(n)→{0,1}log2(n).BothPRFt and PRPt can be randomly or selectively generated by user. The meaning of selectively lies in that user can cover any specific block in a challenge by selectively generating the particular PRPt.LetFPRFt,j denote F keyed with key PRFt applied on the input j. According to public F and P, after receiving the challenge Ct and checking user’s signature, for each j∈1,lC, CSP can calculate the locations ij,t of challenged blocks by ij,t←PPRPt,j∈[1,n] and the associated values vj,t such as vj,t←FPRFt,j∈ZN∗. Here, we use St to denote the lC-elements set ij,t,vj,t1≤j≤lC, which can be generated based on Ct at time t.(
2) CSP’s Proof. After computing St, by randomly choosing a secret interfering element ξt←RZN∗ corresponding to the challenge Ct, CSP computes and signs its proof Pt≔Bt,τt,ωt,ut∥signCSP as below, where both u and ω are the public parameters:(9)Bt⟵∑ij,t,vj,t∈Stvj,t·bij,t+ξt∈Z,τt⟵∏ij,t,vj,t∈Stτij,tvj,tmod⁡N,ωt⟵ωξtmod⁡N,ut⟵uξtmod⁡N.Then CSP transfersPt to TPA. Since the size of the combined block Bt within Pt is roughly the size of a single file block, so CSP has a much smaller communication cost than for transferring lC challenged blocks. The key attribute of Pt is that there is no data privacy that can be deduced from Pt and leaked to TPA, as will be analyzed in Section 3.3.(3) TPA’s Verification. Upon receiving challenge Ct from user’s email box, TPA can compute St by the same way as CSP. Then TPA calculates his auditing parameter ηt as below, where all the hash values hij,t can be found from the leaf nodes of the MHT ΨTPA stored at TPA side.(10)ηt⟵∏ij,t,vj,t∈Stuvj,t·hij,tmod⁡N.Subsequently, TPA parses CSP’s proofPt to obtain Bt,τt, and ωt. Now TPA can use user’s public key PKTag=N,e to check whether(11)ηt·ωBtωt≟τtemod⁡N.If so, TPA outputsYES. Otherwise, according to the signed contract, TPA must report to user that CSP does not pass the integrity auditing upon the challenged blocks. It is clear that the interfering element ξt, generated and kept secretly by CSP, has no influence on the correctness of TPA’s verification. But ξt plays an important effect on the privacy protection of outsourced data, as will be discussed in Section 3.3.In addition, to prove that the auditing work related to the challengeCt has been performed correctly, TPA must generate the corresponding log⁡Θt≔Ct,Pt,ηt, which records the necessary information for the auditing against TPA launched by user.


#### 3.2.4. Design ofAuditTPA

In our scheme, we stress that TPA has to inform user as soon as anything has gone wrong during his auditing. If TPA is lazy and does nothing, then he cannot detect the outsourced data corruption in time, and user will find out such TPA’s misbehavior when executing theAuditTPA protocol upon a batch of TPA’s past logs.Specifically, user randomly selects ak-elements point-in-time set T=ti1≤i≤k, where each ti indicates the time when a past challenge is issued from user’s email box. User sends T to TPA. According to T, TPA parses his local logs to obtain the Pt=Bt,τt,ωt,ut,ηtt∈T and accumulates these values into the corresponding single value, respectively:(12)BT⟵∑t∈TBt,τT⟵∏t∈Tτtmod⁡N,ωT⟵∏t∈Tωtmod⁡N,uT⟵∏t∈Tutmod⁡N,ηT←∏t∈Tηtmod⁡N.Note that, for eacht∈T, TPA can also read the key PRPt from Ct within local log⁡Θt and then compute the locations of all challenged blocks related to the time set T by using the pseudo-random permutation PPRPt,j,1≤j≤lC. Let locat≔ij,tt∈T denote the set of all specified locations. Since some blocks might be challenged more than once, the repetitive locations will be taken away to ensure that every location in locat is unique.For eachij,t∈locat, TPA reads from his local MHT all the corresponding leaf nodes hij,t that constitute the set LNT≔hij,t. In addition, according to LNT, TPA generates the corresponding Leaves Auxiliary Authentication Information, LAAILNT (as shown in Section 3.1). Now, TPA constructs and signs his proof βT  ≔  BT,τT,ωT,uT,ηT,LNT,LAAILNT, which is sent to user as TPA’s response.Upon receivingβT and checking TPA’s signature, user first uses LNT and LAAILNT to compute the new root∗ of MHT and then compares root∗ with the root held by herself. User accepts LNT only when root∗=root, which indicates that all values of LNT pass user’s verification. If root∗≠root, a malicious TPA can be identified immediately.For eacht∈T, by accessing all the challenges Ct stored in her email box, user can use the same approach as CSP/TPA to regenerate each St=ij,t,vj,t1≤j≤lC by herself. Then user computes the following parameter ζT in terms of all hash values hij,t within the accepted LNT:(13)ζT⟵∏t∈T∏ij,t,vj,t∈Stuvj,t·hij,tmod⁡N.By comparingζT with ηT given by TPA within the proof βT, if ζT≠ηT, there is no doubt that TPA is indolent and thus user outputs NO. If ζT=ηT, with her secret element x, user further checks whether(14)uTx≟ωTmod⁡N.If this check fails, user outputsNO, confirming that CSP tries to misconduct by submitting the incompatible proof to TPA. Otherwise, based on her secret key SKTag=N,d, user finally checks whether(15)ωTd·τT≟ζT·ωBTdmod⁡N.If the last check fails, user will learn that (i) TPA is feckless for his past auditing work and (ii) the outsourced data has been damaged at cloud side. Note that if there is something wrong with the challenged file blocks stored in CSP, the corresponding TPA’s auditing is bound to fail and therefore TPA should report to user immediately according to theAuditCSPprotocol. So the execution ofAuditTPA protocol launched by user means that TPA implicitly makes a commitment to user about his conscientiousness for all the past auditing against CSP. In this context, once user’s last check fails, TPA is malicious without any doubt. So user can take actions such as claiming compensations from TPA and CSP in terms of their signed contract.In practice, as long as user’s check upon (15) passes, user can delete all past challenges Ct from her email box. Meanwhile, the authorization of allowing TPA to delete all corresponding logs⁡Θt, signed by user herself, is generated and sent to TPA. In this case, both user and TPA just only need a constant storage space for storing the pregenerated challenges and the corresponding logs, respectively. And by this way theAuditTPAprotocol will gain a significant performance improvement since the total number of point-in-time within the set T can be controlled under a reasonable upper limit.


#### 3.2.5. Design ofIdentifyMalice

Obviously, the process of theAuditCSP protocol has produced enough proofs to identify the malicious CSP who tries to conceal the fact of outsourced data corruption, and the process of theAuditTPA protocol also produces the undeniable proofs to identify the malicious TPA who tries to be lazy or does not perform the required auditing tasks correctly. Now, we show that how our scheme can defend against the malicious user, who wants to put the honest TPA in the wrong by purposely denying TPA’s correct auditing work.As shown in theAuditCSP protocol, firstly, the validity of TPA’s auditing parameter ηt is undeniable for the malicious user. Since all the elements used for computing ηt are incontestable from the user’s perspective, such as all the (ij,t,vj,t) derived from the challenge Ct signed by user herself, all the hash values hij,t can be authenticated based on the public MHT root, and the element u is public. Secondly, the required auditing work for TPA is to use ηt and CSP’s proof Pt to check (11), where the authenticity of Pt can be verified by verifying CSP’s signature, and the other two elements ω and e within (11) are also public. Therefore, in case of dispute or litigation, honest TPA can reveal his own MHT ΨTPA and the logs⁡Θt=Ct,Pt,ηt (or the corresponding authorization of allowing TPA to delete the past logs, signed by user, as described in theAuditTPAprotocol). In this case, provided that TPA always performs his auditing work correctly, then the malicious user has no chance to frame TPA up, since after authenticating ΨTPA by the public root, anyone can use the open logsΘt to reconstruct ηt and check (11) again to prove that honest TPA has actually fulfilled his auditing responsibility.


### 3.3. Security Analysis

According to the definitions in Section2.4, we analyze the security of the proposed scheme in this section. The correctness of (11) within theAuditCSP protocol can be elaborated as follows: (16)τte=∏ij,t,vj,t∈Stτij,tvj,temod⁡N=∏ij,t,vj,t∈Stuvj,t·hij,t·ωvj,t·bij,tedmod⁡N=ηt·∏ij,t,vj,t∈Stωvj,t·bij,tmod⁡N=ηt·ωBt-ξtmod⁡N=ηt·ωBtωtmod⁡N.Furthermore, the correctness of (15) within theAuditTPA protocol is elaborated as follows: (17)ωTd·τT=∏t∈Tωξt·∏ij,t,vj,t∈Stuvj,t·hij,t·ωvj,t·bij,tdmod⁡N=ζTd·∏t∈Tωξt·∏ij,t,vj,t∈Stωvj,t·bij,tdmod⁡N=ζTd·∏t∈TωBtdmod⁡N=ζTd·ωBTdmod⁡N=ζT·ωBTdmod⁡N.ε-Sound. As shown in Section 2.4, our scheme is naturally sound for honest TPA because of the implicit protection. Now, we prove the soundness for the other two cases where either user or CSP is honest. The soundness of our scheme for honest user is based on the Knowledge of Exponent Assumption (KEA), which was introduced by Damgård [27], formalized by Bellare and Palacio [28], and proved to be secure in the generic group model by Abe and Fehr [29]. Formally, KEA is described with anextractor as follows.KEA. For any adversary A that takes input N, u, ux and returns P,Q with P=Qx, there exists an “extractor” EA(·), given the same inputs as A returns B~ such that Q=uB~.Case  1. Honest user interacts with adversary A without aborting the protocol run. In this case, note that u and ω=ux are the public parameters taken as input by adversary A,who cannot deduce any information about user’s secret element x since the discrete logarithm problem is hard. We define B~ as B~≔∑t∈T∑j=1lCvj,t·bij,t. As described in theAuditTPA protocol, user will receive the returned BT,ωT,uT from adversary A. So the following two elements P and Q satisfying that P=Qx are the implicit output of adversary A:(18)P=ωBTωT=ωB~=uB~x;Q=uBTuT=uB~.Based on theKEA, theextractorEA(·) is able to extract B~. Assume that the time set T has k elements; then B~=∑t∈T∑j=1lCvj,t·bij,t is a linear equation built upon k×lC blocks set M≔bij,t1≤j≤lC,t∈T, since user can control the challenge Ct, which means that ij,t,vj,t1≤j≤lC,t∈T can be selectively determined by user. By depending on the honest user to generate independent coefficients vj,t1≤j≤lC,t∈T for the repetitive executions ofAuditTPA protocol upon the same file blocks set M,extractorEA(·) can obtain a system of k×lC independent linear equations for M. At last,extractorEA(·) can recover each file block of M just by solving the system of these linear equations. In terms of Definition 2 in Section 2.4, our scheme is ε-sound.Case  2.Honest CSP interacts with adversary A.At this point, the same security argument as in [23] can be adopted here. Throughout our scheme, as long as user’s outsourced data F~=F,leaves,τ can pass CSP’s verification during the execution of thePreproccess protocol, then honest CSP must correctly possess F~ and follow the subsequent protocols. So it is clear that theextractorEA(·) can always rely on the honest CSP to extract the file F from F~ for defending against any adversary A. This completes the proof for soundness.Privacy-Preserving against Curious TPA. Throughout our scheme, all the running results obtained by TPA are MHT Ψ and CSP’s proof Pt=Bt,τt,ωt,ut, which are derived from the executions ofPreproccess andAuditCSP protocols, respectively, with respect to MHT Ψ, where every leaf node is hash value such as hi←H(bi). So based on the preimage resistance attribute of the cryptographic hash function H·, none of privacy about the outsourced data block bi can be deduced from the leaf nodes of MHT Ψ.Now, we argue that TPA cannot deduce user’s data information from the proofPt output by CSP. Due to the intractability of discrete logarithm, for each t∈T, all the secret random interfering elements ξt, generated and stored individually by CSP for the corresponding challenges Ct, cannot be derived by TPA from ωt=ωξt and ut=uξt even though ω and u are the public parameters. As a consequence, for any specified blocks set bij,t1≤j≤lC, although TPA, via a number of challenges, might gather a system of linear equations such as Bt=ξt+∑j=1lCvj,t·bij,t with the different values of Bt and the independent coefficient vj,t1≤j≤lC, it is impossible for TPA to solve the system and deduce any data block bij,t since ξt is unknown and will randomly change within each linear equation of the system.With regard toτt∈Pt, which can be expressed as(19)τt=u∑j=1lCvj,t·hij,td·ω∑j=1lCvj,t·bij,td,obviously, to deduce the privacy of data blockbij,t, TPA has to compute the exponentiation value ∑j=1lCvj,t·bij,t from τt, which is the same as the intractability of discrete logarithm, let alone d which is the secret key stored by user and is unknown for TPA. Summing up, no matter how many running results collected by TPA, our scheme can always protect user’s data privacy from the curious TPA.


## 3.1. Preliminaries

Given that the user wants to outsource her fileF to CSP. The file F can be seen as a set of n blocks: F=b1,b2,…,bn. We first introduce several necessary techniques, which are important under the environment of remote data auditing.Blockless Verification and Homomorphic Tags [7]. Blockless verification technique enables verifier to audit if the cloud servers possess certain file blocks, without having to retrieve these actual file blocks from the cloud. Blockless verification is essential since it is expensive and impracticable to retrieve all specified file blocks for frequent audits. Homomorphic tags can meet the requirement of blockless verification. Given two file blocks bi and bj, along with their corresponding homomorphic tags τi and τj, then the combination of τi and τj into a value τi+j will correspond to the tag of the sum of blocks bi and bj.Merkle Hash Tree (MHT) [26]. It is a kind of authenticated data structure, which can be used to efficiently and securely prove that, in a given set of elements, the value of each element and the order of all elements are both undamaged. Based on a collision-resistant cryptographic hash function H·, MHT can be constructed as a binary tree, by the rule that the value of each parent node is defined as Hleft_childvalue∥right_childvalue, where the leaf nodes are the hash values of authentic file blocks. In order to realize the authentication of each leaf node in MHT,Leaves Auxiliary Authentication Information (LAAI) is defined as the siblings of the nodes on the path from the leaf nodes to the MHT root. An example of MHT is shown in Figure 2. Assume that auditor possesses the root and wants to authenticate the appointed leaf nodes LN=h3,h6 provided by the adversary. According to the given LAAILN from adversary, auditor can compute hb,hc,he,hf in order and finally computes root∗=H(he∥hf). If root∗=root, auditor accepts all the leaf nodes of LN; otherwise, it rejects them. In our paper, the order of leaf nodes in MHT is treated from left to right. By following the given order, any leaf node can be located and authenticated by the root with its corresponding LAAI. Obviously, all the leaves ofMHT can be authenticated just by the root.Figure 2
The MHT based on 8 file blocks. For the appointed leaf nodes setLN={h3,h6}, the corresponding LAAILN=h4,h5,ha,hd.


## 3.2. Scheme Construction

Now, we detail the specifications of User Focus outsourced auditing scheme, comprising five protocolsSetup,Preproccess,AuditCSP,AuditTPA, andIdentifyMalice.


### 3.2.1. Design ofSetup

For each entityE∈User,CSP,TPA, a corresponding public-private key pair (pkE,skE) is generated for signature by executing the signature key generation algorithm Sign_Key1k. Based on these key pairs, the secure communication links between any two entities can be established and authenticated in terms of the Transport Layer Security protocols.In order to construct the homomorphic tags, the user relies on the RSA algorithm to output the public keyPKTag=N,e, where N=pq is the product of two large primes p and q; e is a random large prime chosen by user. Let d=e-1mod⁡ϕN; then user obtains the private key SKTag=N,d. The PKTag will be sent to TPA, and SKTag is kept by user as her secret.


### 3.2.2. Design ofPreproccess

This protocol, comprising the following four phases, is initiated and dominated by user who holds the fileF.(1) Generating Metadata
Ψ
,
τ
. Let H:0,1∗→ZN∗ be a full-domain hash. For each block {bi}1≤i≤n, user calculates hi←H(bi) as the corresponding leaf node of MHT. When the leaf nodes of all the blocks are generated, user can compute the root of MHT Ψ by iteratively hashing as shown in Section 3.1. Note that user just needs to compute the root, so it is not necessary for user to construct and store the whole MHT Ψ.Then user randomly chooses a public elementu←RZN∗ and a secret element x←RZϕN∗ and computes ω←uxmod⁡N. In terms of her secret key SKTag=N,d, for each block bi, user computes the corresponding tags τi←uhi·ωbidmod⁡N. Let F~ denote the processed file, described as follows:(6)F~≔F=bi,leaves=hi,τ=τi∣1≤i≤n.(2) Uploading
F
~
to CSP. After receiving F~ from user, for each bi∈F, CSP recomputes hi∗←H(bi) and compares hi∗ with the corresponding hi∈leaves. If hi∗≠hi, which signifies that there exists inconsistent data within F~, thus F~ will be rejected by CSP at once. If F~ passes CSP’s verification, based on all the hi∈leaves, CSP can reconstruct the whole MHT, denoted by ΨCSP with rootCSP. After this, CSP uses its signature signCSP to respond to user as follows:(7)responseCSP≔rootCSP,n∥signCSP.Upon receivingresponseCSP, user verifies CSP’s signature and then checks whether rootCSP is equal to root stored in her local. If rootCSP=root, indicating that the same MHT has been constructed at CSP side, then user stores responseCSP and sends out her acceptance to CSP. Otherwise, user aborts the protocol.(3) Authorizing TPA’s Auditing. When receiving the acceptance from user, CSP immediately sends all leaf nodes hi1≤i≤n to TPA. Similarly, TPA also reconstructs the whole MHT, denoted by ΨTPA with the rootTPA and sends his response to user:(8)responseTPA≔rootTPA,n∥signTPA.User executes the same verification process forresponseTPA as the way for responseCSP. If rootTPA=root, responseTPA is accepted and stored in local by user. At last, user sends the public key PKTag=N,e to TPA, meaning that the authorization of auditing CSP is provided to TPA.It is worth mentioning that we make CSP, on behalf of user, to transfer all leaf nodes of MHT to TPA in above process. This is in order to reduce bandwidth cost of user, who might have the limited bandwidth resource. We stress that user does not have to be worried about any security issue by this way. If malicious CSP tries to provide any false leaf node to TPA, as long as the hash functionH· preserves the collision-resistant property, then rootTPA will not be equal to the root at user side with overwhelming probability. Obviously, such unusual condition will be detected by user, who will terminate the auditing authorization immediately.(4) Agreeing on the Contract. A constant number lC needs to be assigned by user for denoting the amount of challenged blocks during each TPA’s auditing to CSP. Let Γ∶={root,lC,n,u,ω} denote the set of system parameters, which is signed by user and sent to both CSP and TPA. Afterwards, CSP and TPA must respond to user with their own signatures upon Γ, respectively, which means that all entities sign the contract for reaching an agreement. Note that CSP and TPA will store user’s signature signUser(Γ) in their locals, respectively, to protect themselves from a dishonest user.At lastF~ will be deleted from user side to complete this protocol. Different from the correspondingStore protocol of [23] that enables TPA to access the whole user’s outsourced data in cloud, throughout ourPreproccess protocol TPA can only obtain from CSP the hash values of file blocks, which contributes to protecting user’s data privacy from the curious TPA in the context of no encryption upon the outsourced data.


### 3.2.3. Design ofAuditCSP

When each pregenerated challenge is released from user’s email box, this protocol will be launched, described as follows.(
1) User’s Challenge. Given a specific point-in-time t, the form of corresponding challenge Ct is defined as Ct  ≔  t∥(PRFt,PRPt,signuser), where PRFt is the key for public pseudo-random function F, PRPt is the key for public pseudo-random permutation P, and signUser is user’s signature.(i)
F: PRFt×{0,1}log2(n)→ZN∗.(ii)
P: PRPt×{0,1}log2(n)→{0,1}log2(n).BothPRFt and PRPt can be randomly or selectively generated by user. The meaning of selectively lies in that user can cover any specific block in a challenge by selectively generating the particular PRPt.LetFPRFt,j denote F keyed with key PRFt applied on the input j. According to public F and P, after receiving the challenge Ct and checking user’s signature, for each j∈1,lC, CSP can calculate the locations ij,t of challenged blocks by ij,t←PPRPt,j∈[1,n] and the associated values vj,t such as vj,t←FPRFt,j∈ZN∗. Here, we use St to denote the lC-elements set ij,t,vj,t1≤j≤lC, which can be generated based on Ct at time t.(
2) CSP’s Proof. After computing St, by randomly choosing a secret interfering element ξt←RZN∗ corresponding to the challenge Ct, CSP computes and signs its proof Pt≔Bt,τt,ωt,ut∥signCSP as below, where both u and ω are the public parameters:(9)Bt⟵∑ij,t,vj,t∈Stvj,t·bij,t+ξt∈Z,τt⟵∏ij,t,vj,t∈Stτij,tvj,tmod⁡N,ωt⟵ωξtmod⁡N,ut⟵uξtmod⁡N.Then CSP transfersPt to TPA. Since the size of the combined block Bt within Pt is roughly the size of a single file block, so CSP has a much smaller communication cost than for transferring lC challenged blocks. The key attribute of Pt is that there is no data privacy that can be deduced from Pt and leaked to TPA, as will be analyzed in Section 3.3.(3) TPA’s Verification. Upon receiving challenge Ct from user’s email box, TPA can compute St by the same way as CSP. Then TPA calculates his auditing parameter ηt as below, where all the hash values hij,t can be found from the leaf nodes of the MHT ΨTPA stored at TPA side.(10)ηt⟵∏ij,t,vj,t∈Stuvj,t·hij,tmod⁡N.Subsequently, TPA parses CSP’s proofPt to obtain Bt,τt, and ωt. Now TPA can use user’s public key PKTag=N,e to check whether(11)ηt·ωBtωt≟τtemod⁡N.If so, TPA outputsYES. Otherwise, according to the signed contract, TPA must report to user that CSP does not pass the integrity auditing upon the challenged blocks. It is clear that the interfering element ξt, generated and kept secretly by CSP, has no influence on the correctness of TPA’s verification. But ξt plays an important effect on the privacy protection of outsourced data, as will be discussed in Section 3.3.In addition, to prove that the auditing work related to the challengeCt has been performed correctly, TPA must generate the corresponding log⁡Θt≔Ct,Pt,ηt, which records the necessary information for the auditing against TPA launched by user.


### 3.2.4. Design ofAuditTPA

In our scheme, we stress that TPA has to inform user as soon as anything has gone wrong during his auditing. If TPA is lazy and does nothing, then he cannot detect the outsourced data corruption in time, and user will find out such TPA’s misbehavior when executing theAuditTPA protocol upon a batch of TPA’s past logs.Specifically, user randomly selects ak-elements point-in-time set T=ti1≤i≤k, where each ti indicates the time when a past challenge is issued from user’s email box. User sends T to TPA. According to T, TPA parses his local logs to obtain the Pt=Bt,τt,ωt,ut,ηtt∈T and accumulates these values into the corresponding single value, respectively:(12)BT⟵∑t∈TBt,τT⟵∏t∈Tτtmod⁡N,ωT⟵∏t∈Tωtmod⁡N,uT⟵∏t∈Tutmod⁡N,ηT←∏t∈Tηtmod⁡N.Note that, for eacht∈T, TPA can also read the key PRPt from Ct within local log⁡Θt and then compute the locations of all challenged blocks related to the time set T by using the pseudo-random permutation PPRPt,j,1≤j≤lC. Let locat≔ij,tt∈T denote the set of all specified locations. Since some blocks might be challenged more than once, the repetitive locations will be taken away to ensure that every location in locat is unique.For eachij,t∈locat, TPA reads from his local MHT all the corresponding leaf nodes hij,t that constitute the set LNT≔hij,t. In addition, according to LNT, TPA generates the corresponding Leaves Auxiliary Authentication Information, LAAILNT (as shown in Section 3.1). Now, TPA constructs and signs his proof βT  ≔  BT,τT,ωT,uT,ηT,LNT,LAAILNT, which is sent to user as TPA’s response.Upon receivingβT and checking TPA’s signature, user first uses LNT and LAAILNT to compute the new root∗ of MHT and then compares root∗ with the root held by herself. User accepts LNT only when root∗=root, which indicates that all values of LNT pass user’s verification. If root∗≠root, a malicious TPA can be identified immediately.For eacht∈T, by accessing all the challenges Ct stored in her email box, user can use the same approach as CSP/TPA to regenerate each St=ij,t,vj,t1≤j≤lC by herself. Then user computes the following parameter ζT in terms of all hash values hij,t within the accepted LNT:(13)ζT⟵∏t∈T∏ij,t,vj,t∈Stuvj,t·hij,tmod⁡N.By comparingζT with ηT given by TPA within the proof βT, if ζT≠ηT, there is no doubt that TPA is indolent and thus user outputs NO. If ζT=ηT, with her secret element x, user further checks whether(14)uTx≟ωTmod⁡N.If this check fails, user outputsNO, confirming that CSP tries to misconduct by submitting the incompatible proof to TPA. Otherwise, based on her secret key SKTag=N,d, user finally checks whether(15)ωTd·τT≟ζT·ωBTdmod⁡N.If the last check fails, user will learn that (i) TPA is feckless for his past auditing work and (ii) the outsourced data has been damaged at cloud side. Note that if there is something wrong with the challenged file blocks stored in CSP, the corresponding TPA’s auditing is bound to fail and therefore TPA should report to user immediately according to theAuditCSPprotocol. So the execution ofAuditTPA protocol launched by user means that TPA implicitly makes a commitment to user about his conscientiousness for all the past auditing against CSP. In this context, once user’s last check fails, TPA is malicious without any doubt. So user can take actions such as claiming compensations from TPA and CSP in terms of their signed contract.In practice, as long as user’s check upon (15) passes, user can delete all past challenges Ct from her email box. Meanwhile, the authorization of allowing TPA to delete all corresponding logs⁡Θt, signed by user herself, is generated and sent to TPA. In this case, both user and TPA just only need a constant storage space for storing the pregenerated challenges and the corresponding logs, respectively. And by this way theAuditTPAprotocol will gain a significant performance improvement since the total number of point-in-time within the set T can be controlled under a reasonable upper limit.


### 3.2.5. Design ofIdentifyMalice

Obviously, the process of theAuditCSP protocol has produced enough proofs to identify the malicious CSP who tries to conceal the fact of outsourced data corruption, and the process of theAuditTPA protocol also produces the undeniable proofs to identify the malicious TPA who tries to be lazy or does not perform the required auditing tasks correctly. Now, we show that how our scheme can defend against the malicious user, who wants to put the honest TPA in the wrong by purposely denying TPA’s correct auditing work.As shown in theAuditCSP protocol, firstly, the validity of TPA’s auditing parameter ηt is undeniable for the malicious user. Since all the elements used for computing ηt are incontestable from the user’s perspective, such as all the (ij,t,vj,t) derived from the challenge Ct signed by user herself, all the hash values hij,t can be authenticated based on the public MHT root, and the element u is public. Secondly, the required auditing work for TPA is to use ηt and CSP’s proof Pt to check (11), where the authenticity of Pt can be verified by verifying CSP’s signature, and the other two elements ω and e within (11) are also public. Therefore, in case of dispute or litigation, honest TPA can reveal his own MHT ΨTPA and the logs⁡Θt=Ct,Pt,ηt (or the corresponding authorization of allowing TPA to delete the past logs, signed by user, as described in theAuditTPAprotocol). In this case, provided that TPA always performs his auditing work correctly, then the malicious user has no chance to frame TPA up, since after authenticating ΨTPA by the public root, anyone can use the open logsΘt to reconstruct ηt and check (11) again to prove that honest TPA has actually fulfilled his auditing responsibility.


## 3.2.1. Design ofSetup

For each entityE∈User,CSP,TPA, a corresponding public-private key pair (pkE,skE) is generated for signature by executing the signature key generation algorithm Sign_Key1k. Based on these key pairs, the secure communication links between any two entities can be established and authenticated in terms of the Transport Layer Security protocols.In order to construct the homomorphic tags, the user relies on the RSA algorithm to output the public keyPKTag=N,e, where N=pq is the product of two large primes p and q; e is a random large prime chosen by user. Let d=e-1mod⁡ϕN; then user obtains the private key SKTag=N,d. The PKTag will be sent to TPA, and SKTag is kept by user as her secret.


## 3.2.2. Design ofPreproccess

This protocol, comprising the following four phases, is initiated and dominated by user who holds the fileF.(1) Generating Metadata
Ψ
,
τ
. Let H:0,1∗→ZN∗ be a full-domain hash. For each block {bi}1≤i≤n, user calculates hi←H(bi) as the corresponding leaf node of MHT. When the leaf nodes of all the blocks are generated, user can compute the root of MHT Ψ by iteratively hashing as shown in Section 3.1. Note that user just needs to compute the root, so it is not necessary for user to construct and store the whole MHT Ψ.Then user randomly chooses a public elementu←RZN∗ and a secret element x←RZϕN∗ and computes ω←uxmod⁡N. In terms of her secret key SKTag=N,d, for each block bi, user computes the corresponding tags τi←uhi·ωbidmod⁡N. Let F~ denote the processed file, described as follows:(6)F~≔F=bi,leaves=hi,τ=τi∣1≤i≤n.(2) Uploading
F
~
to CSP. After receiving F~ from user, for each bi∈F, CSP recomputes hi∗←H(bi) and compares hi∗ with the corresponding hi∈leaves. If hi∗≠hi, which signifies that there exists inconsistent data within F~, thus F~ will be rejected by CSP at once. If F~ passes CSP’s verification, based on all the hi∈leaves, CSP can reconstruct the whole MHT, denoted by ΨCSP with rootCSP. After this, CSP uses its signature signCSP to respond to user as follows:(7)responseCSP≔rootCSP,n∥signCSP.Upon receivingresponseCSP, user verifies CSP’s signature and then checks whether rootCSP is equal to root stored in her local. If rootCSP=root, indicating that the same MHT has been constructed at CSP side, then user stores responseCSP and sends out her acceptance to CSP. Otherwise, user aborts the protocol.(3) Authorizing TPA’s Auditing. When receiving the acceptance from user, CSP immediately sends all leaf nodes hi1≤i≤n to TPA. Similarly, TPA also reconstructs the whole MHT, denoted by ΨTPA with the rootTPA and sends his response to user:(8)responseTPA≔rootTPA,n∥signTPA.User executes the same verification process forresponseTPA as the way for responseCSP. If rootTPA=root, responseTPA is accepted and stored in local by user. At last, user sends the public key PKTag=N,e to TPA, meaning that the authorization of auditing CSP is provided to TPA.It is worth mentioning that we make CSP, on behalf of user, to transfer all leaf nodes of MHT to TPA in above process. This is in order to reduce bandwidth cost of user, who might have the limited bandwidth resource. We stress that user does not have to be worried about any security issue by this way. If malicious CSP tries to provide any false leaf node to TPA, as long as the hash functionH· preserves the collision-resistant property, then rootTPA will not be equal to the root at user side with overwhelming probability. Obviously, such unusual condition will be detected by user, who will terminate the auditing authorization immediately.(4) Agreeing on the Contract. A constant number lC needs to be assigned by user for denoting the amount of challenged blocks during each TPA’s auditing to CSP. Let Γ∶={root,lC,n,u,ω} denote the set of system parameters, which is signed by user and sent to both CSP and TPA. Afterwards, CSP and TPA must respond to user with their own signatures upon Γ, respectively, which means that all entities sign the contract for reaching an agreement. Note that CSP and TPA will store user’s signature signUser(Γ) in their locals, respectively, to protect themselves from a dishonest user.At lastF~ will be deleted from user side to complete this protocol. Different from the correspondingStore protocol of [23] that enables TPA to access the whole user’s outsourced data in cloud, throughout ourPreproccess protocol TPA can only obtain from CSP the hash values of file blocks, which contributes to protecting user’s data privacy from the curious TPA in the context of no encryption upon the outsourced data.


## 3.2.3. Design ofAuditCSP

When each pregenerated challenge is released from user’s email box, this protocol will be launched, described as follows.(
1) User’s Challenge. Given a specific point-in-time t, the form of corresponding challenge Ct is defined as Ct  ≔  t∥(PRFt,PRPt,signuser), where PRFt is the key for public pseudo-random function F, PRPt is the key for public pseudo-random permutation P, and signUser is user’s signature.(i)
F: PRFt×{0,1}log2(n)→ZN∗.(ii)
P: PRPt×{0,1}log2(n)→{0,1}log2(n).BothPRFt and PRPt can be randomly or selectively generated by user. The meaning of selectively lies in that user can cover any specific block in a challenge by selectively generating the particular PRPt.LetFPRFt,j denote F keyed with key PRFt applied on the input j. According to public F and P, after receiving the challenge Ct and checking user’s signature, for each j∈1,lC, CSP can calculate the locations ij,t of challenged blocks by ij,t←PPRPt,j∈[1,n] and the associated values vj,t such as vj,t←FPRFt,j∈ZN∗. Here, we use St to denote the lC-elements set ij,t,vj,t1≤j≤lC, which can be generated based on Ct at time t.(
2) CSP’s Proof. After computing St, by randomly choosing a secret interfering element ξt←RZN∗ corresponding to the challenge Ct, CSP computes and signs its proof Pt≔Bt,τt,ωt,ut∥signCSP as below, where both u and ω are the public parameters:(9)Bt⟵∑ij,t,vj,t∈Stvj,t·bij,t+ξt∈Z,τt⟵∏ij,t,vj,t∈Stτij,tvj,tmod⁡N,ωt⟵ωξtmod⁡N,ut⟵uξtmod⁡N.Then CSP transfersPt to TPA. Since the size of the combined block Bt within Pt is roughly the size of a single file block, so CSP has a much smaller communication cost than for transferring lC challenged blocks. The key attribute of Pt is that there is no data privacy that can be deduced from Pt and leaked to TPA, as will be analyzed in Section 3.3.(3) TPA’s Verification. Upon receiving challenge Ct from user’s email box, TPA can compute St by the same way as CSP. Then TPA calculates his auditing parameter ηt as below, where all the hash values hij,t can be found from the leaf nodes of the MHT ΨTPA stored at TPA side.(10)ηt⟵∏ij,t,vj,t∈Stuvj,t·hij,tmod⁡N.Subsequently, TPA parses CSP’s proofPt to obtain Bt,τt, and ωt. Now TPA can use user’s public key PKTag=N,e to check whether(11)ηt·ωBtωt≟τtemod⁡N.If so, TPA outputsYES. Otherwise, according to the signed contract, TPA must report to user that CSP does not pass the integrity auditing upon the challenged blocks. It is clear that the interfering element ξt, generated and kept secretly by CSP, has no influence on the correctness of TPA’s verification. But ξt plays an important effect on the privacy protection of outsourced data, as will be discussed in Section 3.3.In addition, to prove that the auditing work related to the challengeCt has been performed correctly, TPA must generate the corresponding log⁡Θt≔Ct,Pt,ηt, which records the necessary information for the auditing against TPA launched by user.


## 3.2.4. Design ofAuditTPA

In our scheme, we stress that TPA has to inform user as soon as anything has gone wrong during his auditing. If TPA is lazy and does nothing, then he cannot detect the outsourced data corruption in time, and user will find out such TPA’s misbehavior when executing theAuditTPA protocol upon a batch of TPA’s past logs.Specifically, user randomly selects ak-elements point-in-time set T=ti1≤i≤k, where each ti indicates the time when a past challenge is issued from user’s email box. User sends T to TPA. According to T, TPA parses his local logs to obtain the Pt=Bt,τt,ωt,ut,ηtt∈T and accumulates these values into the corresponding single value, respectively:(12)BT⟵∑t∈TBt,τT⟵∏t∈Tτtmod⁡N,ωT⟵∏t∈Tωtmod⁡N,uT⟵∏t∈Tutmod⁡N,ηT←∏t∈Tηtmod⁡N.Note that, for eacht∈T, TPA can also read the key PRPt from Ct within local log⁡Θt and then compute the locations of all challenged blocks related to the time set T by using the pseudo-random permutation PPRPt,j,1≤j≤lC. Let locat≔ij,tt∈T denote the set of all specified locations. Since some blocks might be challenged more than once, the repetitive locations will be taken away to ensure that every location in locat is unique.For eachij,t∈locat, TPA reads from his local MHT all the corresponding leaf nodes hij,t that constitute the set LNT≔hij,t. In addition, according to LNT, TPA generates the corresponding Leaves Auxiliary Authentication Information, LAAILNT (as shown in Section 3.1). Now, TPA constructs and signs his proof βT  ≔  BT,τT,ωT,uT,ηT,LNT,LAAILNT, which is sent to user as TPA’s response.Upon receivingβT and checking TPA’s signature, user first uses LNT and LAAILNT to compute the new root∗ of MHT and then compares root∗ with the root held by herself. User accepts LNT only when root∗=root, which indicates that all values of LNT pass user’s verification. If root∗≠root, a malicious TPA can be identified immediately.For eacht∈T, by accessing all the challenges Ct stored in her email box, user can use the same approach as CSP/TPA to regenerate each St=ij,t,vj,t1≤j≤lC by herself. Then user computes the following parameter ζT in terms of all hash values hij,t within the accepted LNT:(13)ζT⟵∏t∈T∏ij,t,vj,t∈Stuvj,t·hij,tmod⁡N.By comparingζT with ηT given by TPA within the proof βT, if ζT≠ηT, there is no doubt that TPA is indolent and thus user outputs NO. If ζT=ηT, with her secret element x, user further checks whether(14)uTx≟ωTmod⁡N.If this check fails, user outputsNO, confirming that CSP tries to misconduct by submitting the incompatible proof to TPA. Otherwise, based on her secret key SKTag=N,d, user finally checks whether(15)ωTd·τT≟ζT·ωBTdmod⁡N.If the last check fails, user will learn that (i) TPA is feckless for his past auditing work and (ii) the outsourced data has been damaged at cloud side. Note that if there is something wrong with the challenged file blocks stored in CSP, the corresponding TPA’s auditing is bound to fail and therefore TPA should report to user immediately according to theAuditCSPprotocol. So the execution ofAuditTPA protocol launched by user means that TPA implicitly makes a commitment to user about his conscientiousness for all the past auditing against CSP. In this context, once user’s last check fails, TPA is malicious without any doubt. So user can take actions such as claiming compensations from TPA and CSP in terms of their signed contract.In practice, as long as user’s check upon (15) passes, user can delete all past challenges Ct from her email box. Meanwhile, the authorization of allowing TPA to delete all corresponding logs⁡Θt, signed by user herself, is generated and sent to TPA. In this case, both user and TPA just only need a constant storage space for storing the pregenerated challenges and the corresponding logs, respectively. And by this way theAuditTPAprotocol will gain a significant performance improvement since the total number of point-in-time within the set T can be controlled under a reasonable upper limit.


## 3.2.5. Design ofIdentifyMalice

Obviously, the process of theAuditCSP protocol has produced enough proofs to identify the malicious CSP who tries to conceal the fact of outsourced data corruption, and the process of theAuditTPA protocol also produces the undeniable proofs to identify the malicious TPA who tries to be lazy or does not perform the required auditing tasks correctly. Now, we show that how our scheme can defend against the malicious user, who wants to put the honest TPA in the wrong by purposely denying TPA’s correct auditing work.As shown in theAuditCSP protocol, firstly, the validity of TPA’s auditing parameter ηt is undeniable for the malicious user. Since all the elements used for computing ηt are incontestable from the user’s perspective, such as all the (ij,t,vj,t) derived from the challenge Ct signed by user herself, all the hash values hij,t can be authenticated based on the public MHT root, and the element u is public. Secondly, the required auditing work for TPA is to use ηt and CSP’s proof Pt to check (11), where the authenticity of Pt can be verified by verifying CSP’s signature, and the other two elements ω and e within (11) are also public. Therefore, in case of dispute or litigation, honest TPA can reveal his own MHT ΨTPA and the logs⁡Θt=Ct,Pt,ηt (or the corresponding authorization of allowing TPA to delete the past logs, signed by user, as described in theAuditTPAprotocol). In this case, provided that TPA always performs his auditing work correctly, then the malicious user has no chance to frame TPA up, since after authenticating ΨTPA by the public root, anyone can use the open logsΘt to reconstruct ηt and check (11) again to prove that honest TPA has actually fulfilled his auditing responsibility.


## 3.3. Security Analysis

According to the definitions in Section2.4, we analyze the security of the proposed scheme in this section. The correctness of (11) within theAuditCSP protocol can be elaborated as follows: (16)τte=∏ij,t,vj,t∈Stτij,tvj,temod⁡N=∏ij,t,vj,t∈Stuvj,t·hij,t·ωvj,t·bij,tedmod⁡N=ηt·∏ij,t,vj,t∈Stωvj,t·bij,tmod⁡N=ηt·ωBt-ξtmod⁡N=ηt·ωBtωtmod⁡N.Furthermore, the correctness of (15) within theAuditTPA protocol is elaborated as follows: (17)ωTd·τT=∏t∈Tωξt·∏ij,t,vj,t∈Stuvj,t·hij,t·ωvj,t·bij,tdmod⁡N=ζTd·∏t∈Tωξt·∏ij,t,vj,t∈Stωvj,t·bij,tdmod⁡N=ζTd·∏t∈TωBtdmod⁡N=ζTd·ωBTdmod⁡N=ζT·ωBTdmod⁡N.ε-Sound. As shown in Section 2.4, our scheme is naturally sound for honest TPA because of the implicit protection. Now, we prove the soundness for the other two cases where either user or CSP is honest. The soundness of our scheme for honest user is based on the Knowledge of Exponent Assumption (KEA), which was introduced by Damgård [27], formalized by Bellare and Palacio [28], and proved to be secure in the generic group model by Abe and Fehr [29]. Formally, KEA is described with anextractor as follows.KEA. For any adversary A that takes input N, u, ux and returns P,Q with P=Qx, there exists an “extractor” EA(·), given the same inputs as A returns B~ such that Q=uB~.Case  1. Honest user interacts with adversary A without aborting the protocol run. In this case, note that u and ω=ux are the public parameters taken as input by adversary A,who cannot deduce any information about user’s secret element x since the discrete logarithm problem is hard. We define B~ as B~≔∑t∈T∑j=1lCvj,t·bij,t. As described in theAuditTPA protocol, user will receive the returned BT,ωT,uT from adversary A. So the following two elements P and Q satisfying that P=Qx are the implicit output of adversary A:(18)P=ωBTωT=ωB~=uB~x;Q=uBTuT=uB~.Based on theKEA, theextractorEA(·) is able to extract B~. Assume that the time set T has k elements; then B~=∑t∈T∑j=1lCvj,t·bij,t is a linear equation built upon k×lC blocks set M≔bij,t1≤j≤lC,t∈T, since user can control the challenge Ct, which means that ij,t,vj,t1≤j≤lC,t∈T can be selectively determined by user. By depending on the honest user to generate independent coefficients vj,t1≤j≤lC,t∈T for the repetitive executions ofAuditTPA protocol upon the same file blocks set M,extractorEA(·) can obtain a system of k×lC independent linear equations for M. At last,extractorEA(·) can recover each file block of M just by solving the system of these linear equations. In terms of Definition 2 in Section 2.4, our scheme is ε-sound.Case  2.Honest CSP interacts with adversary A.At this point, the same security argument as in [23] can be adopted here. Throughout our scheme, as long as user’s outsourced data F~=F,leaves,τ can pass CSP’s verification during the execution of thePreproccess protocol, then honest CSP must correctly possess F~ and follow the subsequent protocols. So it is clear that theextractorEA(·) can always rely on the honest CSP to extract the file F from F~ for defending against any adversary A. This completes the proof for soundness.Privacy-Preserving against Curious TPA. Throughout our scheme, all the running results obtained by TPA are MHT Ψ and CSP’s proof Pt=Bt,τt,ωt,ut, which are derived from the executions ofPreproccess andAuditCSP protocols, respectively, with respect to MHT Ψ, where every leaf node is hash value such as hi←H(bi). So based on the preimage resistance attribute of the cryptographic hash function H·, none of privacy about the outsourced data block bi can be deduced from the leaf nodes of MHT Ψ.Now, we argue that TPA cannot deduce user’s data information from the proofPt output by CSP. Due to the intractability of discrete logarithm, for each t∈T, all the secret random interfering elements ξt, generated and stored individually by CSP for the corresponding challenges Ct, cannot be derived by TPA from ωt=ωξt and ut=uξt even though ω and u are the public parameters. As a consequence, for any specified blocks set bij,t1≤j≤lC, although TPA, via a number of challenges, might gather a system of linear equations such as Bt=ξt+∑j=1lCvj,t·bij,t with the different values of Bt and the independent coefficient vj,t1≤j≤lC, it is impossible for TPA to solve the system and deduce any data block bij,t since ξt is unknown and will randomly change within each linear equation of the system.With regard toτt∈Pt, which can be expressed as(19)τt=u∑j=1lCvj,t·hij,td·ω∑j=1lCvj,t·bij,td,obviously, to deduce the privacy of data blockbij,t, TPA has to compute the exponentiation value ∑j=1lCvj,t·bij,t from τt, which is the same as the intractability of discrete logarithm, let alone d which is the secret key stored by user and is unknown for TPA. Summing up, no matter how many running results collected by TPA, our scheme can always protect user’s data privacy from the curious TPA.


## 4. Dynamic Updates

Different from the outsourced auditing scheme of [23], our scheme constructs for each block bi the corresponding homomorphic tag τi without involving the block location i. In this way, the dynamic operations such as modification, insertion, and deletion can be realized by merely updating the targeted file block without affecting any others. For ease of description, we define the function of CalRootnode,LAAInode that is to calculate the hash value of MHT root by applying the node and its corresponding LAAInode, the example of which is described as shown in Section 3.1. As for the insertion operation, by default the new block bi∗ will be inserted behind the appointed block location i.Now we can present Algorithm1 for modifying or inserting a new block bi∗, and Algorithm 2 for deleting an appointed block at cloud server side. The main idea of these two algorithms is to let user control the update of MHT root throughout the process of data dynamics, since both CSP and TPA cannot output the expected root hash value unless they have correctly performed the dynamic operations as required by user. Both of these two algorithms are launched by user, who first transmits to CSP the necessary update command including the appointed location i. After receiving user’s command, CSP must respond with the corresponding hi,LAAIhi. Note that user holds the original MHT root, which enables user to verify the authenticity of hi,LAAIhi from CSP by checking if the root hash value is equal to the output of running CalRoothi,LAAIhi. Once this user’s verification passes, by calling CalRoot· again based on the LAAIhi and above update command, user can compute by herself what the new root∗ would be after performing her update command upon the MHT stored at CSP side. In this case, to obtain user’s authorization for actually executing the dynamic operations upon user’s outsourced file F~, CSP has to update its MHT in terms of user’s command and output to user the same new root∗. Similarly, user will send the update command to TPA, and the same situation of updating MHT applies to the TPA side. Obviously, both CSP and TPA have to be well-behaving all the time; otherwise, their misconducts will be detected when theAuditCSPandAuditTPAprotocols of our proposed outsourced auditing scheme are launched. Finally, user will update her local MHT root with the new root∗, meaning that the dynamic operations are executed successfully.Algorithm 1:Algorithm for modifying or inserting a block.
Algorithm: root∗ = Modify_or_Insert_Block (i, bi∗).
Input: the appointed block location i, and the new block bi∗.
Output: the new root∗ of the updated MHT.
(
1
)
User: compute hi∗←H(bi∗); τi∗←(uhi∗⋅ωbi∗)dmodN;
(
2
)
transmit (mark,i,bi∗,hi∗,τi∗) to CSP;
(
3
)
CSP: compute hi∗~←H(bi∗)
(
4
)
if
h
i
∗
~
=
h
i
∗
then
(
5
)
if
mark = modify then
(
6
)
S
⟵
h
i
∗;
(
7
)
else
m
a
r
k
=
i
n
s
e
r
t
(
8
)
S
⟵
H
(
h
i
∥
h
i
∗
);
(
9
)
end if
(
10
)
compute root~∗⟵CalRoot(S,LAAIhi);
(
11
)
send hi,LAAIhi,root~∗ to user;
(
12
)
end if
(
13
)
User: compute rootT←CalRoot(hi,LAAIhi);
(
14
)
if
r
o
o
t
T
=
r
o
o
t
then
(
15
)
compute root∗←CalRoot(S,LAAIhi);
(
16
)
if
r
o
o
t
∗
=
r
o
o
t
~
∗
then
(
17
)
authorize CSP to execute update operation;
(
18
)
end if
(
19
)
end if
(
20
)
CSP:  ifmark= modify then{notethatroot∗=root~∗}
(
21
)
b
i, hi, τi are replaced by bi∗, hi∗, τi∗ in the outsourced file F~;
(
22
)
update the MHT Ψ stored in cloud by recalculating all the nodes on the path from
the ith leaf node hi∗ to the root∗;
(
23
)
else
m
a
r
k
=
i
n
s
e
r
t
,
n
o
t
e
t
h
a
t
r
o
o
t
∗
=
r
o
o
t
~
∗
(
24
)
insert bi∗, τi∗ into F~ after bi, τi, respectively;
(
25
)
update the MHT Ψ by replacing with H(hi∥hi∗) the ith primordial leaf node that is transformed into
a parent node having the left-child leaf hi and the right-child leaf hi∗, and then recalculating all the
nodes on the path from H(hi∥hi∗) to the root∗;
(
26
)
end if
(
27
)
User: transmit (mark,i,hi∗) to TPA;
(
28
)
TPA: according to the mark, update the MHT Ψ stored at TPA side by the same way as CSP;
(
29
)
send to user the root of the updated MHT Ψ, denoted by root̿∗;
(
30
)
User: ifroot∗=root̿∗then
(
31
)
update the root, stored in her local, with root∗;
(
32
)
end if
(
33
)
return
r
o
o
t
∗;Algorithm 2:Algorithm for deleting a block.
Algorithm: root∗=Delete_Block  (i).
Input: the location i of the appointed block that will be deleted.
Output: the new root∗ of the updated MHT.
(
1
)
User: transmit (delete,i) to CSP;
(
2
)
CSP: based on i, read hi and LAAIhi from its MHT Ψ;
(
3
)
send hi,LAAIhi to user;
(
4
)
User: compute rootT←CalRoot(hi,LAAIhi);
(
5
)
if
r
o
o
t
T
=
r
o
o
t
then
(
6
)
authorize CSP to execute delete operation;
(
7
)
end if
(
8
)
CSP:ifthe sibling node of hi, denoted by S, is a leaf node then
(
9
)
replace with S the parent node of hi which is transformed into a leaf node, and then delete hi from MHT Ψ;
(
10
)
else
S
is  a  parent  node
(
11
)
l
e
t
Ψ
S
denote  the  subtree  with  the  root  is
S
replace with ΨS the parent node of hi, and delete hi from MHT Ψ;
(
12
)
end if
(
13
)
update the MHT Ψ stored in cloud by recalculating all the nodes on the path from
S to the new root of MHT Ψ, denoted by root~∗;
(
14
)
delete bi, τi from the outsourced file F~, and send root~∗ to user;
(
15
)
User: set LAAIS←LAAIhi-S; noticeS∈LAAIhi
(
16
)
compute root∗←CalRoot(S,LAAIS);
(
17
)
if
r
o
o
t
∗
=
r
o
o
t
~
∗
then
(
18
)
transmit (delete,i) to TPA;
(
19
)
end if
(
20
)
TPA: update the MHT Ψ stored at TPA side by the same way as CSP;
(
21
)
send to user the root of the updated MHT Ψ, denoted by root̿∗;
(
22
)
User:ifroot∗=root̿∗then
(
23
)
update the root, stored in her local, with root∗;
(
24
)
end if
(
25
)
return
r
o
o
t
∗;


## 5. Experimental Evaluation

In this section, we simulate the computations of our proposed User Focus scheme and the Fortress scheme of [23] on the Inspur NF5270M4 servers with Intel Xeon CPU E5-2620 at 2.10 GHz, 16 GB RAM, and 7200 RPM 1 TB Serial ATA drive with a 32 MB buffer. Our experiments are implemented by using python language, and all the cryptographic functions are derived from the python cryptography toolkit [30]. We employ SHA1 to produce the 160 bit hash value, and the size of RSA module N is 1024 bit for security. As for the Fortress scheme, we also utilize the tools of bitcoin block explorer [31] to access bitcoin resource for obtaining the random challenges, and we typically set the sector size to be 1 KB (e.g., each 64 KB file block consists of 64 sectors in Fortress).Note that the typical block size for cloud storage is 64 KB–256 KB, as shown in [32]. Since outsourced auditing scheme runs above the cloud storage, the reasonable lower limit of block size should be no less than 64 KB. In our evaluation, user’s outsourced file is chosen to 1 GB. We do not measure the time of uploading the outsourced file from user to CSP, since this overhead is common to the two investigated schemes. Our statistical results are an average of 20 rounds.Firstly, user’s file must be preprocessed before outsourcing. Figure3 shows the required total time for the corresponding preprocessing phases of the two schemes. Furthermore, we also evaluate the computing time consumed by user for our scheme and Fortress, respectively. It turned out that for both schemes the computational overhead incurred at user side accounts for most of thetotal time when preprocessing the outsourced data, and the preprocessing performance of our scheme is orders of magnitude faster than of Fortress. As shown in [23], TPA needs to download the whole user’s file F from cloud and convince the user that he correctly preprocessed F. In this case Fortress requires user to carry out a time-consuming zero-knowledge-proof (ZKP) with TPA, resulting in the heavy computational overhead for user. Compared to Fortress, our User Focus scheme can effectively avoid such ZKP operation since TPA is not involved in preprocessing F and thus gain the performance enhancement.Figure 3
Comparison of time spent for preprocessing user’s outsourced file.Secondly, in Figure4, with respect to the different block sizes, we measure the latency incurred by performing TPA’s auditing against CSPonce in our scheme and in Fortress, respectively. In this experiment, we employ the same parameters as in [23]. During each outsourced auditing executed by TPA, the number of challenged blocks, denoted by lC, is set to 10% of the whole file blocks for both schemes. In addition, since Fortress involves the condition of parallel user-challenge, we also set the number of user-challenged blocks to be 10% of the TPA-challenged blocks as in [23] (i.e., 1% of the whole file blocks). The results show that during TPA’s auditing phase the performance of our scheme is slightly better than Fortress at 64 KB block level, and the latency of our scheme declines faster than that of Fortress as the block size increases.Figure 4
Latency for executing outsourced TPA’s auditing once with respect to the block size.Finally, we focus on evaluating the time incurred on the user when she audits a batch of TPA’s logs all at once. For a fair comparison, in this experiment we set the number of user-challenged blocks in Fortress to be the same as our User Focus scheme (i.e., each log refers to 10% of the whole blocks for user). As shown in Figure5, although the latency increases linearly in two schemes, the performance of our User Focus scheme is almost 5 times faster than that of Fortress. Recall that Fortress relies on bitcoin hash values to determine the challenges, so for reproducing each past challenge, user has to repeatedly interact with bitcoin random resource by sending the HTTP requests and receiving the responses to obtain all past bitcoin hash values, which incurs the noticeable delay as the number of accumulated logs increases since a TPA’s log is related to a past challenge. In our scheme, based on the property of User Focus, user can directly retrieve past challenges from her email box, which saves considerable time for reconstructing challenges when compared to Fortress. Note that each challenge of our scheme is only 88 bytes (8 bytes for the point-in-time t, 40 bytes for the two keys PRFt and PRPt, and 40 bytes for user’s signature), and user can delete all past accumulated challenges once her auditing against TPA is passed (as shown in Section 3.2.4); thus the storage and I/O costs of past challenges are extremely low for user in practice.Figure 5
Time spent by user for auditing TPA once with respect to the number of accumulated TPA’s logs. Here, block size is set to 64 KB that yields the most balanced performance over the two schemes when generating each log, as shown in Figure4.Summing up, for the phases of preprocessingand user’s auditing against TPA that involve the user, the experimental results present that our scheme greatly improves the performance of user side, so our scheme will provide a more pleasant user experience when compared to Fortress. In addition, our User Focus scheme achieves the same performance as Fortress for TPA’s auditing phases at the level of 64 KB block, or even better performance advantage at the bigger block level.


## 6. Related Work

With the popularization of storage outsourcing, the problem of remote data integrity auditing has attracted increasing attentions. All kinds of provable data possession (PDP) and proof of retrievability (POR) schemes [7–23] are proposed to defend against the untrusted remote server. Ateniese et al. provided a series of PDP schemes for the storage security of outsourced data. In [7], they first described the formalized definition of PDP and proposed the original PDP schemes by utilizing the homomorphic verifiable tags that are constructed based on the public key cryptological technique. Simultaneously, to allow anyone, not just the data owner, to audit the untrusted server for data possession, the concept of public auditing is first introduced in [7]. Whereafter, in terms of the symmetric key cryptological technique, Ateniese et al. [10] proposed another provably secure PDP scheme for considering the problems of scalability and data dynamics that are not covered in the original PDP method. Besides, in [11], they also presented two more efficient PDP schemes that go one step further than the original schemes of [7]. To support the fully dynamic operations in the context of remote auditing, Erway et al. [12] extended the PDP model of [7] and presented the first dynamic PDP scheme by using the rank-based authenticated skip list. In addition, Wang et al. [16] and Zhu et al. [19] also proposed other efficient dynamic schemes for public auditing, which are based on the data structures of Merkle Hash Tree (MHT) and Index-Hash Table (IHT), respectively.Juels and Kaliski Jr. [8] first proposed a formal POR model along with the corresponding security definitions. According to the model of [8], Shacham and Waters [9] constructed two POR schemes upon the static data storage but supporting the unlimited number of challenges. The first scheme is built from the pseudorandom functions to enable private auditing, and the second scheme with public auditing is built from the BLS signature [33]. Given that TPA might be curious during the process of public auditing, Wang et al. [13] integrated the random mask technique with the BLS-based public auditing scheme to prevent user’s outsourced data from leaking to TPA, and the scheme of [13] has been further improved to support data dynamics in [15]. Moreover, under the environment of public auditing, many other schemes are also designed to meet the demands of different scenarios, such as fast data error localization [17], the auditing against shared data [18], batch auditing for multiple clouds [20], fine-grained data updates [21], and the lightweight computations for low performance end devices [22].Recently a variety of cloud storage application schemes have been proposed, such as keyword-based data retrieval and image copy detection at cloud side. Xia et al. [34] constructed a special tree-based index structure and proposed a secure multikeyword ranked search scheme enabling dynamic updates upon outsourced encrypted data. Fu et al. [35] designed the parallel search algorithm and proposed another flexible searchable encryption scheme supporting both multikeyword ranked search and parallel search. In the setting of multikeyword fuzzy search, to solve the out-of-order problems during the ranking process, Fu et al. [36] also developed a new keyword transformation method and presented the corresponding efficient search scheme. In view of that traditional keyword-based search schemes that cannot completely match users’ search intention, the innovative semantic search scheme based on the concept hierarchy is proposed in [37], making the personalized search more effective and context-aware. And the content-based search scheme of [38] has further solved the problems of semantic search by utilizing the conceptual graphs and the efficient measure of “sentence scoring.” On the other hand, to protect the images stored in cloud, Xia et al. [39] proposed a privacy-preserving and copy-deterrence CBIR scheme using encryption and watermarking techniques, which can prevent the image user from illegally distributing the retrieved images. Li et al. [40] presented a solution to detect the copy-move forgery in an image, by first segmenting the targeted image into semantically independent patches prior to keypoint extraction and comparison. For detecting the image copies of a given original image generated by arbitrary rotation, Zhou et al. [41] proposed a novel copy detection method based on two global features extracted from rotation invariant partitions. In addition, Zhou et al. [42] designed a global context verification scheme to filter false matches for copy detection, which further addresses the problems of limited discriminability and quantization errors that exist in the bag-of-visual-words (BOW) model adopted by previous detection methods. However, since all application schemes mentioned above are designed upon the outsourced data of cloud storage, so it is obviously important for us to firstly focus on how to audit and confirm the integrity of remote outsourced data. But the existing public auditing schemes cannot protect against the malicious TPA. As shown in [23], malicious TPA is a potential security risk for outsourced data integrity and thus should not be ignored, which is the motivation of this paper.


## 7. Conclusion

Any public auditing/verification scheme can be transformed into a private scheme, just by making user perform the auditing work that should be delegated to TPA. Clearly, public auditing schemes might be more easily large-scale adopted by cloud users in practice, since user’s heavy burden incurred by frequently auditing can be transferred to TPA. Nevertheless, how to protect user from a malicious TPA is a key problem that is never considered by various existing public auditing schemes. The first outsourced auditing scheme Fortress is proposed to defend against the malicious TPA, but Fortress enables TPA to download all outsourced data and thus only relies on data encryption to protect user’s data privacy. A secure outsourced auditing scheme against malicious TPA should be designed to deprive TPA of the access rights over user’s outsourced data in cloud, which is achieved in this paper. Although our proposed scheme is designed without relying on additional independent random source, it also achieves the security of protecting against any malicious entity. In addition, based on the MHT data structure, we extend the outsourced auditing scheme to support dynamic updates. With the analysis and evaluations, our scheme is provably secure and significantly efficient.



---

*Source: 4603237-2017-11-27.xml*