# Security-Enhanced Certificate-Based Remote Data Integrity Batch Auditing for Cloud-IoT

Authors: Wenhao Wang; Yinxia Sun; Yumei Li
Journal: Security and Communication Networks
 (2022)

---

## Abstract

The Internet of Things (IoT) plays a crucial role in the generation of new, intelligent information technologies. Generally, the IoT facilities are composed of lightweight devices, and they expand computing and storage resources primarily through the cloud. Massive data collected by intelligent devices will be stored in cloud servers, but the vulnerabilities of cloud servers will directly threaten the security and reliability of the IoT. To ensure the integrity of data in the cloud, data owners need to audit the integrity of their outsourced data. Recently, several remote data integrity batch auditing protocols have been proposed to reduce transmission loss and time cost in the auditing process. However, most of them cannot resist collusion attacks. Meanwhile, certificate management problem exists in their system, which brings an enormous burden on the system. In this paper, we construct a certificate-based remote data integrity batch auditing protocol which can issue batch auditing and resist the highest level of collusion attacks—the fully chosen-key attacks for cloud-IoT . Our protocol makes use of a certificate-based cryptosystem which gets rid of the certificate management problem and key escrow problem, with no need for secret channels. Our protocol is proved to be secure in the random oracle model and implemented to show its efficiency. The simulation results illustrate that, in the case of enhanced security, our batch auditing protocol still has computational efficiency and practicability.


---

## Body

## 1. Introduction

### 1.1. Background and Motivation

With the introduction and application of new concepts and technologies such as smart cities, virtual sports, and the Metaverse, the number of devices connected to the Internet is increasing, requiring more powerful storage and processing resources. Fortunately, cloud services can provide data outsourcing storage services [1] for data owners (DOs), which are the devices in the IoT. By outsourcing data to a cloud server (CS), a DO is free from the burden of complex data management and huge storage. Meanwhile, a DO can access outsourced data in a network environment anytime and anywhere.While cloud storage and the IoT are convenient to people’s life, they bring some security concerns to the outsourced data [2]. One of the main security problems of cloud storage is the integrity of the outsourced data [3]. On the one hand, the CS is vulnerable to external attacks, resulting in the destruction of the outsourced data’s integrity. On the other hand, the IoT devices store data in the storage resources provided by a cloud service provider (CSP) who will maliciously tamper with the outsourced data in order to gain greater profits. If the data stored in the CS is tampered with or damaged, DOs may suffer considerable loss. Therefore, DOs are forced to audit the integrity of their outsourced data.The local data uploaded to the cloud will be deleted locally at the same time. In this case, the DO audits their own data integrity, which means that they need to download the data stored in the CS to the local server [4], and then locally audit the integrity of the data. It undoubtedly brings more trouble. Remote data integrity auditing (RDIA) can enable the DO to audit the integrity of cloud data and protect its interests without local backup. In practice, DOs prefer to hire a third-party auditor (TPA) to audit the integrity of their outsourced data.Because of the linearity of the linear homomorphic signature (LHS) [5], any linear combination of valid signatures can form a new valid signature. Thus, the LHS can be used to audit data integrity by random sampling. A TPA can sample random data blocks to audit data integrity without accessing the entire file. A basic RDIA process is shown in Figure 1. Firstly, a TPA gives a challenge to the CSP. Then, the CSP honestly generates a proof which is based on the LHS according to the challenge and returns it to the TPA. Finally, the TPA validates the proof and returns “accept” or “reject” to the DO. Note that the process of a TPA validating the proof is actually the process of verifying the linear homomorphic signature.Figure 1
A data integrity auditing model for cloud-IoT.To date, many RDIA protocols have been proposed and the vast majority of them only support auditing data from a single DO in a single auditing process. Let us imagine a scenario. If a TPA needs to audit the data of multiple DOs, it needs to interact with the CSP many times, which is undoubtedly inefficient and highly risky in the complex network environment. Batch auditing [6] is an efficient auditing technique, which enables the TPA to complete multiple data auditing tasks with only one interaction with the CSP. When a TPA needs to audit the data integrity of multiple DOs, it will first prepare a set of challenges and send them to the CSP. After receiving these challenges, the CSP will generate and send a batch proof to the TPA. Passing the inspection of the TPA means that the integrity of the data associated with the set of challenges has not been compromised. In this way, the interaction between the TPA and the CSP is only once.The initial remote data integrity batch auditing (RDIBA) protocols [6, 7] are based on a traditional public key cryptosystem. Although this cryptosystem has been broadly applied in practice, it still faces the problem of public key certificate management, which brings heavy burden to the system. In order to avoid this weakness, an identity-based cryptosystem (IBC) [8] is used to build RDIBA protocols. However, key escrow is an intrinsic defect of the IBC. Therefore, the identity-based RDIBA protocols have certain limitations which are only applied to small, closed systems rather than to RDIA. A certificateless cryptosystem (CLC) [9] is beneficial to address the weaknesses of the public key certificate management and key escrow, simultaneously. Nevertheless, it is necessary for the CLC to construct a costly, secure, and secret channel for each DO to send the partial private key, which is tricky. In order to overcome the shortcomings, we use a certificate-based cryptosystem (CBC) first introduced in [10] to form our protocol. The CBC requires no certificate management, key escrow, secure channels, and a fully trusted authorization, and hence it can be easily deployed in the public environment of cloud-IoT. In recent years, a number of RDIBA protocols have been proposed. Unfortunately, the vast majority of them cannot prevent collusion attacks. It means that the CSP can be tricked by multiple DOs such that the DOs can claim compensations from the CSP.


### 1.2. Our Contributions

In this paper, a security-enhanced certificate-based remote data integrity batch auditing protocol that can resist the highest level of collusion attacks is proposed. The main contributions of our paper can be summarized as follows:(1)
We propose the formal definition and security model of the certificate-based remote data integrity batch auditing (CBRDIBA) protocol according to cloud-IoT.(2)
We give a secure protocol that can prevent the current highest level of collusion attacks. And we offer four games to analyse the security of our protocol in the random oracle model.(3)
We compare batch auditing with single auditing in terms of the communication cost and the computation cost in our protocol in theory, and simulate their performance through experiments by Java pairing-based cryptography library. The simulation results illustrate that, although our protocol is security-enhanced, our batch auditing protocol remains computationally efficient and practical.


### 1.3. The Organization of the Rest Paper

The rest of our paper is structured as follows. In Section2, we review some previous work associated with the CBRDIBA protocol. Next, in Section 3, we give some preliminaries used as the basis for the CBRDIBA protocol and present the problem formulations including the system model, an overview of the CBRDIBA protocol, and the security model. Then, we demonstrate the concrete construction of the CBRDIBA protocol in section 4, and analyze the properties of the CBRDIBA protocol in Section 5. In Section 6, we demonstrate the superiority of the CBRDIBA protocol through theoretical analysis and experiments. Finally, we draw conclusions in Section 7.


## 1.1. Background and Motivation

With the introduction and application of new concepts and technologies such as smart cities, virtual sports, and the Metaverse, the number of devices connected to the Internet is increasing, requiring more powerful storage and processing resources. Fortunately, cloud services can provide data outsourcing storage services [1] for data owners (DOs), which are the devices in the IoT. By outsourcing data to a cloud server (CS), a DO is free from the burden of complex data management and huge storage. Meanwhile, a DO can access outsourced data in a network environment anytime and anywhere.While cloud storage and the IoT are convenient to people’s life, they bring some security concerns to the outsourced data [2]. One of the main security problems of cloud storage is the integrity of the outsourced data [3]. On the one hand, the CS is vulnerable to external attacks, resulting in the destruction of the outsourced data’s integrity. On the other hand, the IoT devices store data in the storage resources provided by a cloud service provider (CSP) who will maliciously tamper with the outsourced data in order to gain greater profits. If the data stored in the CS is tampered with or damaged, DOs may suffer considerable loss. Therefore, DOs are forced to audit the integrity of their outsourced data.The local data uploaded to the cloud will be deleted locally at the same time. In this case, the DO audits their own data integrity, which means that they need to download the data stored in the CS to the local server [4], and then locally audit the integrity of the data. It undoubtedly brings more trouble. Remote data integrity auditing (RDIA) can enable the DO to audit the integrity of cloud data and protect its interests without local backup. In practice, DOs prefer to hire a third-party auditor (TPA) to audit the integrity of their outsourced data.Because of the linearity of the linear homomorphic signature (LHS) [5], any linear combination of valid signatures can form a new valid signature. Thus, the LHS can be used to audit data integrity by random sampling. A TPA can sample random data blocks to audit data integrity without accessing the entire file. A basic RDIA process is shown in Figure 1. Firstly, a TPA gives a challenge to the CSP. Then, the CSP honestly generates a proof which is based on the LHS according to the challenge and returns it to the TPA. Finally, the TPA validates the proof and returns “accept” or “reject” to the DO. Note that the process of a TPA validating the proof is actually the process of verifying the linear homomorphic signature.Figure 1
A data integrity auditing model for cloud-IoT.To date, many RDIA protocols have been proposed and the vast majority of them only support auditing data from a single DO in a single auditing process. Let us imagine a scenario. If a TPA needs to audit the data of multiple DOs, it needs to interact with the CSP many times, which is undoubtedly inefficient and highly risky in the complex network environment. Batch auditing [6] is an efficient auditing technique, which enables the TPA to complete multiple data auditing tasks with only one interaction with the CSP. When a TPA needs to audit the data integrity of multiple DOs, it will first prepare a set of challenges and send them to the CSP. After receiving these challenges, the CSP will generate and send a batch proof to the TPA. Passing the inspection of the TPA means that the integrity of the data associated with the set of challenges has not been compromised. In this way, the interaction between the TPA and the CSP is only once.The initial remote data integrity batch auditing (RDIBA) protocols [6, 7] are based on a traditional public key cryptosystem. Although this cryptosystem has been broadly applied in practice, it still faces the problem of public key certificate management, which brings heavy burden to the system. In order to avoid this weakness, an identity-based cryptosystem (IBC) [8] is used to build RDIBA protocols. However, key escrow is an intrinsic defect of the IBC. Therefore, the identity-based RDIBA protocols have certain limitations which are only applied to small, closed systems rather than to RDIA. A certificateless cryptosystem (CLC) [9] is beneficial to address the weaknesses of the public key certificate management and key escrow, simultaneously. Nevertheless, it is necessary for the CLC to construct a costly, secure, and secret channel for each DO to send the partial private key, which is tricky. In order to overcome the shortcomings, we use a certificate-based cryptosystem (CBC) first introduced in [10] to form our protocol. The CBC requires no certificate management, key escrow, secure channels, and a fully trusted authorization, and hence it can be easily deployed in the public environment of cloud-IoT. In recent years, a number of RDIBA protocols have been proposed. Unfortunately, the vast majority of them cannot prevent collusion attacks. It means that the CSP can be tricked by multiple DOs such that the DOs can claim compensations from the CSP.


## 1.2. Our Contributions

In this paper, a security-enhanced certificate-based remote data integrity batch auditing protocol that can resist the highest level of collusion attacks is proposed. The main contributions of our paper can be summarized as follows:(1)
We propose the formal definition and security model of the certificate-based remote data integrity batch auditing (CBRDIBA) protocol according to cloud-IoT.(2)
We give a secure protocol that can prevent the current highest level of collusion attacks. And we offer four games to analyse the security of our protocol in the random oracle model.(3)
We compare batch auditing with single auditing in terms of the communication cost and the computation cost in our protocol in theory, and simulate their performance through experiments by Java pairing-based cryptography library. The simulation results illustrate that, although our protocol is security-enhanced, our batch auditing protocol remains computationally efficient and practical.


## 1.3. The Organization of the Rest Paper

The rest of our paper is structured as follows. In Section2, we review some previous work associated with the CBRDIBA protocol. Next, in Section 3, we give some preliminaries used as the basis for the CBRDIBA protocol and present the problem formulations including the system model, an overview of the CBRDIBA protocol, and the security model. Then, we demonstrate the concrete construction of the CBRDIBA protocol in section 4, and analyze the properties of the CBRDIBA protocol in Section 5. In Section 6, we demonstrate the superiority of the CBRDIBA protocol through theoretical analysis and experiments. Finally, we draw conclusions in Section 7.


## 2. Related Work

In the cloud-IoT environment, RDIA provides a fundamental solution to audit the integrity of data according to homomorphic verifiable tags (HVTs), which are some homomorphic signatures of the data blocks. The concept of homomorphic signature was first proposed by Rivest in 2000 [11]. It can be divided into linear homomorphic signature, polynomial function homomorphic signature, and fully homomorphic signature. In 2007, Zhao et al. [12] proposed the first linear homomorphic signature (LHS) scheme that allows the arbitrary linear combination of the signature, which can be used to easily audit the integrity of the received data. However, their scheme has been proven to be unsafe and impractical. In the same year, Ateniese et al. [13] first presented a provable data possession model and initially introduced the technique of probabilistic integrity checking for the remote data.In 2009, Boneh et al. [5] proposed a LHS scheme that gives the first formal definition of the LHS scheme. In the following years, a large number of LHS schemes have been proposed, which have been further improved in terms of efficiency, privacy, and security. In 2015, Yu et al. [14] suggested an identity-based LHS scheme. The disadvantages of using public key certificates are avoided by adding the identity-based feature. In 2018, Li et al. [15] used a certificateless LHS signature scheme to construct a certificateless public data integrity auditing protocol for data shared among a group. In 2021, Li et al. [16] constructed a data integrity auditing protocol for cloud-assisted wireless body area networks using certificate-based LHS. Their protocol adds timestamps to the HVTs such that adversaries cannot use the expired valid proof to pretend to be the current ones. In 2022, Li et al. [17] introduced a concept of transparent integrity auditing which can keep the CS from misbehaving (i.e., procrastinating auditing).All the above LHS schemes are constructed in single-user scenarios, and all the signatures entered in the algorithm are produced using the same private key. In real life, there are many application scenarios with multi-users. In these scenarios, a newly generated signature is aggregated from signatures generated by different DOs using their private keys. For these scenarios, an aggregate signature (AS) scheme can be used. The first AS scheme and its formal definition were proposed by [18]. As time went by, identity-based AS [19], certificateless AS [20], and certificate-based AS [21] were gradually proposed. In AS, a problem worth paying attention to is the fully chosen-key attacks [22], which were first proposed by Wu et al. in 2019. The fully chosen-key attacks are currently the most difficult collusion attacks to defend against.As time progressed, AS were gradually combined with LHS. The first linear homomorphic aggregate signature (LHAS) was put forward by Jing [23] in 2014, which supports linear operations on binary domains. Its security is based on the small integer solution problem [24]. In 2018, Han et al. [25] proposed an efficient error search technique called Lucas search, which is based on the Lucas sequence [26], to efficiently search the corrupted data files once the batch auditing task fails. In 2019, Wang et al. [27] used a certificate-based cryptosystem to construct a data integrity auditing protocol in which they mentioned that their scheme can perform batch auditing. Although their protocol can perform batch auditing and has used a CBC, it cannot prevent collusion attacks. In 2019, Yang et al. [28] constructed a data integrity batch auditing protocol that can work in multi-cloud storage. In 2020, Huang et al. [29] applied the CLC to RDIBA and proposed a certificateless remote data integrity batch auditing protocol. However, most of the above protocols are not resistant to collusion attacks let alone the fully chosen-key attacks.


## 3. System Model and Objectives

### 3.1. Preliminaries

Definition 1 (Bilinear Pairing).
LetG1,G2,GT denote three multiplicative groups of the same order q. Let g1 be a generator of G1 and let g2 be a generator of G2. e:G1×G2⟶GT is a bilinear mapping with following properties:(1)
Bilinearity:eg1a1,g2a2=eg1,g2a1a2 for any a1,a2∈ℤq and g1∈G1,g2∈G2.(2)
Non-degeneracy: ifg1 is a generator of G1 and g2 is a generator of G2, then eg1,g2 is a generator of GT.(3)
Computability: for anyg1∈G1 and g2∈G2, eg1,g2 is a generator of GT.


#### 3.1.1. Co-Computational Diffie-Hellman Problem (co-CDH)

LetG1,G2 be two cyclic groups of the same prime order q. g1 is a generator of G1 and g2 is a generator of G2; for random a∈ℤq∗, given g1,g2,g2a, compute g1a.


#### 3.1.2. Co-CDH Problem Assumption

We say that the co-CDH assumption holds inG1 and G2 if the advantage is negligible in solving the co-CDH problem for any probabilistic polynomial-time algorithm.


#### 3.1.3. k-Collusion Attack Algorithm Problem (k-CAA)

SupposeG1 and G2 are two cyclic groups with sizable prime q, a,h1,…,hk∈ℤq∗ are k+1 integers. Given g1∈G1,gia∈Gii=1,2, and k pairs h1,g1a+h1−1,…,hk,g1a+hk−1 output a new pair h∗,g1a+h∗−1 for some h∗∉h1,…,hk.


#### 3.1.4. k-CAA Problem Assumption

We say that the k-CAA assumption holds inG1 and G2 if the advantage is negligible in solving the k-CAA problem for any probabilistic polynomial-time algorithm.


### 3.2. The RDIBA System Model

We raise a RDIBA system where the TPA validates timestamps and the integrity of multiple datasets. The system is composed of three kinds of entities: data owners (DOs), cloud service provider (CSP), and third-party auditor (TPA). As the clients of the CSP, the DOs upload their datasets to the CSP and then delete them locally. The DOs are foxy. Two or more data owners may negotiate with each other to generate tags for their own data blocks using each other’s private keys. In this case, the TPA will respond “accept,” even if the single auditing information is not right. After that, the data owners will extort compensation from the CSP. The CSP is honest but curious. Although the CSP will honestly generate proofs, as the certification authority of the system, it can embed trapdoors in the system parameters to achieve the purpose of forging a valid signature without owning the user’s private key. As the system user, the TPA can have access to the datasets and validate the data integrity. Figure2 shows the system model and the process is elaborated as follows:(1)
Every DO generates timestamps and tags for data blocks that come from the collected dataset. The DOs then upload these data blocks with the related auditing information (such as all tags of data blocks, the label of the dataset, timestamp, and the number of data blocks) to the CS and delete them locally.(2)
The TPA can obtain the auditing information from the CSP, and then generate and send one or more challenges to the CSP. On receiving a challenge or a set of challenges, the CSP will generate a proof or a batch proof and then return it to the TPA.(3)
The TPA will validate the authenticity and correctness of the proof or the batch proof and output “accept” or “reject.” If the proof or the batch proof passes the verification, the corresponding one or multiple datasets stored in the CSP are considered to be secure.Figure 2
A remote data integrity batch auditing system model.When a TPA issues multiple challenges, the CSP only needs to interact with the TPA once because the TPA validates batch proof, which means it validates all corresponding proofs. There is no doubt that a lot of data transmission loss is saved.


#### 3.2.1. System Components

A RDIBA system modelΩ = (System Setup, User Registration, Outsourcing Storage, Auditing, Batch Auditing) is an interactive protocol allowing a third party (i.e., TPA) to validate that files are stored truthfully.(i)
System Setup: The CSP initializes a data integrity auditing system. After generating the system master private keymsk, the CSP publishes the system parameters params.(ii)
User Registration: The DO generates public/private key pairupkID,uskID and provides the CSP with its public key upkID. The CSP returns a verifiable certificate CertID to the TPA.(iii)
Outsourcing Storage: On receiving an encoded datasetF=m1,…,mk named ds and a timestamp t, the DO uploads the encoded dataset F, label τ, and tags σi of data blocks to the CS.(iv)
Auditing: The TPA provides the CSP with a challengechal by sampling some data blocks. And then according to the challenge, the CSP generates a proof PF and returns it to the TPA. Next, on receiving a valid proof PF, the TPA outputs “accept.” Otherwise, it outputs “reject.” Outputting “Accept” also means that the dataset is stored in the CS intactly and honestly.(v)
Batch Auditing: The TPA provides the CSP with challengeschalz,z=1,…,l,l≤L (As shown in Figure 2, L indicates the total number of data owners in the system) by sampling some data blocks. And then according to the challenges, the CSP generates a batch proof and returns it to the TPA. Next, on receiving a valid proof PF, the TPA outputs “accept.” Otherwise, it outputs “reject.” Outputting “Accept” also means that multiple corresponding datasets are stored in the CS intactly and honestly.


### 3.3. Design Objectives

Our protocol is designed to achieve the following objectives:(i)
Correctness of Auditing: The CSP cannot generate the valid proofs without preserving the entire original dataset and timestamp.(ii)
Correctness of Batch Auditing: The batch proof is valid, if and only if every individual proof used in the Batch Proof Generation algorithm is valid.(iii)
Batch Auditing: The TPA can perform batch auditing. Note that batch auditing means that the TPA only needs to interact with the CSP once.(iv)
Anonymity: In our protocol, only the DO and the CSP can know the real identityRID of the DO. Any other entity like a TPA can only know the pseudonym ID of the DO.(v)
Verifiability: The TPA can validate the integrity of files by sampling some random data blocks with no access to the entire files.(vi)
Security: To ensure the correctness and integrity of the data, a secure CBRDIBA protocol should resist the following attacks: (1) The system user (or CSP) can forge a tag of a data block. (2) The CSP can replace the new challenge response with the expired valid proof to deceive the DO. (3) Two or more data owners can use each other’s private key to forge invalid tags which cannot pass the verification, but their batch proof can pass the batch proof verification.The security model can be defined using the following four games between adversariesAI, AII, AIII, AIV and challenger ℬ. The goal of the adversaries AI, AII, and AIII is to forge a valid single proof. AIV aims to forge a valid batch proof.Among them,AI is an outside attacker (hostile DO) who wants to forge a tag of data block in order to outsmart the TPA. AII is an inside attacker (honest but curious CSP) who is more inclined to defend itself when mistakes occur. It can hold some system information (such as the system master private key) that the DO does not have.We can go to the literature [16] and read the attack models (Game I and Game II).AIII models the ability of the CSP to forge a valid proof, and attempts to generate a valid proof when some data blocks are damaged. The adversary game of AIII is as follows.Game III (Type III adversaryAIII):(i)
System Initialization: On inputting a security parameter1λ, ℬ runs System Setup to generate public parameters params and system master private key msk, and sends params to AIII.(ii)
Oracle Simulation:AIII can adaptively make TagGen Queries and ProofCheck Queries.(iii)
Challenge:ℬ generates a challenge chal and sends it to AIII. On receiving chal, AIII generates a proof PF and returns it to ℬ.(iv)
Forge:AIII outputs ID∗,upkID∗,τ∗,chal∗,PF∗. AIII wins the game if the following conditions are satisfied:(1)
ProofPF=m∗,σ∗ can pass the algorithm Proof Verification, where m∗∉F.(2)
There is at least one challenged data block that has never been issued a TagGen Queries.In our protocol, we consider the DO can be dodgy and that two or more data owners may cheat the TPA and the CSP for profit. We simulate these data owners as adversaryAIV. The purpose of AIV is to use a set of single proofs to generate a valid batch proof with at least one invalid single proof. The adversary AIV can do the fully chosen-key attacks. Now we revisit the security model in [22] through the following game between an adversary AIV and a challenger ℬ. The Game IV consists of three steps: System Initialization, Oracle Simulation, and Forge. The adversary game of AIV is as follows.Game IV (Type IV adversaryAIV):System Initialization: Inputting the security parameterλ, the challenger ℬ generates the system parameters params. Furthermore, ℬ randomly generates the public-secret key pair upkver,uskver for the TPA, and then ℬ gives AIV the params and upkver.Oracle Simulation:AIV can access the following queries:(i)
Corruption Queries:AIV requests such a query, and ℬ generates the key pairs upkIDz,uskIDz by running the algorithm UserkeyGen, and then returns uskIDz to AIV.(ii)
Batch Proof Check Queries: The simulatorℬ generates some challenges and sends the challenges to AIV. Then, on receiving the challenges from ℬ, AIV generates a batch proof BPF and returns it to ℬ. Finally, ℬ verifies BPF by running the algorithm Batch Proof Verification and gives the result to AIV.Forge: Finally,AIV outputs its forgery. If the following two conditions are satisfied, AIV wins the game:(1)
The batch proof is generated from all the single proofs.(2)
The batch proofσ∗ is valid.(3)
At least one single proof of the batch proof is invalid.Definition 2.
A CBRDIBA protocol is secure if the advantage of the adversariesAI, AII, AIII, and AIV winning game I, game II, game III, and game IV in probabilistic polynomial time (PPT) is negligible, respectively.


## 3.1. Preliminaries

Definition 1 (Bilinear Pairing).
LetG1,G2,GT denote three multiplicative groups of the same order q. Let g1 be a generator of G1 and let g2 be a generator of G2. e:G1×G2⟶GT is a bilinear mapping with following properties:(1)
Bilinearity:eg1a1,g2a2=eg1,g2a1a2 for any a1,a2∈ℤq and g1∈G1,g2∈G2.(2)
Non-degeneracy: ifg1 is a generator of G1 and g2 is a generator of G2, then eg1,g2 is a generator of GT.(3)
Computability: for anyg1∈G1 and g2∈G2, eg1,g2 is a generator of GT.


### 3.1.1. Co-Computational Diffie-Hellman Problem (co-CDH)

LetG1,G2 be two cyclic groups of the same prime order q. g1 is a generator of G1 and g2 is a generator of G2; for random a∈ℤq∗, given g1,g2,g2a, compute g1a.


### 3.1.2. Co-CDH Problem Assumption

We say that the co-CDH assumption holds inG1 and G2 if the advantage is negligible in solving the co-CDH problem for any probabilistic polynomial-time algorithm.


### 3.1.3. k-Collusion Attack Algorithm Problem (k-CAA)

SupposeG1 and G2 are two cyclic groups with sizable prime q, a,h1,…,hk∈ℤq∗ are k+1 integers. Given g1∈G1,gia∈Gii=1,2, and k pairs h1,g1a+h1−1,…,hk,g1a+hk−1 output a new pair h∗,g1a+h∗−1 for some h∗∉h1,…,hk.


### 3.1.4. k-CAA Problem Assumption

We say that the k-CAA assumption holds inG1 and G2 if the advantage is negligible in solving the k-CAA problem for any probabilistic polynomial-time algorithm.


## 3.1.1. Co-Computational Diffie-Hellman Problem (co-CDH)

LetG1,G2 be two cyclic groups of the same prime order q. g1 is a generator of G1 and g2 is a generator of G2; for random a∈ℤq∗, given g1,g2,g2a, compute g1a.


## 3.1.2. Co-CDH Problem Assumption

We say that the co-CDH assumption holds inG1 and G2 if the advantage is negligible in solving the co-CDH problem for any probabilistic polynomial-time algorithm.


## 3.1.3. k-Collusion Attack Algorithm Problem (k-CAA)

SupposeG1 and G2 are two cyclic groups with sizable prime q, a,h1,…,hk∈ℤq∗ are k+1 integers. Given g1∈G1,gia∈Gii=1,2, and k pairs h1,g1a+h1−1,…,hk,g1a+hk−1 output a new pair h∗,g1a+h∗−1 for some h∗∉h1,…,hk.


## 3.1.4. k-CAA Problem Assumption

We say that the k-CAA assumption holds inG1 and G2 if the advantage is negligible in solving the k-CAA problem for any probabilistic polynomial-time algorithm.


## 3.2. The RDIBA System Model

We raise a RDIBA system where the TPA validates timestamps and the integrity of multiple datasets. The system is composed of three kinds of entities: data owners (DOs), cloud service provider (CSP), and third-party auditor (TPA). As the clients of the CSP, the DOs upload their datasets to the CSP and then delete them locally. The DOs are foxy. Two or more data owners may negotiate with each other to generate tags for their own data blocks using each other’s private keys. In this case, the TPA will respond “accept,” even if the single auditing information is not right. After that, the data owners will extort compensation from the CSP. The CSP is honest but curious. Although the CSP will honestly generate proofs, as the certification authority of the system, it can embed trapdoors in the system parameters to achieve the purpose of forging a valid signature without owning the user’s private key. As the system user, the TPA can have access to the datasets and validate the data integrity. Figure2 shows the system model and the process is elaborated as follows:(1)
Every DO generates timestamps and tags for data blocks that come from the collected dataset. The DOs then upload these data blocks with the related auditing information (such as all tags of data blocks, the label of the dataset, timestamp, and the number of data blocks) to the CS and delete them locally.(2)
The TPA can obtain the auditing information from the CSP, and then generate and send one or more challenges to the CSP. On receiving a challenge or a set of challenges, the CSP will generate a proof or a batch proof and then return it to the TPA.(3)
The TPA will validate the authenticity and correctness of the proof or the batch proof and output “accept” or “reject.” If the proof or the batch proof passes the verification, the corresponding one or multiple datasets stored in the CSP are considered to be secure.Figure 2
A remote data integrity batch auditing system model.When a TPA issues multiple challenges, the CSP only needs to interact with the TPA once because the TPA validates batch proof, which means it validates all corresponding proofs. There is no doubt that a lot of data transmission loss is saved.


### 3.2.1. System Components

A RDIBA system modelΩ = (System Setup, User Registration, Outsourcing Storage, Auditing, Batch Auditing) is an interactive protocol allowing a third party (i.e., TPA) to validate that files are stored truthfully.(i)
System Setup: The CSP initializes a data integrity auditing system. After generating the system master private keymsk, the CSP publishes the system parameters params.(ii)
User Registration: The DO generates public/private key pairupkID,uskID and provides the CSP with its public key upkID. The CSP returns a verifiable certificate CertID to the TPA.(iii)
Outsourcing Storage: On receiving an encoded datasetF=m1,…,mk named ds and a timestamp t, the DO uploads the encoded dataset F, label τ, and tags σi of data blocks to the CS.(iv)
Auditing: The TPA provides the CSP with a challengechal by sampling some data blocks. And then according to the challenge, the CSP generates a proof PF and returns it to the TPA. Next, on receiving a valid proof PF, the TPA outputs “accept.” Otherwise, it outputs “reject.” Outputting “Accept” also means that the dataset is stored in the CS intactly and honestly.(v)
Batch Auditing: The TPA provides the CSP with challengeschalz,z=1,…,l,l≤L (As shown in Figure 2, L indicates the total number of data owners in the system) by sampling some data blocks. And then according to the challenges, the CSP generates a batch proof and returns it to the TPA. Next, on receiving a valid proof PF, the TPA outputs “accept.” Otherwise, it outputs “reject.” Outputting “Accept” also means that multiple corresponding datasets are stored in the CS intactly and honestly.


## 3.2.1. System Components

A RDIBA system modelΩ = (System Setup, User Registration, Outsourcing Storage, Auditing, Batch Auditing) is an interactive protocol allowing a third party (i.e., TPA) to validate that files are stored truthfully.(i)
System Setup: The CSP initializes a data integrity auditing system. After generating the system master private keymsk, the CSP publishes the system parameters params.(ii)
User Registration: The DO generates public/private key pairupkID,uskID and provides the CSP with its public key upkID. The CSP returns a verifiable certificate CertID to the TPA.(iii)
Outsourcing Storage: On receiving an encoded datasetF=m1,…,mk named ds and a timestamp t, the DO uploads the encoded dataset F, label τ, and tags σi of data blocks to the CS.(iv)
Auditing: The TPA provides the CSP with a challengechal by sampling some data blocks. And then according to the challenge, the CSP generates a proof PF and returns it to the TPA. Next, on receiving a valid proof PF, the TPA outputs “accept.” Otherwise, it outputs “reject.” Outputting “Accept” also means that the dataset is stored in the CS intactly and honestly.(v)
Batch Auditing: The TPA provides the CSP with challengeschalz,z=1,…,l,l≤L (As shown in Figure 2, L indicates the total number of data owners in the system) by sampling some data blocks. And then according to the challenges, the CSP generates a batch proof and returns it to the TPA. Next, on receiving a valid proof PF, the TPA outputs “accept.” Otherwise, it outputs “reject.” Outputting “Accept” also means that multiple corresponding datasets are stored in the CS intactly and honestly.


## 3.3. Design Objectives

Our protocol is designed to achieve the following objectives:(i)
Correctness of Auditing: The CSP cannot generate the valid proofs without preserving the entire original dataset and timestamp.(ii)
Correctness of Batch Auditing: The batch proof is valid, if and only if every individual proof used in the Batch Proof Generation algorithm is valid.(iii)
Batch Auditing: The TPA can perform batch auditing. Note that batch auditing means that the TPA only needs to interact with the CSP once.(iv)
Anonymity: In our protocol, only the DO and the CSP can know the real identityRID of the DO. Any other entity like a TPA can only know the pseudonym ID of the DO.(v)
Verifiability: The TPA can validate the integrity of files by sampling some random data blocks with no access to the entire files.(vi)
Security: To ensure the correctness and integrity of the data, a secure CBRDIBA protocol should resist the following attacks: (1) The system user (or CSP) can forge a tag of a data block. (2) The CSP can replace the new challenge response with the expired valid proof to deceive the DO. (3) Two or more data owners can use each other’s private key to forge invalid tags which cannot pass the verification, but their batch proof can pass the batch proof verification.The security model can be defined using the following four games between adversariesAI, AII, AIII, AIV and challenger ℬ. The goal of the adversaries AI, AII, and AIII is to forge a valid single proof. AIV aims to forge a valid batch proof.Among them,AI is an outside attacker (hostile DO) who wants to forge a tag of data block in order to outsmart the TPA. AII is an inside attacker (honest but curious CSP) who is more inclined to defend itself when mistakes occur. It can hold some system information (such as the system master private key) that the DO does not have.We can go to the literature [16] and read the attack models (Game I and Game II).AIII models the ability of the CSP to forge a valid proof, and attempts to generate a valid proof when some data blocks are damaged. The adversary game of AIII is as follows.Game III (Type III adversaryAIII):(i)
System Initialization: On inputting a security parameter1λ, ℬ runs System Setup to generate public parameters params and system master private key msk, and sends params to AIII.(ii)
Oracle Simulation:AIII can adaptively make TagGen Queries and ProofCheck Queries.(iii)
Challenge:ℬ generates a challenge chal and sends it to AIII. On receiving chal, AIII generates a proof PF and returns it to ℬ.(iv)
Forge:AIII outputs ID∗,upkID∗,τ∗,chal∗,PF∗. AIII wins the game if the following conditions are satisfied:(1)
ProofPF=m∗,σ∗ can pass the algorithm Proof Verification, where m∗∉F.(2)
There is at least one challenged data block that has never been issued a TagGen Queries.In our protocol, we consider the DO can be dodgy and that two or more data owners may cheat the TPA and the CSP for profit. We simulate these data owners as adversaryAIV. The purpose of AIV is to use a set of single proofs to generate a valid batch proof with at least one invalid single proof. The adversary AIV can do the fully chosen-key attacks. Now we revisit the security model in [22] through the following game between an adversary AIV and a challenger ℬ. The Game IV consists of three steps: System Initialization, Oracle Simulation, and Forge. The adversary game of AIV is as follows.Game IV (Type IV adversaryAIV):System Initialization: Inputting the security parameterλ, the challenger ℬ generates the system parameters params. Furthermore, ℬ randomly generates the public-secret key pair upkver,uskver for the TPA, and then ℬ gives AIV the params and upkver.Oracle Simulation:AIV can access the following queries:(i)
Corruption Queries:AIV requests such a query, and ℬ generates the key pairs upkIDz,uskIDz by running the algorithm UserkeyGen, and then returns uskIDz to AIV.(ii)
Batch Proof Check Queries: The simulatorℬ generates some challenges and sends the challenges to AIV. Then, on receiving the challenges from ℬ, AIV generates a batch proof BPF and returns it to ℬ. Finally, ℬ verifies BPF by running the algorithm Batch Proof Verification and gives the result to AIV.Forge: Finally,AIV outputs its forgery. If the following two conditions are satisfied, AIV wins the game:(1)
The batch proof is generated from all the single proofs.(2)
The batch proofσ∗ is valid.(3)
At least one single proof of the batch proof is invalid.Definition 2.
A CBRDIBA protocol is secure if the advantage of the adversariesAI, AII, AIII, and AIV winning game I, game II, game III, and game IV in probabilistic polynomial time (PPT) is negligible, respectively.


## 4. A CBRDIBA Protocol

Based on the construction of homomorphic verifiable tags in [16], we design a security-enhanced CBRDIBA protocol which is composed of five procedures: System Setup, User Registration, Outsourcing Storage, Auditing, and Batch Auditing. The notations used in this section are shown in Table 1.Table 1
Notations and descriptions.
NotationDescriptionsλSecurity parameterPFA single proofBPFA batch proofchalzThez-th challenge at one auditingIA subset selected by the TPAFA datasetdsThe name of a datasetτThe label of a datasetmi,i∈1,kThe data blocks of one datasetσi,i∈1,kThe tags of related data blocks in a datasettA timestampIDzThe pseudonym of userzRIDzThe real identity of userzupkverThe public key of the TPAuskverThe private key of the TPA


### 4.1. System Setup

Given a security parameterλ, the CSP does:(i)
Generate a bilinear groupG1,G2,GT,q,e, where q>2λ, G1,G2,GT are three multiplicative cyclic groups with the same prime order q. Bilinear pairing e:G1×G2⟶GT. Isomorphic mapping ψ:G2⟶G1.(ii)
Generate a generatorg1 in G1 and a generator g2 in G2.(iii)
LetH0:0,1∗⟶ℤq∗, H1:0,1∗×G2⟶G1, H2:0,1∗×0,1∗×G1⟶ℤq∗, H3:0,1∗×ℤn∗×G1⟶ℤq∗, and H4:G2⟶0,1∗ be five collision resistant hash functions.(iv)
Randomly chooses∈ℤq∗ as the master private key, and the master public key is mpk=g2s.The CSP publishes the system parametersparams=q,G1,G2,GT,e,ψ,g1,g2,mpk,H0,H1,H2,H3,H4 and keeps the system master private key msk=s secret.


### 4.2. User Registration

The user registration process is composed of three phases.(i)
Phase 1 (UserKeyGen): Given the system parametersparams and the user’s real identity RID, the user does:(1)
Randomly choosex∈ℤq∗ as the user’s secret key which is denoted by uskID. Generate the user’s pseudonym by computing ID=RID⊕H4mpkuskID.(2)
ComputeupkID=g2x as the user’s public key.(ii)
Phase 2 (Certify): Given the system parameterparams, master private key msk, the user’s public key upkID with ID, the CSP generates the certificate CertID=H1ID,upkIDs for the user ID and sends it to the user.(iii)
Phase 3 (Authentication): The userID validates the certificate. If the equation(1)eCertID,g2=eH1ID,upkID,mpk,holds, then the user succeeds in logging into the system.


### 4.3. Outsourcing Storage

The outsourcing storage procedure is composed of two phases: Data Processing and Data Upload.(i)
Phase 1 (Data Processing):(1)
Given an encrypted datasetF∈0,1∗ named ds, the DO splits the dataset into k data blocks m1,m2,…,mk, and each block comprises n sectors, i.e., F=mi,jk×n(2)
The DO randomly choosesα∈ℤq∗, and then computes β=g2α and τ0=CertID1/uskID+H2ID,ds,t,β. The DO sets τ=τ0,β,ds,t,k,n as the label of the dataset.(3)
For eachmi,i∈1,k, the DO computes tags σ1,…,σk with(2)σi=g1∑j=1nH3ID,j,τ0mijα.(ii)
Phase 2 (Data Upload): After the above phase is completed, the DO uploads the labelτ, all data blocks m1,…,mk, and the corresponding tags σ1,…,σk to the CSP. Meanwhile, the DO only stores the label τ of the dataset and deletes the data blocks and the corresponding tags locally.


### 4.4. Auditing

The auditing procedure is composed of three phases: Challenge, Proof Generation, and Proof verification.(i)
Phase 1 (Challenge): The TPA can get the label and send the challenge to the CSP for checking the data integrity. Firstly, the TPA randomly chooses a nonempty subsetI⊆1,k along with random values ci∈ℤq∗ for every i∈I. After that, the TPA sends the user identity ID, the identifier of dataset ds, and the challenge chal=ID,ds,i,ci:i∈I to the CSP.(ii)
Phase 2 (Proof Generation): The CSP will honestly generate the proof according to the challenge. On receiving a user identityID, the identifier of dataset ds, and a challenge chal, the CSP computes m=∑i∈Icimi, σ=∏i∈Iσici, and returns PF=σ and m to the TPA.(iii)
Phase 3 (Proof Verification): Firstly, on receiving the proofPF and corresponding m from the CSP, the TPA can check validity of label τ by(3)eτ0,upkID·g2H2ID,ds,t,β=eH1ID,upkID,mpk.And then, if the above equation holds, the TPA tests(4)eσ,g2=eg1∑j=1nH3ID,j,τ0mj,β.In the end, if the above equation holds, the TPA thinks the dataset stored in the CSP is unwounded. Otherwise, the dataset has been damaged.


### 4.5. Batch Auditing

The TPA can improve the efficiency of auditing through batch auditing. The batch auditing procedure is composed of four phases: Challenges, Single Proof Generation, Batch Proof Generation, and Batch Proof verification. We describe the batch auditing process as follows.(i)
Phase 1 (Challenges): The TPA wants to verify the integrity of multiple data once. Firstly, the TPA randomly choosessver∈Zq∗ as its private key uskver, and computes upkver=g2sver as its public key. The registration procedure of the TPA is similar to DO’s registration procedure. However, for security and actual needs, the TPA cannot hide its real identity. Then, the TPA gets labels and sends some challenges to the CSP. It randomly selects l nonempty subsets Iz⊆1,kz,z=1,…,l along with random values czi∈ℤq∗ for every i∈Iz. After that, the TPA prepares the user identity IDz, the identifier of dataset dsz, and the challenge chalz=IDz,dsz,i,czi:i∈Iz, where z=1,…,l is the serial number of lchals. Note that for each user, the number and location of the challenged blocks may be different. The TPA sends them and its public key upkver to the CSP with no secure channels and keeps its private key uskver secret.(ii)
Phase 2 (Single Proof Generation): Same as Proof Generation 4.4, on receiving user identitiesIDz, the identifier of dataset dsz, and a challenge chalz, the CSP computes mz=∑i∈Izczimzi, σz=∏i∈Izσziczi, where z=1,…,l.(iii)
Phase 3 (Batch Proof Generation): After generating every single proofσz,z=1,…,l, the CSP computes r with the public key of the TPA as follows:(5)r=H0eσ1,upkver,…,eσl,upkver,and then, the CSP computes the batch proofσ˜ as follows:(6)σ˜=∏z=1lσzr.The CSP returnsBPF=σ˜ and m1,…,ml to the TPA.(iv)
Phase 4 (Batch Proof Verification): Firstly, on receiving a responseBPF and corresponding mz,z=1,…,l from the CSP, the TPA validates the validity of the corresponding labels of multiple datasets τz,z=1,…,l by(7)e∏z=1lH1IDz,upkIDz,mpk=∏z=1leτ0z,upkIDz·g2H2IDz,dsz,tz,βz.Next, if the above equation holds, the TPA computes(8)r′=H0eg1∑j=1nH3ID1,j,τ01·m1jsver,β1,…,eg1∑j=1nH3IDl,j,τ0l·mljsver,βl,note that sver is the private key of the TPA.And then, the TPA tests(9)eσ˜,g2=∏z=1leg1∑j=1nH3IDz,j,τozmzj,βzr′,where(10)mz=∏i∈Iczimzi,mz=mz1,…,mzn,z=1,…,l.If all the above equations hold, the TPA thinks multiple corresponding datasets stored in the CSP are unwounded. Otherwise, one or more datasets have been damaged, and then we can use Lucas search to efficiently identify which datasets have been breached. The Lucas search is divided into two cases according to the amount of DOs. Please refer to [25] for details.


## 4.1. System Setup

Given a security parameterλ, the CSP does:(i)
Generate a bilinear groupG1,G2,GT,q,e, where q>2λ, G1,G2,GT are three multiplicative cyclic groups with the same prime order q. Bilinear pairing e:G1×G2⟶GT. Isomorphic mapping ψ:G2⟶G1.(ii)
Generate a generatorg1 in G1 and a generator g2 in G2.(iii)
LetH0:0,1∗⟶ℤq∗, H1:0,1∗×G2⟶G1, H2:0,1∗×0,1∗×G1⟶ℤq∗, H3:0,1∗×ℤn∗×G1⟶ℤq∗, and H4:G2⟶0,1∗ be five collision resistant hash functions.(iv)
Randomly chooses∈ℤq∗ as the master private key, and the master public key is mpk=g2s.The CSP publishes the system parametersparams=q,G1,G2,GT,e,ψ,g1,g2,mpk,H0,H1,H2,H3,H4 and keeps the system master private key msk=s secret.


## 4.2. User Registration

The user registration process is composed of three phases.(i)
Phase 1 (UserKeyGen): Given the system parametersparams and the user’s real identity RID, the user does:(1)
Randomly choosex∈ℤq∗ as the user’s secret key which is denoted by uskID. Generate the user’s pseudonym by computing ID=RID⊕H4mpkuskID.(2)
ComputeupkID=g2x as the user’s public key.(ii)
Phase 2 (Certify): Given the system parameterparams, master private key msk, the user’s public key upkID with ID, the CSP generates the certificate CertID=H1ID,upkIDs for the user ID and sends it to the user.(iii)
Phase 3 (Authentication): The userID validates the certificate. If the equation(1)eCertID,g2=eH1ID,upkID,mpk,holds, then the user succeeds in logging into the system.


## 4.3. Outsourcing Storage

The outsourcing storage procedure is composed of two phases: Data Processing and Data Upload.(i)
Phase 1 (Data Processing):(1)
Given an encrypted datasetF∈0,1∗ named ds, the DO splits the dataset into k data blocks m1,m2,…,mk, and each block comprises n sectors, i.e., F=mi,jk×n(2)
The DO randomly choosesα∈ℤq∗, and then computes β=g2α and τ0=CertID1/uskID+H2ID,ds,t,β. The DO sets τ=τ0,β,ds,t,k,n as the label of the dataset.(3)
For eachmi,i∈1,k, the DO computes tags σ1,…,σk with(2)σi=g1∑j=1nH3ID,j,τ0mijα.(ii)
Phase 2 (Data Upload): After the above phase is completed, the DO uploads the labelτ, all data blocks m1,…,mk, and the corresponding tags σ1,…,σk to the CSP. Meanwhile, the DO only stores the label τ of the dataset and deletes the data blocks and the corresponding tags locally.


## 4.4. Auditing

The auditing procedure is composed of three phases: Challenge, Proof Generation, and Proof verification.(i)
Phase 1 (Challenge): The TPA can get the label and send the challenge to the CSP for checking the data integrity. Firstly, the TPA randomly chooses a nonempty subsetI⊆1,k along with random values ci∈ℤq∗ for every i∈I. After that, the TPA sends the user identity ID, the identifier of dataset ds, and the challenge chal=ID,ds,i,ci:i∈I to the CSP.(ii)
Phase 2 (Proof Generation): The CSP will honestly generate the proof according to the challenge. On receiving a user identityID, the identifier of dataset ds, and a challenge chal, the CSP computes m=∑i∈Icimi, σ=∏i∈Iσici, and returns PF=σ and m to the TPA.(iii)
Phase 3 (Proof Verification): Firstly, on receiving the proofPF and corresponding m from the CSP, the TPA can check validity of label τ by(3)eτ0,upkID·g2H2ID,ds,t,β=eH1ID,upkID,mpk.And then, if the above equation holds, the TPA tests(4)eσ,g2=eg1∑j=1nH3ID,j,τ0mj,β.In the end, if the above equation holds, the TPA thinks the dataset stored in the CSP is unwounded. Otherwise, the dataset has been damaged.


## 4.5. Batch Auditing

The TPA can improve the efficiency of auditing through batch auditing. The batch auditing procedure is composed of four phases: Challenges, Single Proof Generation, Batch Proof Generation, and Batch Proof verification. We describe the batch auditing process as follows.(i)
Phase 1 (Challenges): The TPA wants to verify the integrity of multiple data once. Firstly, the TPA randomly choosessver∈Zq∗ as its private key uskver, and computes upkver=g2sver as its public key. The registration procedure of the TPA is similar to DO’s registration procedure. However, for security and actual needs, the TPA cannot hide its real identity. Then, the TPA gets labels and sends some challenges to the CSP. It randomly selects l nonempty subsets Iz⊆1,kz,z=1,…,l along with random values czi∈ℤq∗ for every i∈Iz. After that, the TPA prepares the user identity IDz, the identifier of dataset dsz, and the challenge chalz=IDz,dsz,i,czi:i∈Iz, where z=1,…,l is the serial number of lchals. Note that for each user, the number and location of the challenged blocks may be different. The TPA sends them and its public key upkver to the CSP with no secure channels and keeps its private key uskver secret.(ii)
Phase 2 (Single Proof Generation): Same as Proof Generation 4.4, on receiving user identitiesIDz, the identifier of dataset dsz, and a challenge chalz, the CSP computes mz=∑i∈Izczimzi, σz=∏i∈Izσziczi, where z=1,…,l.(iii)
Phase 3 (Batch Proof Generation): After generating every single proofσz,z=1,…,l, the CSP computes r with the public key of the TPA as follows:(5)r=H0eσ1,upkver,…,eσl,upkver,and then, the CSP computes the batch proofσ˜ as follows:(6)σ˜=∏z=1lσzr.The CSP returnsBPF=σ˜ and m1,…,ml to the TPA.(iv)
Phase 4 (Batch Proof Verification): Firstly, on receiving a responseBPF and corresponding mz,z=1,…,l from the CSP, the TPA validates the validity of the corresponding labels of multiple datasets τz,z=1,…,l by(7)e∏z=1lH1IDz,upkIDz,mpk=∏z=1leτ0z,upkIDz·g2H2IDz,dsz,tz,βz.Next, if the above equation holds, the TPA computes(8)r′=H0eg1∑j=1nH3ID1,j,τ01·m1jsver,β1,…,eg1∑j=1nH3IDl,j,τ0l·mljsver,βl,note that sver is the private key of the TPA.And then, the TPA tests(9)eσ˜,g2=∏z=1leg1∑j=1nH3IDz,j,τozmzj,βzr′,where(10)mz=∏i∈Iczimzi,mz=mz1,…,mzn,z=1,…,l.If all the above equations hold, the TPA thinks multiple corresponding datasets stored in the CSP are unwounded. Otherwise, one or more datasets have been damaged, and then we can use Lucas search to efficiently identify which datasets have been breached. The Lucas search is divided into two cases according to the amount of DOs. Please refer to [25] for details.


## 5. Properties’ Analysis

### 5.1. Correctness

#### 5.1.1. Correctness of Auditing

In procedure 4.4, the proof of dataset includes the labelτ of the dataset and the tags σ of data blocks. Furthermore, every tag is generated by the Data Processing algorithm, and the single proof is generated by the Proof Generation algorithm. All of them are equivalent, i.e., the Proof Verification algorithm can verify both of them. Assuming that all entities operate honestly with the algorithms described above, then the correctness of the scheme can be verified from two aspects:(1)
For any file labelτ and for any single proof PF=m,σ, we have:(11)σ=∏i∈Iσjcj=∏i∈Ig1∑j=1nH3ID,j,τ0mijαci=g1∑j=1nH3ID,j,τ0∑i∈Icimijα=g1∑j=1nH3ID,j,τ0mjα.(2)
For any file labelτ=τ0,β,ds,t,k,n and for any data block mi∈F with corresponding tag σi, we have:(12)eσi,g2=eg1∑j=1nH3ID,j,τ0mijα,g2=eg1∑j=1nH3ID,j,τ0mij,β.


#### 5.1.2. Correctness of Batch Auditing

If the single proofσz is generated by the DO IDz directly with public key upkIDz, then the following equations hold for z=1,…,l:(13)eσz,upkver=e∏j=1ng1H3IDz,j,τ0z·mzj,βzsver,so,(14)r=H0eσ˜1,upkver,…,eσ˜l,upkver=H0eg1∑j=1nH3ID1,j,τ01·m1jsver,β1,…,eg1∑j=1nH3ID1,j,τ01·mljsver,βl=r′,and then(15)eσ˜,g2=e∏z=1lσzr,g2=∏z=1leσz,g2r=∏z=1leg1∑j=1nH3IDz,j,τozmzj,βzr′.And for the label of datasetdsz,z=1,…,l, we have(16)e∏z=1lH1IDz,upkIDz,mpk=∏z=1leH1IDz,upkIDz,mpk=∏z=1leτoz,upkIDzg2H2IDz,dsz,tz,βz.


### 5.2. Batch Auditing

If the TPA needs to audit the integrity of multiple data blocks simultaneously, it can issue valid challenges according todsz and kz, where z=1,…,l. When the CSP receives multiple challenges from the same TPA, the CSP generates a batch proof and sends it to the TPA. Batch proof allows the TPA to interact with the CSP only once to verify that the integrity of the stored data that have not been corrupted.


### 5.3. Anonymity

In our protocol, the user’s real nameRID is protected by a pseudonym ID=RID⊕H4mpkuskID. Every entity can know the mpk and the upkID, but they cannot get the knowledge of msk or uskID. We have H4mpkuskID=H4upkIDmsk. Apart from the user with real identity RID and the CSP, any other third entity cannot know the RID of the user because of the secrecy of msk, uskID, andRID, and the unipolarity of the hash function H4.


### 5.4. Security

#### 5.4.1. The Security of Single Data Auditing

In our certificate-based remote data integrity auditing (CBRDIA, not including the Batch Auditing procedure) protocol, we consider three types of PPT adversaries. Type I adversaryAI models an attacker who can replace the user’s public key. Type II adversary AII models the honest but curious CSP who holds the master secret key and is not allowed to replace the target user’s public key. AI and AII cannot hold both user’s private key and certificate. Type III adversary AIII models the ability of the CSP to forge a valid proof. We conclude the security of the single data auditing procedure in our protocol by Theorems 1–3.Theorem 1.
Suppose a PPT adversaryAI can forge a valid proof with advantage ϵ, and suppose AI can make at most qu times Create User Queries, qe times Certification Queries, and qt times TagGen Queries. Then there exists a challenger ℬ to solve the co-CDH problem with advantage ϵ′≥1−1/quqe1−1/qt+1qt1/qt+1quϵ.Proof.
The detailed proof is given inA.Theorem 2.
Suppose a PPT adversaryAII can forge a valid proof with advantage ϵ, and suppose AII can make at most qu times Create User Queries, qr times Collusion Queries, and qt times TagGen Queries. Then there exists a challenger ℬ to solve the k-CAA problem with advantage ϵ′≥1−1/quqr1−1/qt+1qt1/qt+1quϵ.Proof.
The detailed proof is given inB.Theorem 3.
The probability ofℬ forging a valid single proof is negligible if the file challenged is damaged or modified.Proof.
The detailed proof is given inC.


#### 5.4.2. The Security of Batch Auditing

Theorem 4.
SupposeH0 is a collision-resistant Hash function. The batch proof in the CBRDIBA protocol is valid if and only if every individual proof used in the Batch Proof Generation algorithm is valid.Proof.
The detailed proof is given inD.


## 5.1. Correctness

### 5.1.1. Correctness of Auditing

In procedure 4.4, the proof of dataset includes the labelτ of the dataset and the tags σ of data blocks. Furthermore, every tag is generated by the Data Processing algorithm, and the single proof is generated by the Proof Generation algorithm. All of them are equivalent, i.e., the Proof Verification algorithm can verify both of them. Assuming that all entities operate honestly with the algorithms described above, then the correctness of the scheme can be verified from two aspects:(1)
For any file labelτ and for any single proof PF=m,σ, we have:(11)σ=∏i∈Iσjcj=∏i∈Ig1∑j=1nH3ID,j,τ0mijαci=g1∑j=1nH3ID,j,τ0∑i∈Icimijα=g1∑j=1nH3ID,j,τ0mjα.(2)
For any file labelτ=τ0,β,ds,t,k,n and for any data block mi∈F with corresponding tag σi, we have:(12)eσi,g2=eg1∑j=1nH3ID,j,τ0mijα,g2=eg1∑j=1nH3ID,j,τ0mij,β.


### 5.1.2. Correctness of Batch Auditing

If the single proofσz is generated by the DO IDz directly with public key upkIDz, then the following equations hold for z=1,…,l:(13)eσz,upkver=e∏j=1ng1H3IDz,j,τ0z·mzj,βzsver,so,(14)r=H0eσ˜1,upkver,…,eσ˜l,upkver=H0eg1∑j=1nH3ID1,j,τ01·m1jsver,β1,…,eg1∑j=1nH3ID1,j,τ01·mljsver,βl=r′,and then(15)eσ˜,g2=e∏z=1lσzr,g2=∏z=1leσz,g2r=∏z=1leg1∑j=1nH3IDz,j,τozmzj,βzr′.And for the label of datasetdsz,z=1,…,l, we have(16)e∏z=1lH1IDz,upkIDz,mpk=∏z=1leH1IDz,upkIDz,mpk=∏z=1leτoz,upkIDzg2H2IDz,dsz,tz,βz.


## 5.1.1. Correctness of Auditing

In procedure 4.4, the proof of dataset includes the labelτ of the dataset and the tags σ of data blocks. Furthermore, every tag is generated by the Data Processing algorithm, and the single proof is generated by the Proof Generation algorithm. All of them are equivalent, i.e., the Proof Verification algorithm can verify both of them. Assuming that all entities operate honestly with the algorithms described above, then the correctness of the scheme can be verified from two aspects:(1)
For any file labelτ and for any single proof PF=m,σ, we have:(11)σ=∏i∈Iσjcj=∏i∈Ig1∑j=1nH3ID,j,τ0mijαci=g1∑j=1nH3ID,j,τ0∑i∈Icimijα=g1∑j=1nH3ID,j,τ0mjα.(2)
For any file labelτ=τ0,β,ds,t,k,n and for any data block mi∈F with corresponding tag σi, we have:(12)eσi,g2=eg1∑j=1nH3ID,j,τ0mijα,g2=eg1∑j=1nH3ID,j,τ0mij,β.


## 5.1.2. Correctness of Batch Auditing

If the single proofσz is generated by the DO IDz directly with public key upkIDz, then the following equations hold for z=1,…,l:(13)eσz,upkver=e∏j=1ng1H3IDz,j,τ0z·mzj,βzsver,so,(14)r=H0eσ˜1,upkver,…,eσ˜l,upkver=H0eg1∑j=1nH3ID1,j,τ01·m1jsver,β1,…,eg1∑j=1nH3ID1,j,τ01·mljsver,βl=r′,and then(15)eσ˜,g2=e∏z=1lσzr,g2=∏z=1leσz,g2r=∏z=1leg1∑j=1nH3IDz,j,τozmzj,βzr′.And for the label of datasetdsz,z=1,…,l, we have(16)e∏z=1lH1IDz,upkIDz,mpk=∏z=1leH1IDz,upkIDz,mpk=∏z=1leτoz,upkIDzg2H2IDz,dsz,tz,βz.


## 5.2. Batch Auditing

If the TPA needs to audit the integrity of multiple data blocks simultaneously, it can issue valid challenges according todsz and kz, where z=1,…,l. When the CSP receives multiple challenges from the same TPA, the CSP generates a batch proof and sends it to the TPA. Batch proof allows the TPA to interact with the CSP only once to verify that the integrity of the stored data that have not been corrupted.


## 5.3. Anonymity

In our protocol, the user’s real nameRID is protected by a pseudonym ID=RID⊕H4mpkuskID. Every entity can know the mpk and the upkID, but they cannot get the knowledge of msk or uskID. We have H4mpkuskID=H4upkIDmsk. Apart from the user with real identity RID and the CSP, any other third entity cannot know the RID of the user because of the secrecy of msk, uskID, andRID, and the unipolarity of the hash function H4.


## 5.4. Security

### 5.4.1. The Security of Single Data Auditing

In our certificate-based remote data integrity auditing (CBRDIA, not including the Batch Auditing procedure) protocol, we consider three types of PPT adversaries. Type I adversaryAI models an attacker who can replace the user’s public key. Type II adversary AII models the honest but curious CSP who holds the master secret key and is not allowed to replace the target user’s public key. AI and AII cannot hold both user’s private key and certificate. Type III adversary AIII models the ability of the CSP to forge a valid proof. We conclude the security of the single data auditing procedure in our protocol by Theorems 1–3.Theorem 1.
Suppose a PPT adversaryAI can forge a valid proof with advantage ϵ, and suppose AI can make at most qu times Create User Queries, qe times Certification Queries, and qt times TagGen Queries. Then there exists a challenger ℬ to solve the co-CDH problem with advantage ϵ′≥1−1/quqe1−1/qt+1qt1/qt+1quϵ.Proof.
The detailed proof is given inA.Theorem 2.
Suppose a PPT adversaryAII can forge a valid proof with advantage ϵ, and suppose AII can make at most qu times Create User Queries, qr times Collusion Queries, and qt times TagGen Queries. Then there exists a challenger ℬ to solve the k-CAA problem with advantage ϵ′≥1−1/quqr1−1/qt+1qt1/qt+1quϵ.Proof.
The detailed proof is given inB.Theorem 3.
The probability ofℬ forging a valid single proof is negligible if the file challenged is damaged or modified.Proof.
The detailed proof is given inC.


### 5.4.2. The Security of Batch Auditing

Theorem 4.
SupposeH0 is a collision-resistant Hash function. The batch proof in the CBRDIBA protocol is valid if and only if every individual proof used in the Batch Proof Generation algorithm is valid.Proof.
The detailed proof is given inD.


## 5.4.1. The Security of Single Data Auditing

In our certificate-based remote data integrity auditing (CBRDIA, not including the Batch Auditing procedure) protocol, we consider three types of PPT adversaries. Type I adversaryAI models an attacker who can replace the user’s public key. Type II adversary AII models the honest but curious CSP who holds the master secret key and is not allowed to replace the target user’s public key. AI and AII cannot hold both user’s private key and certificate. Type III adversary AIII models the ability of the CSP to forge a valid proof. We conclude the security of the single data auditing procedure in our protocol by Theorems 1–3.Theorem 1.
Suppose a PPT adversaryAI can forge a valid proof with advantage ϵ, and suppose AI can make at most qu times Create User Queries, qe times Certification Queries, and qt times TagGen Queries. Then there exists a challenger ℬ to solve the co-CDH problem with advantage ϵ′≥1−1/quqe1−1/qt+1qt1/qt+1quϵ.Proof.
The detailed proof is given inA.Theorem 2.
Suppose a PPT adversaryAII can forge a valid proof with advantage ϵ, and suppose AII can make at most qu times Create User Queries, qr times Collusion Queries, and qt times TagGen Queries. Then there exists a challenger ℬ to solve the k-CAA problem with advantage ϵ′≥1−1/quqr1−1/qt+1qt1/qt+1quϵ.Proof.
The detailed proof is given inB.Theorem 3.
The probability ofℬ forging a valid single proof is negligible if the file challenged is damaged or modified.Proof.
The detailed proof is given inC.


## 5.4.2. The Security of Batch Auditing

Theorem 4.
SupposeH0 is a collision-resistant Hash function. The batch proof in the CBRDIBA protocol is valid if and only if every individual proof used in the Batch Proof Generation algorithm is valid.Proof.
The detailed proof is given inD.


## 6. Performance Evaluation

Before analyzing the performance of our CBRDIBA protocol, we first compared our CBRDIBA protocol with several data integrity auditing protocols [13, 16, 25, 27–29] in Table 2, and we notice that the CBRDIBA protocol supports batch auditing, resisting collusion attacks, anonymity, Lucas error search, with no key escrow problem, and with no secure channels simultaneously. The protocol uses Lucas search to deal with batch auditing failures, which is a more efficient error search method than binary search. And the protocol also adds timestamps to the HVTs such that it can make adversaries not use the expired valid proof to pretend to be the current ones.Table 2
Comparison of multiple features.
FeatureAteniese et al. [13]Li et al. [16]Yang et al. [28]Han et al. [25]Huang et al. [29]Wang et al. [27]CBRDIBACan do batch auditingNoNoYesYesYesYesYesCan resist collusion attacks——NoNoNoNoYesLucas error search——NoYesNoNoYesAnonymityNoNoNoNoNoNoYesNo key escrow problemNoYesYesNoYesYesYesNo secure channelNoYesYesNoNoYesYesAdd timestampNoYesNoNoNoNoYesFurthermore, we will demonstrate the efficiency of our data integrity batch auditing scheme in comparison with data integrity auditing of a single DO both theoretically and experimentally. Table3 shows the notations used in this section.Table 3
The notations of operations.
NotationsMeaningsTHMap-to-point hash operationTPBilinear pairing operationTE1Exponential operation inG1TE2Exponential operation inG2TM1Multiplicative operation inG1TM2Multiplicative operation inG2nThe number of data block’s sectorscThe number of challenged data blocksZqThe binary length of an element inℤqG1The binary length of an element inG1lThe number of proofs used in the batch proof


### 6.1. Theoretical Analysis

#### 6.1.1. Communication Cost

From Table4 we can see that the communication cost of Batch Auditing with l different DOs is lower than the cost of l times Auditing procedures.Note that as the number of DOs involved in a batch auditing procedure increases, the number of interactions between the CSP and the TPA is constant. However, there is no doubt that in the Auditing procedure, the number of DOs is directly proportional to the number of interactions.


#### 6.1.2. Computation Cost

In Table4, we list the computation and communication costs of the Auditing procedure and the Batch Auditing procedure. Note that, in order to facilitate to compare, we ignore the time cost of map to Zq hash operation, additive operation in Zq, and inverse operation in Zq. The comparison results show that the computation cost of batch auditing with l different DOs is 3l+2Tp+lTH1+lTM1+lTM2+2lTE1+2lTE2, which is lower than the cost of l times Auditing procedures. Although the efficiency improvement was not very significant (mainly only n pairing operations off), it was due to the fact that we considered our protocol could resist collusion attacks.Table 4
Comparison of the computation cost and the communication cost.
Auditing approachProof generation costProof verification costCommunication cost of auditingInteractions timesl times single auditingcTE1+TM1l4Tp+TE1+TE2+TM2+THlG1+c+nZqlBatch auditing withl DOslTp+lTM1+lTE1+lcTE1+TM13l+2Tp+lTH+lTM1+lTM2+2lTE1+2lTE2lc+nZq+G1+Zq1


### 6.2. Experiment Analysis

We implement our CBRDIBA protocol using the Java Pairing-Based Cryptography (JPBC) Library [30] and evaluate it on a personal computer with Intel i7 2.20 GHz quad-cores processor, 16 GB RAM. In our implementation, we use the parameter f.param which is one of the standard parameter settings of the JPBC library. f.param provides an asymmetric pairing. For 80-bit security, only 160 bits are needed to represent elements of G1 and 320 bits for G2. To effectively evaluate the performance, the size of the test file we choose is 112 KB (114763 bytes), and we split a test dataset F with size SizeF bits into m blocks in our experiments. Then, we further divide each data block into n sectors, and the length of each sector is 160 bits. The number m of the data blocks and the number n of the data block’s sectors satisfy m−1n≤SizeF/160≤mn.


#### 6.2.1. Proof Verification Cost

We simulate the TPA to run the algorithms Proof Verification and Batch Proof Verification when the total data blocks are 375 with different numbers of DOs from 10 to 100. We define the algorithms Proof Verification and Batch Proof Verification to verify the proof. Both of them will finish the same amount of users’ data auditing mission in their own way. In this case, Figure3 shows that the cost of algorithm Batch Proof Verification is lower than that of Proof Verification.Figure 3
Comparison of proof verification cost for different number of data owners.Furthermore, the TPA runs the algorithms Proof Verification and Batch Proof Verification when the total data blocks are 375 with different numbers of challenged blocks from 10 to 100. In order to control variables, we set the number of data owners in this experiment as 20. In this environment, Figure4 shows that in most cases, the cost of algorithm Batch Proof Verification is lower than that of Proof Verification.Figure 4
Comparison of proof verification cost for different number of challenged blocks.


## 6.1. Theoretical Analysis

### 6.1.1. Communication Cost

From Table4 we can see that the communication cost of Batch Auditing with l different DOs is lower than the cost of l times Auditing procedures.Note that as the number of DOs involved in a batch auditing procedure increases, the number of interactions between the CSP and the TPA is constant. However, there is no doubt that in the Auditing procedure, the number of DOs is directly proportional to the number of interactions.


### 6.1.2. Computation Cost

In Table4, we list the computation and communication costs of the Auditing procedure and the Batch Auditing procedure. Note that, in order to facilitate to compare, we ignore the time cost of map to Zq hash operation, additive operation in Zq, and inverse operation in Zq. The comparison results show that the computation cost of batch auditing with l different DOs is 3l+2Tp+lTH1+lTM1+lTM2+2lTE1+2lTE2, which is lower than the cost of l times Auditing procedures. Although the efficiency improvement was not very significant (mainly only n pairing operations off), it was due to the fact that we considered our protocol could resist collusion attacks.Table 4
Comparison of the computation cost and the communication cost.
Auditing approachProof generation costProof verification costCommunication cost of auditingInteractions timesl times single auditingcTE1+TM1l4Tp+TE1+TE2+TM2+THlG1+c+nZqlBatch auditing withl DOslTp+lTM1+lTE1+lcTE1+TM13l+2Tp+lTH+lTM1+lTM2+2lTE1+2lTE2lc+nZq+G1+Zq1


## 6.1.1. Communication Cost

From Table4 we can see that the communication cost of Batch Auditing with l different DOs is lower than the cost of l times Auditing procedures.Note that as the number of DOs involved in a batch auditing procedure increases, the number of interactions between the CSP and the TPA is constant. However, there is no doubt that in the Auditing procedure, the number of DOs is directly proportional to the number of interactions.


## 6.1.2. Computation Cost

In Table4, we list the computation and communication costs of the Auditing procedure and the Batch Auditing procedure. Note that, in order to facilitate to compare, we ignore the time cost of map to Zq hash operation, additive operation in Zq, and inverse operation in Zq. The comparison results show that the computation cost of batch auditing with l different DOs is 3l+2Tp+lTH1+lTM1+lTM2+2lTE1+2lTE2, which is lower than the cost of l times Auditing procedures. Although the efficiency improvement was not very significant (mainly only n pairing operations off), it was due to the fact that we considered our protocol could resist collusion attacks.Table 4
Comparison of the computation cost and the communication cost.
Auditing approachProof generation costProof verification costCommunication cost of auditingInteractions timesl times single auditingcTE1+TM1l4Tp+TE1+TE2+TM2+THlG1+c+nZqlBatch auditing withl DOslTp+lTM1+lTE1+lcTE1+TM13l+2Tp+lTH+lTM1+lTM2+2lTE1+2lTE2lc+nZq+G1+Zq1


## 6.2. Experiment Analysis

We implement our CBRDIBA protocol using the Java Pairing-Based Cryptography (JPBC) Library [30] and evaluate it on a personal computer with Intel i7 2.20 GHz quad-cores processor, 16 GB RAM. In our implementation, we use the parameter f.param which is one of the standard parameter settings of the JPBC library. f.param provides an asymmetric pairing. For 80-bit security, only 160 bits are needed to represent elements of G1 and 320 bits for G2. To effectively evaluate the performance, the size of the test file we choose is 112 KB (114763 bytes), and we split a test dataset F with size SizeF bits into m blocks in our experiments. Then, we further divide each data block into n sectors, and the length of each sector is 160 bits. The number m of the data blocks and the number n of the data block’s sectors satisfy m−1n≤SizeF/160≤mn.


### 6.2.1. Proof Verification Cost

We simulate the TPA to run the algorithms Proof Verification and Batch Proof Verification when the total data blocks are 375 with different numbers of DOs from 10 to 100. We define the algorithms Proof Verification and Batch Proof Verification to verify the proof. Both of them will finish the same amount of users’ data auditing mission in their own way. In this case, Figure3 shows that the cost of algorithm Batch Proof Verification is lower than that of Proof Verification.Figure 3
Comparison of proof verification cost for different number of data owners.Furthermore, the TPA runs the algorithms Proof Verification and Batch Proof Verification when the total data blocks are 375 with different numbers of challenged blocks from 10 to 100. In order to control variables, we set the number of data owners in this experiment as 20. In this environment, Figure4 shows that in most cases, the cost of algorithm Batch Proof Verification is lower than that of Proof Verification.Figure 4
Comparison of proof verification cost for different number of challenged blocks.


## 6.2.1. Proof Verification Cost

We simulate the TPA to run the algorithms Proof Verification and Batch Proof Verification when the total data blocks are 375 with different numbers of DOs from 10 to 100. We define the algorithms Proof Verification and Batch Proof Verification to verify the proof. Both of them will finish the same amount of users’ data auditing mission in their own way. In this case, Figure3 shows that the cost of algorithm Batch Proof Verification is lower than that of Proof Verification.Figure 3
Comparison of proof verification cost for different number of data owners.Furthermore, the TPA runs the algorithms Proof Verification and Batch Proof Verification when the total data blocks are 375 with different numbers of challenged blocks from 10 to 100. In order to control variables, we set the number of data owners in this experiment as 20. In this environment, Figure4 shows that in most cases, the cost of algorithm Batch Proof Verification is lower than that of Proof Verification.Figure 4
Comparison of proof verification cost for different number of challenged blocks.


## 7. Conclusion

In this paper, we first present a security-enhanced CBRDIBA protocol for cloud-IoT. In our protocol, the TPA can audit the integrity of multiple data simultaneously. If the file is corrupted or lost, the DO will require the CSP to compensate for the damaged file. The correctness and security of the proposed protocol are proved. The security games show that our protocol can resist the highest level of collusion attacks. The communication and computation costs of batch auditing in our protocol have been evaluated through experiments and theoretic analysis. The results indicate that in the case of enhanced security, our batch auditing protocol still has computational efficiency and practicability.



---

*Source: 7882662-2022-07-31.xml*