# An Effective Integrity Verification Scheme of Cloud Data Based on BLS Signature

Authors: Xiling Luo; Zequan Zhou; Lin Zhong; Jian Mao; Chaoyong Chen
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Cloud storage services allow users to outsource their data remotely to save their local storage space and enable them to manage resources on demand. However, once users outsourced their data to the remote cloud platform, they lose the physical control of the data. How to ensure the integrity of outsourced data is the major concern of cloud users and also is the main challenge in the cloud service deployment. Limited by the communication and computation overheads, traditional hash-based integrity verification solutions in the stand-alone systems cannot be directly adopted in remote cloud storing environment. In this paper, we improve the previous privacy preserving model and propose an effective integrity verification scheme of cloud data based on BLS signature (EoCo), which ensures public audition and data privacy preserving. In addition, EoCo also supports batch auditing operations. We conducted theoretical analysis of our scheme, demonstrated its correctness and security properties, and evaluated the system performance as well.


---

## Body

## 1. Introduction

Recent years, cloud storage services are getting more and more popular, which allow users to outsource their data remotely to save their local storage space and enable them to manage resources on demand. However, once users outsourced the data to the remote cloud platform, they lose the physical control of their data. Some cloud service providers (CSPs) may remove users’ data that are less accessed to gain more profits. In addition, the loss of data may also be caused by system crashes or operation errors [1, 2]. In this situation, CSPs may conceal the fact that users’ data have no longer been stored correctly. How to ensure the integrity of outsourced data is a major concern of cloud users. Being limited by the communication and computation overheads, traditional hash-based integrity verification solutions for stand-alone systems cannot be directly adopted in remote cloud storing environments. For example, a strawman solution is to compute and keep the message authentication code of the file before outsourcing and then retrieve the whole file from the cloud server and check with the message authentication code. However, this will introduce unacceptable communication and computational overhead.To verify the integrity of cloud data without retrieving the whole outsourced files, Ateniese et al. [3] proposed a provable data possession (PDP) scheme, which provides remote integrity verification based on homomorphic tag and sampling techniques. Their improved approach supports public audition but cannot ensure the privacy preserving property. Juels et al. [4] proposed a proof of retrievability (POR) protocol to audit and ensure the correctness of remote data once data corruption happened. Nevertheless, the scheme only supports limited rounds of verification without privacy protection of public audition. The scheme proposed by Shacham et al. [5] cannot protect data privacy either. Although many other public auditing solutions have been proposed [6–12] that preserves privacy during the integrity audition, some schemes [6, 8, 9] only prevent the data leakage, rather than provide rigorous privacy guarantee. The solutions proposed by Wang et al. and Worku et al. [6, 9] fail to achieve reliable data protection under their security models.In this paper, we propose an effective verification of cloud data integrity scheme, EoCo, based on BLS (Boneh-Lynn-Shacham) signature with strong privacy protection. Besides efficient remote data integrity verification, our scheme also supports public auditability, privacy protection, blockless verification, and batch audition. We formally define a new integrity protection model based on the work proposed by Worku et al. [9] and prove that dishonest server cannot bypass the verification based on the CDH (computational Diffie-Hellman) problem. We also introduce a ZK-privacy (zero knowledge privacy) model and prove that our scheme is secure against CMA (adaptive chosen messages attack) attacks and CPA (chosen plaintext attack) attacks under the security assumption of the cryptographic primitives.Contributions. Our contributions can be summarized as follows:(i)
We propose a remote data integrity protection scheme that ensures public auditability, privacy protection, and blockless verification. Besides, our scheme may also support batch auditing operations.
(ii)
We introduce and formally define a ZK-privacy model, where the adversary obtains zero knowledge from the auditing interactions. We prove the privacy preserving property of our scheme under the ZK-privacy model.
(iii)
We evaluate the performance of our proposed scheme through mathematically analysis and compare it with related schemes in communication and computation overhead. The communication overhead of EoCo is onlyO
(
1
).Paper Organization. The rest of this paper is organized as follows. In Section 2, we discuss the related work and the key challenges; Section 3 presents the preliminaries of the proposed scheme; in Section 4, we describe the system model and the security goals; in Section 5, we propose our publicly auditable integrity verification scheme; we conduct theoretical analysis with security proof in Section 6; in Section 7, we evaluate the performance overhead of our approach; and Section 8 concludes the paper.


## 2. Related Works

### 2.1. Provable Data Possession and Proof of Retrievability

Ateniese et al. [3] first proposed a remote auditing system using a provable data possession (PDP) model to ensure data integrity in untrusted storage services. To deploy RSA (Rivest-Shamir-Adleman) digital signature, the scheme splits data into small file blocks. The high probability guarantee of data integrity is achieved by randomly selecting some blocks and check the correctness by using the attribute of RSA homomorphic linear validation. Ateniese et al. [13] introduced the retrievability property on the basis of PDP using error-correcting codes. However, as the linear combination of sample file blocks is exposed to external auditors in the public auditing process, the above two solutions cannot achieve provable privacy protection. Juels et al. [4] proposed POR model to construct data integrity verification. The scheme ensures data integrity and retrievability through spot-checking and error-correcting codes. Spot-checking is to randomly embed special check blocks, sentinels, into the data file, and then randomly select a number of sentinels to verify the file data’s integrity. However, this scheme has a critical problem that once the times of validations is beyond a certain number, these fixed sentinels will be exposed and the data integrity will not be guaranteed. In addition, the scheme cannot support public audition. Bowers et al. [14] improved the POR model, and Shacham et al. [5, 15] also proposed an improved POR scheme base on BLS signature [16]. However, these schemes cannot ensure privacy protection for the same reason as the scheme proposed by Ateniese et al. [3]. Shah et al. [12, 17] introduced a third party auditor (TPA) and sent a number of precomputed symmetric-keyed hashes over the encrypted data to the TPA. Nevertheless, this scheme can only be applied to encrypted files and used in a limited way. When the keyed hashes are used up, this scheme will give the user additional online burden. Worku et al. [9] redefined a new integrity protection model that ensured a stronger definition of integrity by adding a second query phase and also proposed a scheme that claims to be able to acquire provable security under the model. However, Liu et al. [11] proved that the scheme in [9] does not satisfy the definition of its own security mode. Worku’s scheme cite 10 selects a unique identifier n
a
m
e for each file, but the n
a
m
e cannot be well embedded into the scheme and is not tightly connected to the scheme. Therefore, the adversary can extract important knowledge in the second inquiry phase of the security model [18].


### 2.2. Public Audition

Wang et al. [6] proposed a public audition scheme with the privacy protection property that an adversary cannot obtain the information of data in the PDP model. Worku et al. [9] presented that the Wang’s scheme [6] is not secure against the attacks from malicious servers and proposed a privacy preserving scheme. Wang et al. [8] proposed an improved scheme to achieve the property of privacy protection. However, these schemes [6, 8, 9] cannot satisfy the definition of the strict privacy protection model, IND-privacy (indistinguishability-privacy), presented by Fan et al. [10]. The IND-privacy model achieves privacy protection by proving the indistinguishability of responses in the auditing process to external auditors. The general idea and design of Worku’s scheme [9] and Wang’s scheme [8] are similar. The former uses μ
=
μ
′
+
r
h
(
R
) to hide the linear combination μ
′ of the blocks, while the latter is implemented by μ
=
r
+
h
(
R
)
μ
′, where r and R are the random numbers and h stands for hash function. These two ways can only ensure that external auditors cannot obtain the relevant information of the data, but for the malicious auditors, it is easy to distinguish the different information to obtain the relevant knowledge of the cloud users. The protocol proposed by Fan et al. [10] is inefficient and its symmetric external Diffie-Hellman assumption can be solved in the presence of bilinear mapping.


### 2.3. Dynamic Maintenance

In practical settings, supporting dynamic maintenance is desired in remote data attestation. Ateniese et al. [19] proposed the concept of dynamic operation and built a scheme that does not require batch encryption based on a symmetric cryptosystem. However, this scheme is limited to the number of queries and does not support full sense of dynamic scenarios. Wang et al. [7, 8] supported full dynamic operations by using Merkle hash tree (MHT) structure. Erway et al. [20] developed a skiplist-based scheme to enable the integrity of data with full dynamics operations. Sookhak et al. [21] also proposed a dynamic scheme. Xin et al. [22] proposed an effective and secure access control approach for multiauthority cloud storage systems.In addition, the communication and computational overheads are also critical metrics to evaluate the efficiency of cloud services [23, 24]. Among the schemes above, the communication overhead of [8] during validation is O
(
n
), while [9] is more efficient in computational overhead. We illustrate the comparison of the relevant solutions in Table 1.Table 1
Schemes attribute comparison.
Ateniese-[3]
Juels-[4]
[5]
Wang-[6]
Wang-[8]
Worku-[9]
Our scheme
Data integrity protection
Yes
Yes
Yes
No
Yes
No
Yes
Public auditability
Yes
No
Yes
No
Yes
Yes
Yes
Privacy protection
No
No
No
No
Yes
Yes
Yes
Blockless verification
Yes
No
Yes
Yes
Yes
Yes
Yes
Batch auditing
No
No
No
No
Yes
Yes
Yes
Retrievability
No
Yes
No
No
No
No
Yes
Audit times
Unlimit
limit
limit
Unlimit
Unlimit
Unlimit
Unlimit
Communication
O
(
1
)
O
(
n
)
O
(
n
)
O
(
n
)
O
(
n
)
O
(
1
)
O
(
1
)


## 2.1. Provable Data Possession and Proof of Retrievability

Ateniese et al. [3] first proposed a remote auditing system using a provable data possession (PDP) model to ensure data integrity in untrusted storage services. To deploy RSA (Rivest-Shamir-Adleman) digital signature, the scheme splits data into small file blocks. The high probability guarantee of data integrity is achieved by randomly selecting some blocks and check the correctness by using the attribute of RSA homomorphic linear validation. Ateniese et al. [13] introduced the retrievability property on the basis of PDP using error-correcting codes. However, as the linear combination of sample file blocks is exposed to external auditors in the public auditing process, the above two solutions cannot achieve provable privacy protection. Juels et al. [4] proposed POR model to construct data integrity verification. The scheme ensures data integrity and retrievability through spot-checking and error-correcting codes. Spot-checking is to randomly embed special check blocks, sentinels, into the data file, and then randomly select a number of sentinels to verify the file data’s integrity. However, this scheme has a critical problem that once the times of validations is beyond a certain number, these fixed sentinels will be exposed and the data integrity will not be guaranteed. In addition, the scheme cannot support public audition. Bowers et al. [14] improved the POR model, and Shacham et al. [5, 15] also proposed an improved POR scheme base on BLS signature [16]. However, these schemes cannot ensure privacy protection for the same reason as the scheme proposed by Ateniese et al. [3]. Shah et al. [12, 17] introduced a third party auditor (TPA) and sent a number of precomputed symmetric-keyed hashes over the encrypted data to the TPA. Nevertheless, this scheme can only be applied to encrypted files and used in a limited way. When the keyed hashes are used up, this scheme will give the user additional online burden. Worku et al. [9] redefined a new integrity protection model that ensured a stronger definition of integrity by adding a second query phase and also proposed a scheme that claims to be able to acquire provable security under the model. However, Liu et al. [11] proved that the scheme in [9] does not satisfy the definition of its own security mode. Worku’s scheme cite 10 selects a unique identifier n
a
m
e for each file, but the n
a
m
e cannot be well embedded into the scheme and is not tightly connected to the scheme. Therefore, the adversary can extract important knowledge in the second inquiry phase of the security model [18].


## 2.2. Public Audition

Wang et al. [6] proposed a public audition scheme with the privacy protection property that an adversary cannot obtain the information of data in the PDP model. Worku et al. [9] presented that the Wang’s scheme [6] is not secure against the attacks from malicious servers and proposed a privacy preserving scheme. Wang et al. [8] proposed an improved scheme to achieve the property of privacy protection. However, these schemes [6, 8, 9] cannot satisfy the definition of the strict privacy protection model, IND-privacy (indistinguishability-privacy), presented by Fan et al. [10]. The IND-privacy model achieves privacy protection by proving the indistinguishability of responses in the auditing process to external auditors. The general idea and design of Worku’s scheme [9] and Wang’s scheme [8] are similar. The former uses μ
=
μ
′
+
r
h
(
R
) to hide the linear combination μ
′ of the blocks, while the latter is implemented by μ
=
r
+
h
(
R
)
μ
′, where r and R are the random numbers and h stands for hash function. These two ways can only ensure that external auditors cannot obtain the relevant information of the data, but for the malicious auditors, it is easy to distinguish the different information to obtain the relevant knowledge of the cloud users. The protocol proposed by Fan et al. [10] is inefficient and its symmetric external Diffie-Hellman assumption can be solved in the presence of bilinear mapping.


## 2.3. Dynamic Maintenance

In practical settings, supporting dynamic maintenance is desired in remote data attestation. Ateniese et al. [19] proposed the concept of dynamic operation and built a scheme that does not require batch encryption based on a symmetric cryptosystem. However, this scheme is limited to the number of queries and does not support full sense of dynamic scenarios. Wang et al. [7, 8] supported full dynamic operations by using Merkle hash tree (MHT) structure. Erway et al. [20] developed a skiplist-based scheme to enable the integrity of data with full dynamics operations. Sookhak et al. [21] also proposed a dynamic scheme. Xin et al. [22] proposed an effective and secure access control approach for multiauthority cloud storage systems.In addition, the communication and computational overheads are also critical metrics to evaluate the efficiency of cloud services [23, 24]. Among the schemes above, the communication overhead of [8] during validation is O
(
n
), while [9] is more efficient in computational overhead. We illustrate the comparison of the relevant solutions in Table 1.Table 1
Schemes attribute comparison.
Ateniese-[3]
Juels-[4]
[5]
Wang-[6]
Wang-[8]
Worku-[9]
Our scheme
Data integrity protection
Yes
Yes
Yes
No
Yes
No
Yes
Public auditability
Yes
No
Yes
No
Yes
Yes
Yes
Privacy protection
No
No
No
No
Yes
Yes
Yes
Blockless verification
Yes
No
Yes
Yes
Yes
Yes
Yes
Batch auditing
No
No
No
No
Yes
Yes
Yes
Retrievability
No
Yes
No
No
No
No
Yes
Audit times
Unlimit
limit
limit
Unlimit
Unlimit
Unlimit
Unlimit
Communication
O
(
1
)
O
(
n
)
O
(
n
)
O
(
n
)
O
(
n
)
O
(
1
)
O
(
1
)


## 3. Preliminaries

### 3.1. Bilinear Map and GDH Groups

LetG
1, G
2, and G
T be multiplicative cyclic groups of the same large prime order p, where |
G
1
|
=
|
G
2
|
=
|
G
T
|. Let g
1
,
g
2 be the generators of G
1
,
G
2, respectively. e
:
G
1
×
G
2
→
G
T is a bilinear map if it satisfies the following properties:(i)
Bilinear:∀
u
∈
G
1
,
v
∈
G
2 and ∀
a
,
b
∈
Z
p, e
(
u
a
,
v
b
)
=
e
(
u
,
v
)
a
b holds.
(ii)
Nondegenerate:∃
u
∈
G
1
,
v
∈
G
2, such that e
(
u
,
v
)
≠
I
G
T, I
G
T is the identity element of the cyclic group G
T.If there exists an isomorphismψ
:
G
2
→
G
1, with ψ
(
g
2
)
=
g
1, (
G
1
,
G
2
) is a Gap Diffie-Hellman (GDH) group pair. We can set G
1
=
G
2
=
G and g
1
=
g
2
=
g and take ψ to be the identity map.(a) Computational co-Diffie-Hellman (co-CDH) on GDH [16]. Given g
2
,
g
2
α
∈
G
2 and h
∈
G
1 as input and α
∈
Z
p, compute h
α
∈
G
1.(b) Decision co-Diffie-Hellman (co-DDH) on GDH [16]. Given g
2
,
g
2
α
∈
G
2 and h
,
h
β
∈
G
1 as input, if α
=
β the output is yes; otherwise, the output is no. When the answer is yes, we say that (
g
2
,
g
2
α
,
h
,
h
α
) is a co-Diffie-Hellman tuple.WhenG
1
=
G
2, these problems reduce to a standard CDH and DDH problems. The co-DDH problem is easy to be solved but co-CDH is hard on the GDH group [16].


### 3.2. BLS Signature

The BLS signature [16] includes three functions, K
e
y
G
e
n
,
S
i
g
n, and V
e
r
i
f
y. Let (
G
1
,
G
2
) be a GDH group where |
G
1
|
=
|
G
2
|
=
p. It makes use of a full-domain hash function H
:
{
0,1
}
∗
→
G
1.(i)
KeyGen. Randomly choose x
←
Z
p and compute v
←
g
2
x. The public key is v
∈
G
2 and the private key is x.
(ii)
Sign. Given a private key x
∈
Z
p and a message M
∈
{
0,1
}
∗, compute h
←
H
(
M
)
∈
G
1 and σ
←
h
x. The signature is σ
∈
G
1.
(iii)
Verify. Given a public key v
∈
G
2, a message M
∈
{
0,1
}
∗, and the signature σ
∈
G
1, compute h
←
H
(
M
)
∈
G
1 and verify whether (
g
2
,
v
,
h
,
σ
) is a valid co-Diffie-Hellman tuple. If so, outputvalid; otherwise, outputinvalid.


## 3.1. Bilinear Map and GDH Groups

LetG
1, G
2, and G
T be multiplicative cyclic groups of the same large prime order p, where |
G
1
|
=
|
G
2
|
=
|
G
T
|. Let g
1
,
g
2 be the generators of G
1
,
G
2, respectively. e
:
G
1
×
G
2
→
G
T is a bilinear map if it satisfies the following properties:(i)
Bilinear:∀
u
∈
G
1
,
v
∈
G
2 and ∀
a
,
b
∈
Z
p, e
(
u
a
,
v
b
)
=
e
(
u
,
v
)
a
b holds.
(ii)
Nondegenerate:∃
u
∈
G
1
,
v
∈
G
2, such that e
(
u
,
v
)
≠
I
G
T, I
G
T is the identity element of the cyclic group G
T.If there exists an isomorphismψ
:
G
2
→
G
1, with ψ
(
g
2
)
=
g
1, (
G
1
,
G
2
) is a Gap Diffie-Hellman (GDH) group pair. We can set G
1
=
G
2
=
G and g
1
=
g
2
=
g and take ψ to be the identity map.(a) Computational co-Diffie-Hellman (co-CDH) on GDH [16]. Given g
2
,
g
2
α
∈
G
2 and h
∈
G
1 as input and α
∈
Z
p, compute h
α
∈
G
1.(b) Decision co-Diffie-Hellman (co-DDH) on GDH [16]. Given g
2
,
g
2
α
∈
G
2 and h
,
h
β
∈
G
1 as input, if α
=
β the output is yes; otherwise, the output is no. When the answer is yes, we say that (
g
2
,
g
2
α
,
h
,
h
α
) is a co-Diffie-Hellman tuple.WhenG
1
=
G
2, these problems reduce to a standard CDH and DDH problems. The co-DDH problem is easy to be solved but co-CDH is hard on the GDH group [16].


## 3.2. BLS Signature

The BLS signature [16] includes three functions, K
e
y
G
e
n
,
S
i
g
n, and V
e
r
i
f
y. Let (
G
1
,
G
2
) be a GDH group where |
G
1
|
=
|
G
2
|
=
p. It makes use of a full-domain hash function H
:
{
0,1
}
∗
→
G
1.(i)
KeyGen. Randomly choose x
←
Z
p and compute v
←
g
2
x. The public key is v
∈
G
2 and the private key is x.
(ii)
Sign. Given a private key x
∈
Z
p and a message M
∈
{
0,1
}
∗, compute h
←
H
(
M
)
∈
G
1 and σ
←
h
x. The signature is σ
∈
G
1.
(iii)
Verify. Given a public key v
∈
G
2, a message M
∈
{
0,1
}
∗, and the signature σ
∈
G
1, compute h
←
H
(
M
)
∈
G
1 and verify whether (
g
2
,
v
,
h
,
σ
) is a valid co-Diffie-Hellman tuple. If so, outputvalid; otherwise, outputinvalid.


## 4. Approach Overview

### 4.1. System Model

Our scheme, EoCo, is built on the system model presented in Figure1. The model consists of three entities,Users,CSP Servers, andThe Third Party Auditor.(i)
Users. Cloud users own the data and want to save local storage and computing resources by uploading them to the cloud.
(ii)
CSP Servers. The CSP servers have a large amount of storage space available for users. At the same time, CSP servers provide effective cloud operations such as data update and queries and retrieve requests from the customers.
(iii)
The Third Party Auditor (TPA). The TPA has more ability and expertise than the clients. Users could ask a TPA help to audit the integrity of the outsourced data on behalf of them.Figure 1
The EoCo-based network system model.In our system model, our remote data integrity protection scheme consists of five critical operations,KeyGen,TokenGen,Challenge,Response, andCheckProof. A cloud user runsKeyGen to generate her/his public key p
k and private key s
k (with a security parameter k as its input). The user runs theTokenGen algorithm to generate a token for the file and outsources the file with corresponding token to the CSP server. When the user wants to check the correctness of her/his data, she/he may delegate the integrity audition to a TPA. The TPA creates c
h
a
l usingChallenge and sends it to the CSP server. The server runsResponse and returns the proof P to TPA. The TPA runsCheckProof to check whether it is correct, and if it is correct, the output is s
u
c
c
e
s
s; otherwise, the output is f
a
i
l
u
r
e.In the system shown in Figure1, we mainly take two threats in to account,the threat to integrity, andthe threat to privacy [25]. Accordingly, we classify attackers into two types based on the knowledge H that they processed.(i)
Threat to Integrity. The attacker observes the data D
A, the authentication identifier T, and the public key p
k, i.e., H
=
<
D
A
,
T
,
p
k
>. The purpose of such attacker is to produce a legitimate proof for the forge DA.
(ii)
Threat to Privacy. The attacker observes only the public key p
k and the proof P, i.e., H
=
<
P
,
p
k
>. The purpose of such attacker is to acquire additional knowledge, such as the content of data or the type of data.


### 4.2. Integrity Protection Model

We improve the integrity protection model proposed by Worku et al. [9] and through this model, we demonstrate two objectives.(1)
If the data are not stay the original state, an adversary cannot successfully construct a valid proof in polynomial time with nonnegligible probability.
(2)
If the adversary can always pass the verification, then it can be shown that the data remains intact.Our integrity protection model allows an adversary to query large filesF
i. The adversary A, may be a dishonest cloud service provider who interacts with a challenger C (users or TPA). The integrity game consists of the following steps and we illustrate the details in Figure 2.(i)
Setup. The challenger C runs the algorithm of key generation, sends the public key p
k to the adversary A, and retains the private key s
k secret.
(ii)
Query1. The adversary A adaptively makes tagging queries: it selects a file F
1 and sends it to C. The challenger C then computes the token T
1 and sends it back to A. The adversary A continues to query C for the token T
2
,
…
,
T
q on the files of its choice F
2
,
…
,
F
q. In general, the challenger C generates T
i for some 1
≤
i
≤
q.
(iii)
Challenge. The challenger C generates a challenge c
h
a
l and requests the adversary A to provide a proof of integrity for the file F
∗ (note that file F
∗ must differ from the F
i in query phase).
(iv)
Query2. Repeat Query1, the challenger C generates T
i for some i
,
q
+
1
≤
i
≤
n.
(v)
Forge. The adversary A computes a proof of integrity P for the file F
∗ according to challenge c
h
a
l and returns P to C.Figure 2
Integrity protection game.If theP can pass the verification, the adversary A wins the game.Definition 1.
An EoCo scheme guarantees data integrity if for any polynomial time adversaryA cannot win the game with nonnegligible probability.


### 4.3. Privacy Protection Model

In this subsection, we define a new privacy protection model,the ZK-privacy model, and prove that the scheme does not have any information leakage by showing that the attacker has zero knowledge during the audit process. The ZK-privacy model takes place between a challenger S such as cloud server and an adversary A such as malicious TPA. The game model includes the following steps and we summarize the critical operations in Figure 3.(i)
Setup. The challenger S runs the algorithm of key generation to generate key pair (
p
k
,
s
k
) and sends the public key p
k to the adversary A.
(ii)
Phase 1 (Steps 1–3). The adversary A adaptively makes queries: it selects a file F and sends it to the challenger S, then the challenger S generates the token, T
=
(
t
,
Φ
), for the file F, and sends it to the adversary A.
(iii)
Phase 2 (Steps 4–7). The adversary A chooses two files F
0, F
1, and F
0
≠
F
1, which are different from the files in Phase 1. Then the challenger S generates corresponding T
0
=
(
t
0
,
Φ
0
)
,
T
1
=
(
t
0
,
Φ
0
). Next, the challenger S randomly selects b
∈
{
0,1
} and sends t
b to A. The adversary A generates a challenge c
h
a
l to S. The challenger S generates proof, P
b
=
(
σ
b
,
μ
), to the A. Finally, the adversary A outputs a bit b
′ as a guess of the b. If b
′
=
b, the adversary wins the game.Figure 3
ZK-privacy game.Definition 2.
We define the advantage of the adversaryA as (1)
A
d
v
A
λ
=
V
i
e
w
A
b
=
0
-
V
i
e
w
A
b
=
1
TheV
i
e
w
A
(
b
=
0
o
r
1
) indicates the probability distribution of the view of A in the case of b
=
0 or b
=
1. An EoCo scheme guarantees that there is no an information leakage if A
d
v
A
(
λ
)
=
0.


## 4.1. System Model

Our scheme, EoCo, is built on the system model presented in Figure1. The model consists of three entities,Users,CSP Servers, andThe Third Party Auditor.(i)
Users. Cloud users own the data and want to save local storage and computing resources by uploading them to the cloud.
(ii)
CSP Servers. The CSP servers have a large amount of storage space available for users. At the same time, CSP servers provide effective cloud operations such as data update and queries and retrieve requests from the customers.
(iii)
The Third Party Auditor (TPA). The TPA has more ability and expertise than the clients. Users could ask a TPA help to audit the integrity of the outsourced data on behalf of them.Figure 1
The EoCo-based network system model.In our system model, our remote data integrity protection scheme consists of five critical operations,KeyGen,TokenGen,Challenge,Response, andCheckProof. A cloud user runsKeyGen to generate her/his public key p
k and private key s
k (with a security parameter k as its input). The user runs theTokenGen algorithm to generate a token for the file and outsources the file with corresponding token to the CSP server. When the user wants to check the correctness of her/his data, she/he may delegate the integrity audition to a TPA. The TPA creates c
h
a
l usingChallenge and sends it to the CSP server. The server runsResponse and returns the proof P to TPA. The TPA runsCheckProof to check whether it is correct, and if it is correct, the output is s
u
c
c
e
s
s; otherwise, the output is f
a
i
l
u
r
e.In the system shown in Figure1, we mainly take two threats in to account,the threat to integrity, andthe threat to privacy [25]. Accordingly, we classify attackers into two types based on the knowledge H that they processed.(i)
Threat to Integrity. The attacker observes the data D
A, the authentication identifier T, and the public key p
k, i.e., H
=
<
D
A
,
T
,
p
k
>. The purpose of such attacker is to produce a legitimate proof for the forge DA.
(ii)
Threat to Privacy. The attacker observes only the public key p
k and the proof P, i.e., H
=
<
P
,
p
k
>. The purpose of such attacker is to acquire additional knowledge, such as the content of data or the type of data.


## 4.2. Integrity Protection Model

We improve the integrity protection model proposed by Worku et al. [9] and through this model, we demonstrate two objectives.(1)
If the data are not stay the original state, an adversary cannot successfully construct a valid proof in polynomial time with nonnegligible probability.
(2)
If the adversary can always pass the verification, then it can be shown that the data remains intact.Our integrity protection model allows an adversary to query large filesF
i. The adversary A, may be a dishonest cloud service provider who interacts with a challenger C (users or TPA). The integrity game consists of the following steps and we illustrate the details in Figure 2.(i)
Setup. The challenger C runs the algorithm of key generation, sends the public key p
k to the adversary A, and retains the private key s
k secret.
(ii)
Query1. The adversary A adaptively makes tagging queries: it selects a file F
1 and sends it to C. The challenger C then computes the token T
1 and sends it back to A. The adversary A continues to query C for the token T
2
,
…
,
T
q on the files of its choice F
2
,
…
,
F
q. In general, the challenger C generates T
i for some 1
≤
i
≤
q.
(iii)
Challenge. The challenger C generates a challenge c
h
a
l and requests the adversary A to provide a proof of integrity for the file F
∗ (note that file F
∗ must differ from the F
i in query phase).
(iv)
Query2. Repeat Query1, the challenger C generates T
i for some i
,
q
+
1
≤
i
≤
n.
(v)
Forge. The adversary A computes a proof of integrity P for the file F
∗ according to challenge c
h
a
l and returns P to C.Figure 2
Integrity protection game.If theP can pass the verification, the adversary A wins the game.Definition 1.
An EoCo scheme guarantees data integrity if for any polynomial time adversaryA cannot win the game with nonnegligible probability.


## 4.3. Privacy Protection Model

In this subsection, we define a new privacy protection model,the ZK-privacy model, and prove that the scheme does not have any information leakage by showing that the attacker has zero knowledge during the audit process. The ZK-privacy model takes place between a challenger S such as cloud server and an adversary A such as malicious TPA. The game model includes the following steps and we summarize the critical operations in Figure 3.(i)
Setup. The challenger S runs the algorithm of key generation to generate key pair (
p
k
,
s
k
) and sends the public key p
k to the adversary A.
(ii)
Phase 1 (Steps 1–3). The adversary A adaptively makes queries: it selects a file F and sends it to the challenger S, then the challenger S generates the token, T
=
(
t
,
Φ
), for the file F, and sends it to the adversary A.
(iii)
Phase 2 (Steps 4–7). The adversary A chooses two files F
0, F
1, and F
0
≠
F
1, which are different from the files in Phase 1. Then the challenger S generates corresponding T
0
=
(
t
0
,
Φ
0
)
,
T
1
=
(
t
0
,
Φ
0
). Next, the challenger S randomly selects b
∈
{
0,1
} and sends t
b to A. The adversary A generates a challenge c
h
a
l to S. The challenger S generates proof, P
b
=
(
σ
b
,
μ
), to the A. Finally, the adversary A outputs a bit b
′ as a guess of the b. If b
′
=
b, the adversary wins the game.Figure 3
ZK-privacy game.Definition 2.
We define the advantage of the adversaryA as (1)
A
d
v
A
λ
=
V
i
e
w
A
b
=
0
-
V
i
e
w
A
b
=
1
TheV
i
e
w
A
(
b
=
0
o
r
1
) indicates the probability distribution of the view of A in the case of b
=
0 or b
=
1. An EoCo scheme guarantees that there is no an information leakage if A
d
v
A
(
λ
)
=
0.


## 5. Our Schemes

### 5.1. Definition and Framework

Our scheme mainly consists of five polynomial time algorithms: KeyGen, TokenGen, Challenge, Response, and CheckProof. The cloud user is represented byC, the cloud server is represented by S, and the third party auditor is represented by T
P
A.(i)
KeyGen(
1
k
)
→
(
p
k
,
s
k
)
.
K
e
y
G
e
n is a probabilistic key generation algorithm, which is set up and initialized by C. It takes as input a security parameter k and outputs a pair of key (
p
k
,
s
k
).
(ii)
TokenGen(
s
k
,
p
k
,
F
)
→
T
.
T
o
k
e
n
G
e
n is a deterministic algorithm to compute tokens. It takes as inputs a private key s
k, a public key p
k and a file F
=
(
m
1
,
…
,
m
n
). The output is the token T
=
(
t
,
Φ
=
{
σ
i
}
1
≤
i
≤
n
), where t is a file tag which includes a file n
a
m
e, Φ is an ordered collection, and σ
i is the unique authentication identifier corresponding to the blocks m
i in the file F.
(iii)
Challenge(
1
k
)
→
c
h
a
l
.
C
h
a
l
l
e
n
g
e is a deterministic algorithm. It takes as input a security parameter k. It outputs a challenge c
h
a
l.
(iv)
Response(
p
k
,
c
h
a
l
,
Φ
,
F
)
→
P
.
R
e
s
p
o
n
s
e is to create the proof of the data integrity corresponding to the received challenge. It takes as inputs a public key p
k, a file F, a challenge c
h
a
l, and an ordered set Φ. The output is an integrity proof P of the file F.
(v)
CheckProof(
p
k
,
P
,
c
h
a
l
,
t
)
→
(
s
u
c
.
or
f
a
i
l
.
)
.
C
h
e
c
k
P
r
o
o
f is the function to verify the returned proof P. It takes as inputs a public key p
k, a challenge c
h
a
l, and a proof P as input. It outputs s
u
c
c
e
s
s or f
a
i
l
u
r
e.A EoCo scheme can be summed up as two processes: one is the setup process to initialize the scheme, and the other is the verification process to confirm whether the data is integrity.(i)
Setup. The cloud user C has a file F and runs the algorithmKeyGen to generate the key pair (
p
k
,
s
k
). C then stores the key pair locally and uses it to run the algorithmTokenGen to generate a token, T
=
(
t
,
Φ
=
{
σ
i
}
1
≤
i
≤
n
). Finally, C sends T and F to S and deletes F and T from its local storage.
(ii)
Audition. TPA runs the algorithmChallenge to generate a challenge c
h
a
l corresponding to the target files. TPA sends c
h
a
l to the server S. After receiving c
h
a
l, S computes the proof P accordingly and returns the TPA the proof P and t by using the function R
e
s
p
o
n
s
e. The TPA validates P and t using the functionCheckProof.


### 5.2. Notations

In this subsection, we illustrate the parameters and notations used in our scheme. As listed in Table2, p is a large prime and the EoCo scheme is built on the group Z
p and supports a cyclic group G with a bilinear setting. Let g be an element of cyclic group. In the setup phase, the date owner splits the file F into n small file blocks, that is, F
=
(
m
1
,
…
,
m
n
), and for 1
≤
i
≤
n, every block m
i
∈
Z
p. H
:
{
0,1
}
∗
→
G is a secure hash function. The additional BLS signature used in our scheme is represented as S
S
i
g
(
·
). In addition, we take advantage of a pseudorandom permutation (PRP) π and a pseudorandom functions (PRF) f with the following parameters. We write f
k
(
x
) to denote f keyed with key k applied on input x.(i)
π
:
{
0,1
}
l
o
g
2
(
n
)
×
k
→
{
0,1
}
l
o
g
2
(
n
).
(ii)
f
:
{
0,1
}
∗
×
k
→
Z
p.Table 2
Notation list of symbols and parameters.
Symbols
Description
p
a large prime
Z
p
a group of integers with orderp
G
a cyclic group
g
an element of G
H
a hash function,{
0,1
}
∗
→
G
π
a pseudo-random permutation,{
0,1
}
l
o
g
2
(
n
)
×
K
→
{
0,1
}
l
o
g
2
(
n
)
f
a pseudo-random functions,{
0,1
}
∗
×
K
→
Z
p
S
S
i
g
(
⋅
)
an additional BLS signature
F
=
(
m
1
,
.
.
.
,
m
n
)
divide a big data fileF into n small file blocks and m
i
∈
Z
p


### 5.3. EoCo Scheme

(i)
KeyGen(
1
k
). The algorithm first generates a secure BLS signature key pair (
s
p
k
,
s
s
k
). Next, the algorithm randomly selects an element in the Z
p, x
←
Z
p, and computes v
←
g
x
∈
G. Then, the algorithm randomly selects an element in the G, u
←
G, and computes w
←
u
x. Finally, the algorithm returns public key p
k
=
(
s
p
k
,
g
,
v
,
u
,
w
) and private key s
k
=
(
s
s
k
,
x
).
(ii)
TokenGen(
s
k
,
p
k
,
F
=
(
m
1
,
…
,
m
n
)
). The algorithm randomly selects an element in the Z
p as a unique identifier of file F, n
a
m
e
←
Z
p, and calculates file identification tag by BLS signature, t
=
n
a
m
e
∥
S
S
i
g
s
s
k
(
n
a
m
e
). Next, the algorithm generates unique authentication identifier for each block m
i in the file, σ
i
←
(
H
(
W
i
)
·
u
m
i
)
x
∈
G. For 1
≤
i
≤
n, W
i
=
n
a
m
e
∥
i. The algorithm then outputs token T
=
(
t
,
Φ
=
{
σ
i
}
1
≤
i
≤
n
).
(iii)
Challenge(
1
k
). The algorithm first determines the number of file blocks c. According to the security parameters k, the algorithm randomly selects key k
1 for π and key k
2 for f. Finally, the algorithm returns c
h
a
l
=
(
c
,
k
1
,
k
2
).
(iv)
Response(
p
k
,
c
h
a
l
,
Φ
=
{
σ
i
}
1
≤
i
≤
n
)
,
F
). The algorithm first selects a secret random value r
←
Z
p. For 1
≤
j
≤
c, the algorithm computes i
j
=
π
k
1
(
j
) and a
j
=
f
k
2
(
j
), and the algorithm then computes aggregated authentication identifier σ
=
σ
i
1
a
1
·
σ
i
2
a
2
,
…
,
·
σ
i
c
a
c
·
w
r (note that σ
i
j is the i
j-th value in Φ). μ
=
v
μ
′
+
r
∈
G, and μ
′
=
a
1
m
i
1
+
,
…
,
a
c
m
i
c. Finally, the algorithm outputs proof P
=
(
σ
,
μ
).
(v)
CheckProof(
p
k
,
P
,
c
h
a
l
,
t
). The algorithm first verifies whether the file tag t is correct. If t is incorrect, the algorithm outputs f
a
i
l
u
r
e and quit; otherwise the algorithm extracts n
a
m
e and for 1
≤
j
≤
c, the algorithm calculates i
j
=
π
k
1
(
j
), a
j
=
f
k
2
(
j
) and W
i
j
=
n
a
m
e
∥
i
j. Finally, the algorithm verifies the following equation:(2)
e
σ
,
g
=
e
∏
j
=
1
c
H
W
i
j
a
j
,
v
·
e
u
,
μIf (2) holds, C
h
e
c
k
P
r
o
o
f returns s
u
c
c
e
s
s; otherwise, it returns f
a
i
l
u
r
e.


## 5.1. Definition and Framework

Our scheme mainly consists of five polynomial time algorithms: KeyGen, TokenGen, Challenge, Response, and CheckProof. The cloud user is represented byC, the cloud server is represented by S, and the third party auditor is represented by T
P
A.(i)
KeyGen(
1
k
)
→
(
p
k
,
s
k
)
.
K
e
y
G
e
n is a probabilistic key generation algorithm, which is set up and initialized by C. It takes as input a security parameter k and outputs a pair of key (
p
k
,
s
k
).
(ii)
TokenGen(
s
k
,
p
k
,
F
)
→
T
.
T
o
k
e
n
G
e
n is a deterministic algorithm to compute tokens. It takes as inputs a private key s
k, a public key p
k and a file F
=
(
m
1
,
…
,
m
n
). The output is the token T
=
(
t
,
Φ
=
{
σ
i
}
1
≤
i
≤
n
), where t is a file tag which includes a file n
a
m
e, Φ is an ordered collection, and σ
i is the unique authentication identifier corresponding to the blocks m
i in the file F.
(iii)
Challenge(
1
k
)
→
c
h
a
l
.
C
h
a
l
l
e
n
g
e is a deterministic algorithm. It takes as input a security parameter k. It outputs a challenge c
h
a
l.
(iv)
Response(
p
k
,
c
h
a
l
,
Φ
,
F
)
→
P
.
R
e
s
p
o
n
s
e is to create the proof of the data integrity corresponding to the received challenge. It takes as inputs a public key p
k, a file F, a challenge c
h
a
l, and an ordered set Φ. The output is an integrity proof P of the file F.
(v)
CheckProof(
p
k
,
P
,
c
h
a
l
,
t
)
→
(
s
u
c
.
or
f
a
i
l
.
)
.
C
h
e
c
k
P
r
o
o
f is the function to verify the returned proof P. It takes as inputs a public key p
k, a challenge c
h
a
l, and a proof P as input. It outputs s
u
c
c
e
s
s or f
a
i
l
u
r
e.A EoCo scheme can be summed up as two processes: one is the setup process to initialize the scheme, and the other is the verification process to confirm whether the data is integrity.(i)
Setup. The cloud user C has a file F and runs the algorithmKeyGen to generate the key pair (
p
k
,
s
k
). C then stores the key pair locally and uses it to run the algorithmTokenGen to generate a token, T
=
(
t
,
Φ
=
{
σ
i
}
1
≤
i
≤
n
). Finally, C sends T and F to S and deletes F and T from its local storage.
(ii)
Audition. TPA runs the algorithmChallenge to generate a challenge c
h
a
l corresponding to the target files. TPA sends c
h
a
l to the server S. After receiving c
h
a
l, S computes the proof P accordingly and returns the TPA the proof P and t by using the function R
e
s
p
o
n
s
e. The TPA validates P and t using the functionCheckProof.


## 5.2. Notations

In this subsection, we illustrate the parameters and notations used in our scheme. As listed in Table2, p is a large prime and the EoCo scheme is built on the group Z
p and supports a cyclic group G with a bilinear setting. Let g be an element of cyclic group. In the setup phase, the date owner splits the file F into n small file blocks, that is, F
=
(
m
1
,
…
,
m
n
), and for 1
≤
i
≤
n, every block m
i
∈
Z
p. H
:
{
0,1
}
∗
→
G is a secure hash function. The additional BLS signature used in our scheme is represented as S
S
i
g
(
·
). In addition, we take advantage of a pseudorandom permutation (PRP) π and a pseudorandom functions (PRF) f with the following parameters. We write f
k
(
x
) to denote f keyed with key k applied on input x.(i)
π
:
{
0,1
}
l
o
g
2
(
n
)
×
k
→
{
0,1
}
l
o
g
2
(
n
).
(ii)
f
:
{
0,1
}
∗
×
k
→
Z
p.Table 2
Notation list of symbols and parameters.
Symbols
Description
p
a large prime
Z
p
a group of integers with orderp
G
a cyclic group
g
an element of G
H
a hash function,{
0,1
}
∗
→
G
π
a pseudo-random permutation,{
0,1
}
l
o
g
2
(
n
)
×
K
→
{
0,1
}
l
o
g
2
(
n
)
f
a pseudo-random functions,{
0,1
}
∗
×
K
→
Z
p
S
S
i
g
(
⋅
)
an additional BLS signature
F
=
(
m
1
,
.
.
.
,
m
n
)
divide a big data fileF into n small file blocks and m
i
∈
Z
p


## 5.3. EoCo Scheme

(i)
KeyGen(
1
k
). The algorithm first generates a secure BLS signature key pair (
s
p
k
,
s
s
k
). Next, the algorithm randomly selects an element in the Z
p, x
←
Z
p, and computes v
←
g
x
∈
G. Then, the algorithm randomly selects an element in the G, u
←
G, and computes w
←
u
x. Finally, the algorithm returns public key p
k
=
(
s
p
k
,
g
,
v
,
u
,
w
) and private key s
k
=
(
s
s
k
,
x
).
(ii)
TokenGen(
s
k
,
p
k
,
F
=
(
m
1
,
…
,
m
n
)
). The algorithm randomly selects an element in the Z
p as a unique identifier of file F, n
a
m
e
←
Z
p, and calculates file identification tag by BLS signature, t
=
n
a
m
e
∥
S
S
i
g
s
s
k
(
n
a
m
e
). Next, the algorithm generates unique authentication identifier for each block m
i in the file, σ
i
←
(
H
(
W
i
)
·
u
m
i
)
x
∈
G. For 1
≤
i
≤
n, W
i
=
n
a
m
e
∥
i. The algorithm then outputs token T
=
(
t
,
Φ
=
{
σ
i
}
1
≤
i
≤
n
).
(iii)
Challenge(
1
k
). The algorithm first determines the number of file blocks c. According to the security parameters k, the algorithm randomly selects key k
1 for π and key k
2 for f. Finally, the algorithm returns c
h
a
l
=
(
c
,
k
1
,
k
2
).
(iv)
Response(
p
k
,
c
h
a
l
,
Φ
=
{
σ
i
}
1
≤
i
≤
n
)
,
F
). The algorithm first selects a secret random value r
←
Z
p. For 1
≤
j
≤
c, the algorithm computes i
j
=
π
k
1
(
j
) and a
j
=
f
k
2
(
j
), and the algorithm then computes aggregated authentication identifier σ
=
σ
i
1
a
1
·
σ
i
2
a
2
,
…
,
·
σ
i
c
a
c
·
w
r (note that σ
i
j is the i
j-th value in Φ). μ
=
v
μ
′
+
r
∈
G, and μ
′
=
a
1
m
i
1
+
,
…
,
a
c
m
i
c. Finally, the algorithm outputs proof P
=
(
σ
,
μ
).
(v)
CheckProof(
p
k
,
P
,
c
h
a
l
,
t
). The algorithm first verifies whether the file tag t is correct. If t is incorrect, the algorithm outputs f
a
i
l
u
r
e and quit; otherwise the algorithm extracts n
a
m
e and for 1
≤
j
≤
c, the algorithm calculates i
j
=
π
k
1
(
j
), a
j
=
f
k
2
(
j
) and W
i
j
=
n
a
m
e
∥
i
j. Finally, the algorithm verifies the following equation:(2)
e
σ
,
g
=
e
∏
j
=
1
c
H
W
i
j
a
j
,
v
·
e
u
,
μIf (2) holds, C
h
e
c
k
P
r
o
o
f returns s
u
c
c
e
s
s; otherwise, it returns f
a
i
l
u
r
e.


## 6. Scheme Analysis

### 6.1. Correctness

In this subsection, we discuss the correctness of our scheme; that is, the CSPs will definitely pass through the audition if they follow the protocol honestly. By signing then
a
m
e of a file with an additional BLS signature, we can prevent an adversary from tampering with the n
a
m
e. We use a hash function to ensure that the file tag, n
a
m
e, is perfectly embedded in the authentication identifier. We make use of a PRP function and a PRF function to ensure the randomness of the challenge content and the security of the response. If the data is kept properly, the correctness of the verification equation (2) can be shown as follows:(3)
e
∏
j
=
1
c
H
W
i
j
a
j
,
v
·
e
u
,
μ
=
e
∏
j
=
1
c
H
W
i
j
a
j
,
g
x
·
e
u
μ
′
+
r
,
g
x
=
e
∏
j
=
1
c
H
W
i
j
a
j
u
μ
′
,
g
x
·
e
u
r
,
g
x
=
e
∏
j
=
1
c
σ
i
j
a
j
,
g
·
e
u
x
r
,
g
=
e
∏
j
=
1
c
σ
i
j
a
j
w
r
,
g
=
e
σ
,
g


### 6.2. Integrity Protection

The integrity protection of EoCo is based on the symmetric co-CDH problem or standard CDH problem.Theorem 3.
Under the CDH assumptions, EoCo guarantees data integrity protection in the random oracle model.
We first propose a simplified scheme, S-EoCo. By proving the security of S-EoCo, we can prove the security of EoCo. S-EoCo and EoCo differ only in theKenGen andResponse algorithms as follows:(i)
KeyGen(
1
k
). The algorithm first generates a secure BLS signature key pair (
s
p
k
,
s
s
k
). Next, the algorithm randomly selects an element in the Z
p, x
←
Z
p, and computes v
←
g
x
∈
G. Then, the algorithm randomly selects an element in the G, u
←
G. Finally, the algorithm returns public key p
k
=
(
s
p
k
,
g
,
v
,
u
) and private key s
k
=
(
s
s
k
,
x
).
(ii)
Response(
p
k
,
c
h
a
l
,
Φ
=
{
σ
i
}
1
≤
i
≤
n
)
,
F
). For 1
≤
j
≤
c, the algorithm computes i
j
=
π
k
1
(
j
)
,
a
j
=
f
k
2
(
j
). Then, for I
=
{
i
1
,
i
2
,
…
,
i
c
}, the algorithm computes aggregated authentication identifier σ
=
σ
i
1
a
1
·
σ
i
2
a
2
,
…
,
·
σ
i
c
a
c, μ
=
v
μ
′
∈
G, where μ
′
=
a
1
m
i
1
+
,
…
,
a
c
m
i
c. Finally, the algorithm outputs proof P
=
(
σ
,
μ
).Proof.
We reduce the security of our S-EoCo scheme to the security of the CDH problem. We model hash functionH
(
·
) as random oracle.
If an adversaryA can break the integrity protection of the S-EoCo scheme, we show how to construct an adversary C that uses A in order to break CDH problem.
For the CDH problem,C is given (
g
,
g
α
,
h
)
∈
G and needs to calculate h
α. Then C will play the role of the challenger in the integrity protection game and will interact with A as follows.(i)
Setup. The challenger C selects a secret key pair (
s
p
k
,
s
s
k
) and gets p
k
=
(
s
p
k
,
g
,
v
,
u
), where u
=
g
a
h
b, a
←
Z
,
b
←
Z
p, v
=
g
α. Then C sends public key to the adversary A.
(ii)
Query1. The adversary A adaptively presents queries in the way that it selects different files F
1
,
…
,
F
n and sends them to C to create T
o
k
e
ns. In order to answer queries, C simulates in a random oracle machine as follows:
(1)
ForF
=
{
m
1
,
m
2
,
…
,
m
n
}, randomly selects an element in group Z
p as the unique identifier of file F, n
a
m
e
←
Z
p, and calculates file identification tags t
=
n
a
m
e
∥
S
S
i
g
s
s
k
(
n
a
m
e
).
(2)
(a)
WhenA queries j for hash value, C first checks whether j is in the hash tuple list (
j
,
H
(
j
)
). If it is in the list, C sends H
(
j
) to A as the answer; otherwise, C randomly selects and replies C an elements in G, ω
←
G, as H
(
j
), and adds H
(
j
) to the hash tuple list (
j
,
H
(
j
)
).
(b)
WhenA performs the identifier query, C calculates W
i
=
n
a
m
e
∥
i. If W
i
=
j, C announcesfailure; otherwise, C randomly selects r
i
←
Z
p, calculates H
(
W
i
)
=
g
r
i
·
g
-
a
m
i
·
h
-
b
m
i, and builds a list of identifiers (
W
i
,
m
i
,
r
i
,
H
(
W
i
)
,
σ
i
). C can compute σ
m
i using the formula below. (4)
σ
m
i
=
H
W
i
·
u
m
i
α
=
g
r
i
·
g
-
a
m
i
·
h
-
b
m
i
·
u
m
i
α
=
g
r
i
·
g
-
a
m
i
·
h
-
b
m
i
·
g
a
m
i
·
h
b
m
i
α
=
g
r
i
α
=
g
α
r
i
(3)
C sends the file identifier T
=
(
t
,
Φ
=
{
σ
i
}
1
≤
i
≤
n
)
) to A.
(iii)
Challenge. For files F
∗
=
{
m
1
∗
,
m
2
∗
,
…
,
m
n
∗
}, C sends challenge c
h
a
l to A, and F
∗ is different from above F that have been query.
(iv)
Query2. Repeat the Query1, but A cannot query the file blocks included in c
h
a
l.
(v)
Forge.
A creates and returns P to C according to challenge c
h
a
l. If P can pass through the verification, A wins the game.
Suppose that an honest cloud server computes a proof,P
=
(
σ
,
μ
), then the following verification formula should be satisfied:(5)
e
σ
,
g
=
e
∏
i
∈
I
H
W
i
a
i
,
v
·
e
u
,
μ
Suppose that the adversaryA wins games with nonnegligible probability. The proof output by A is P
∗
=
(
σ
∗
,
μ
∗
) that can pass the verification with nonnegligible probability, thus formula (6) is satisfied.(6)
e
σ
∗
,
g
=
e
∏
i
∈
I
H
W
i
a
i
,
v
·
e
u
,
μ
∗
According to the game,μ
≠
μ
∗. Let Δ
μ
′
=
μ
′
∗
-
μ
′. Because G is a multiplicative cyclic group, we can find an inverse element of σ in the group. We substitute σ
-
1 for σ in formula (5) to get the deformation of formula (5).(7)
e
σ
-
1
,
g
=
e
∏
i
∈
I
H
W
i
a
i
,
v
-
1
·
e
u
,
μ
-
1
We multiplyσ
∗ by σ
-
1 and obtain the following equation:(8)
e
σ
∗
σ
-
1
,
g
=
e
u
,
μ
∗
μ
-
1
=
e
u
,
v
μ
′
∗
-
μ
′
=
e
u
,
v
Δ
μ
′
=
e
u
Δ
μ
′
,
v
Becauseu
=
g
a
h
b, we replace u in formula (8).(9)
e
σ
∗
σ
-
1
,
g
=
e
g
a
h
b
α
Δ
μ
′
,
g
=
e
g
a
α
Δ
μ
′
h
b
α
Δ
μ
′
,
g
=
e
v
a
Δ
μ
′
h
α
b
Δ
μ
′
,
g
The above equation can be further deformed as follows:(10)
e
σ
∗
σ
-
1
v
-
a
Δ
μ
′
,
g
-
b
Δ
μ
′
=
e
h
α
,
g
It can be derived from formula (10) that h
α
=
(
σ
∗
σ
-
1
v
-
a
Δ
μ
′
)
-
b
Δ
μ
′. C takes back μ
′
∗ from the adversary A and calculates Δ
μ
′
=
μ
′
∗
-
μ
′. It means that as long as b
Δ
μ
′
≠
0
mod
⁡
p
C can solve the CDH problem. As Δ
μ
′
≠
0
mod
⁡
p, the probability that b
Δ
μ
′
≠
0 is 1
-
1
/
p, which is nonnegligible. And the probability that simulation failure possibility of C is 1
/
q is negligible. So if the adversary wins the game with a nonnegligible probability, the CDH problem can be solved with a nonnegligible probability. Aggregation tags inResponse in the EoCo scheme is that σ
=
σ
i
1
a
1
·
σ
i
2
a
2
,
…
,
·
σ
i
c
a
c
·
w
r and μ
=
v
μ
′
+
r
∈
G. We add w
r on the basis of S-EoCo that makes scheme stronger.
Here we proved the Theorem3.


### 6.3. Privacy Preserving

Theorem 4.
According to Definition2, an adversary is completely zero knowledge if, for any polynomial time algorithm A, A
d
v
A
(
λ
)
=
0.Proof.
To prove Theorem4, we construct a simulator S to interact with an adversary A following the steps below.(1)
A selects two different files F
0
=
(
m
1
(
0
)
,
…
,
m
n
(
0
)
) and F
1
=
(
m
1
(
1
)
,
…
,
m
n
(
1
)
), for 1
≤
i
≤
n, which satisfy m
i
(
0
)
≠
m
i
(
1
).
(2)
The simulatorS generates T
0
=
(
t
0
,
Φ
0
) and T
1
=
(
t
1
,
Φ
1
) for the files F
0 and F
1, respectively. Then S randomly selects b
∈
{
0,1
} and sends t
b to A.
(3)
WhenA received t
b, A randomly generates a challenge c
h
a
l
=
{
c
,
k
1
,
k
2
} and sends c
h
a
l to S request proof of F
b
(4)
The simulatorS calculates and sends response proof P
b
=
(
σ
b
,
μ
) to A.
(5)
The identifier inP
b is that σ
b
=
σ
i
1
a
1
·
σ
i
2
a
2
,
…
,
·
σ
i
c
a
c
·
w
r, μ
=
v
μ
′
+
r
∈
G, and μ
′
=
a
1
m
i
1
(
b
)
+
,
…
,
a
c
m
i
c
(
b
), and it satisfies(11)
e
σ
,
g
=
e
∏
i
∈
I
H
W
i
a
i
,
v
·
e
u
,
μ
From the perspective ofA, A can only see (
P
b
,
F
0
,
F
1
,
p
k
). Since A cannot know the value of r (unless A can solve the discrete logarithm (DL) problem) and r is randomly and uniformly distributed, for the adversary A, P
0 and P
1 also are uniformly distributed.
Sincep
k is public, so V
i
e
w
A
(
P
0
,
F
0
,
F
1
,
p
k
) and V
i
e
w
A
(
P
1
,
F
0
,
F
1
,
p
k
) have the same probability distribution. The advantage of the adversary A is as follows:(12)
A
d
v
A
λ
=
P
r
V
i
e
w
A
P
0
,
F
0
,
F
1
,
p
k
-
P
r
V
i
e
w
A
P
1
,
F
0
,
F
1
,
p
k
=
0
The above equation shows that the protocol is strict zero knowledge to the adversaryA, and thus, the adversary cannot get any information through the auditing process.
Here we complete the proof.


### 6.4. Batch Auditing

Sometimes, a TPA will audit multiple files on behalf of different users. While one by one validation is too tedious and inefficient, it is desired that the TPA could parallelly audit the integrity of multiple cloud user data. Suppose thatQ cloud users are entrusted with the same TPA. We slightly modify our scheme by using BLS signature to aggregate different signatures and thus provide the effective verification for all Q users/files simultaneously. In fact, our attribute of batch auditing is to enhance the audit efficiency of TPA. Therefore, in EoCo scheme, we only need to make minor modifications on theCheckProof algorithm.(i)
CheckProof(
p
k
,
P
,
c
h
a
l
,
t
). For 1
≤
l
≤
Q, the algorithm first verifies whether the file tag t
l is correct. The algorithm then outputs f
a
i
l
u
r
e if it is wrong; otherwise, the algorithm extracts n
a
m
e
l and continues. Next, for 1
≤
j
≤
c, the algorithm calculates i
j
=
π
k
1
(
j
)
,
a
j
=
f
k
2
(
j
) and (
W
i
j
)
l
=
n
a
m
e
l
∥
i
j and computes aggregate authentication identifier σ
Q
=
∏
l
=
1
Q
‍
σ
l. Finally, the algorithm verifies the following equation:(13)
∏
l
=
1
Q
e
∏
j
=
1
c
H
W
i
j
l
a
j
,
v
l
·
e
u
,
μ
l
=
e
σ
Q
,
gWe validate the correctness of batch audition scheme below and show that the honest CSPs will pass the audition successfully if they follow the protocol.(14)
∏
l
=
1
Q
e
∏
j
=
1
c
H
W
i
j
l
a
j
,
v
l
·
e
u
,
μ
l
=
∏
l
=
1
Q
e
∏
j
=
1
c
H
W
i
j
l
a
j
u
μ
l
′
,
g
x
l
·
e
u
r
l
,
g
x
l
=
∏
l
=
1
Q
e
∏
j
=
1
c
σ
i
j
l
a
j
,
g
·
e
u
x
l
r
l
,
g
=
∏
l
=
1
Q
e
∏
j
=
1
c
σ
i
j
l
a
j
,
g
·
e
w
l
r
l
,
g
=
∏
l
=
1
Q
e
∏
j
=
1
c
σ
i
j
l
a
j
·
w
l
r
l
,
g
=
e
∏
l
=
1
Q
σ
l
,
g
=
e
σ
Q
,
g


## 6.1. Correctness

In this subsection, we discuss the correctness of our scheme; that is, the CSPs will definitely pass through the audition if they follow the protocol honestly. By signing then
a
m
e of a file with an additional BLS signature, we can prevent an adversary from tampering with the n
a
m
e. We use a hash function to ensure that the file tag, n
a
m
e, is perfectly embedded in the authentication identifier. We make use of a PRP function and a PRF function to ensure the randomness of the challenge content and the security of the response. If the data is kept properly, the correctness of the verification equation (2) can be shown as follows:(3)
e
∏
j
=
1
c
H
W
i
j
a
j
,
v
·
e
u
,
μ
=
e
∏
j
=
1
c
H
W
i
j
a
j
,
g
x
·
e
u
μ
′
+
r
,
g
x
=
e
∏
j
=
1
c
H
W
i
j
a
j
u
μ
′
,
g
x
·
e
u
r
,
g
x
=
e
∏
j
=
1
c
σ
i
j
a
j
,
g
·
e
u
x
r
,
g
=
e
∏
j
=
1
c
σ
i
j
a
j
w
r
,
g
=
e
σ
,
g


## 6.2. Integrity Protection

The integrity protection of EoCo is based on the symmetric co-CDH problem or standard CDH problem.Theorem 3.
Under the CDH assumptions, EoCo guarantees data integrity protection in the random oracle model.
We first propose a simplified scheme, S-EoCo. By proving the security of S-EoCo, we can prove the security of EoCo. S-EoCo and EoCo differ only in theKenGen andResponse algorithms as follows:(i)
KeyGen(
1
k
). The algorithm first generates a secure BLS signature key pair (
s
p
k
,
s
s
k
). Next, the algorithm randomly selects an element in the Z
p, x
←
Z
p, and computes v
←
g
x
∈
G. Then, the algorithm randomly selects an element in the G, u
←
G. Finally, the algorithm returns public key p
k
=
(
s
p
k
,
g
,
v
,
u
) and private key s
k
=
(
s
s
k
,
x
).
(ii)
Response(
p
k
,
c
h
a
l
,
Φ
=
{
σ
i
}
1
≤
i
≤
n
)
,
F
). For 1
≤
j
≤
c, the algorithm computes i
j
=
π
k
1
(
j
)
,
a
j
=
f
k
2
(
j
). Then, for I
=
{
i
1
,
i
2
,
…
,
i
c
}, the algorithm computes aggregated authentication identifier σ
=
σ
i
1
a
1
·
σ
i
2
a
2
,
…
,
·
σ
i
c
a
c, μ
=
v
μ
′
∈
G, where μ
′
=
a
1
m
i
1
+
,
…
,
a
c
m
i
c. Finally, the algorithm outputs proof P
=
(
σ
,
μ
).Proof.
We reduce the security of our S-EoCo scheme to the security of the CDH problem. We model hash functionH
(
·
) as random oracle.
If an adversaryA can break the integrity protection of the S-EoCo scheme, we show how to construct an adversary C that uses A in order to break CDH problem.
For the CDH problem,C is given (
g
,
g
α
,
h
)
∈
G and needs to calculate h
α. Then C will play the role of the challenger in the integrity protection game and will interact with A as follows.(i)
Setup. The challenger C selects a secret key pair (
s
p
k
,
s
s
k
) and gets p
k
=
(
s
p
k
,
g
,
v
,
u
), where u
=
g
a
h
b, a
←
Z
,
b
←
Z
p, v
=
g
α. Then C sends public key to the adversary A.
(ii)
Query1. The adversary A adaptively presents queries in the way that it selects different files F
1
,
…
,
F
n and sends them to C to create T
o
k
e
ns. In order to answer queries, C simulates in a random oracle machine as follows:
(1)
ForF
=
{
m
1
,
m
2
,
…
,
m
n
}, randomly selects an element in group Z
p as the unique identifier of file F, n
a
m
e
←
Z
p, and calculates file identification tags t
=
n
a
m
e
∥
S
S
i
g
s
s
k
(
n
a
m
e
).
(2)
(a)
WhenA queries j for hash value, C first checks whether j is in the hash tuple list (
j
,
H
(
j
)
). If it is in the list, C sends H
(
j
) to A as the answer; otherwise, C randomly selects and replies C an elements in G, ω
←
G, as H
(
j
), and adds H
(
j
) to the hash tuple list (
j
,
H
(
j
)
).
(b)
WhenA performs the identifier query, C calculates W
i
=
n
a
m
e
∥
i. If W
i
=
j, C announcesfailure; otherwise, C randomly selects r
i
←
Z
p, calculates H
(
W
i
)
=
g
r
i
·
g
-
a
m
i
·
h
-
b
m
i, and builds a list of identifiers (
W
i
,
m
i
,
r
i
,
H
(
W
i
)
,
σ
i
). C can compute σ
m
i using the formula below. (4)
σ
m
i
=
H
W
i
·
u
m
i
α
=
g
r
i
·
g
-
a
m
i
·
h
-
b
m
i
·
u
m
i
α
=
g
r
i
·
g
-
a
m
i
·
h
-
b
m
i
·
g
a
m
i
·
h
b
m
i
α
=
g
r
i
α
=
g
α
r
i
(3)
C sends the file identifier T
=
(
t
,
Φ
=
{
σ
i
}
1
≤
i
≤
n
)
) to A.
(iii)
Challenge. For files F
∗
=
{
m
1
∗
,
m
2
∗
,
…
,
m
n
∗
}, C sends challenge c
h
a
l to A, and F
∗ is different from above F that have been query.
(iv)
Query2. Repeat the Query1, but A cannot query the file blocks included in c
h
a
l.
(v)
Forge.
A creates and returns P to C according to challenge c
h
a
l. If P can pass through the verification, A wins the game.
Suppose that an honest cloud server computes a proof,P
=
(
σ
,
μ
), then the following verification formula should be satisfied:(5)
e
σ
,
g
=
e
∏
i
∈
I
H
W
i
a
i
,
v
·
e
u
,
μ
Suppose that the adversaryA wins games with nonnegligible probability. The proof output by A is P
∗
=
(
σ
∗
,
μ
∗
) that can pass the verification with nonnegligible probability, thus formula (6) is satisfied.(6)
e
σ
∗
,
g
=
e
∏
i
∈
I
H
W
i
a
i
,
v
·
e
u
,
μ
∗
According to the game,μ
≠
μ
∗. Let Δ
μ
′
=
μ
′
∗
-
μ
′. Because G is a multiplicative cyclic group, we can find an inverse element of σ in the group. We substitute σ
-
1 for σ in formula (5) to get the deformation of formula (5).(7)
e
σ
-
1
,
g
=
e
∏
i
∈
I
H
W
i
a
i
,
v
-
1
·
e
u
,
μ
-
1
We multiplyσ
∗ by σ
-
1 and obtain the following equation:(8)
e
σ
∗
σ
-
1
,
g
=
e
u
,
μ
∗
μ
-
1
=
e
u
,
v
μ
′
∗
-
μ
′
=
e
u
,
v
Δ
μ
′
=
e
u
Δ
μ
′
,
v
Becauseu
=
g
a
h
b, we replace u in formula (8).(9)
e
σ
∗
σ
-
1
,
g
=
e
g
a
h
b
α
Δ
μ
′
,
g
=
e
g
a
α
Δ
μ
′
h
b
α
Δ
μ
′
,
g
=
e
v
a
Δ
μ
′
h
α
b
Δ
μ
′
,
g
The above equation can be further deformed as follows:(10)
e
σ
∗
σ
-
1
v
-
a
Δ
μ
′
,
g
-
b
Δ
μ
′
=
e
h
α
,
g
It can be derived from formula (10) that h
α
=
(
σ
∗
σ
-
1
v
-
a
Δ
μ
′
)
-
b
Δ
μ
′. C takes back μ
′
∗ from the adversary A and calculates Δ
μ
′
=
μ
′
∗
-
μ
′. It means that as long as b
Δ
μ
′
≠
0
mod
⁡
p
C can solve the CDH problem. As Δ
μ
′
≠
0
mod
⁡
p, the probability that b
Δ
μ
′
≠
0 is 1
-
1
/
p, which is nonnegligible. And the probability that simulation failure possibility of C is 1
/
q is negligible. So if the adversary wins the game with a nonnegligible probability, the CDH problem can be solved with a nonnegligible probability. Aggregation tags inResponse in the EoCo scheme is that σ
=
σ
i
1
a
1
·
σ
i
2
a
2
,
…
,
·
σ
i
c
a
c
·
w
r and μ
=
v
μ
′
+
r
∈
G. We add w
r on the basis of S-EoCo that makes scheme stronger.
Here we proved the Theorem3.


## 6.3. Privacy Preserving

Theorem 4.
According to Definition2, an adversary is completely zero knowledge if, for any polynomial time algorithm A, A
d
v
A
(
λ
)
=
0.Proof.
To prove Theorem4, we construct a simulator S to interact with an adversary A following the steps below.(1)
A selects two different files F
0
=
(
m
1
(
0
)
,
…
,
m
n
(
0
)
) and F
1
=
(
m
1
(
1
)
,
…
,
m
n
(
1
)
), for 1
≤
i
≤
n, which satisfy m
i
(
0
)
≠
m
i
(
1
).
(2)
The simulatorS generates T
0
=
(
t
0
,
Φ
0
) and T
1
=
(
t
1
,
Φ
1
) for the files F
0 and F
1, respectively. Then S randomly selects b
∈
{
0,1
} and sends t
b to A.
(3)
WhenA received t
b, A randomly generates a challenge c
h
a
l
=
{
c
,
k
1
,
k
2
} and sends c
h
a
l to S request proof of F
b
(4)
The simulatorS calculates and sends response proof P
b
=
(
σ
b
,
μ
) to A.
(5)
The identifier inP
b is that σ
b
=
σ
i
1
a
1
·
σ
i
2
a
2
,
…
,
·
σ
i
c
a
c
·
w
r, μ
=
v
μ
′
+
r
∈
G, and μ
′
=
a
1
m
i
1
(
b
)
+
,
…
,
a
c
m
i
c
(
b
), and it satisfies(11)
e
σ
,
g
=
e
∏
i
∈
I
H
W
i
a
i
,
v
·
e
u
,
μ
From the perspective ofA, A can only see (
P
b
,
F
0
,
F
1
,
p
k
). Since A cannot know the value of r (unless A can solve the discrete logarithm (DL) problem) and r is randomly and uniformly distributed, for the adversary A, P
0 and P
1 also are uniformly distributed.
Sincep
k is public, so V
i
e
w
A
(
P
0
,
F
0
,
F
1
,
p
k
) and V
i
e
w
A
(
P
1
,
F
0
,
F
1
,
p
k
) have the same probability distribution. The advantage of the adversary A is as follows:(12)
A
d
v
A
λ
=
P
r
V
i
e
w
A
P
0
,
F
0
,
F
1
,
p
k
-
P
r
V
i
e
w
A
P
1
,
F
0
,
F
1
,
p
k
=
0
The above equation shows that the protocol is strict zero knowledge to the adversaryA, and thus, the adversary cannot get any information through the auditing process.
Here we complete the proof.


## 6.4. Batch Auditing

Sometimes, a TPA will audit multiple files on behalf of different users. While one by one validation is too tedious and inefficient, it is desired that the TPA could parallelly audit the integrity of multiple cloud user data. Suppose thatQ cloud users are entrusted with the same TPA. We slightly modify our scheme by using BLS signature to aggregate different signatures and thus provide the effective verification for all Q users/files simultaneously. In fact, our attribute of batch auditing is to enhance the audit efficiency of TPA. Therefore, in EoCo scheme, we only need to make minor modifications on theCheckProof algorithm.(i)
CheckProof(
p
k
,
P
,
c
h
a
l
,
t
). For 1
≤
l
≤
Q, the algorithm first verifies whether the file tag t
l is correct. The algorithm then outputs f
a
i
l
u
r
e if it is wrong; otherwise, the algorithm extracts n
a
m
e
l and continues. Next, for 1
≤
j
≤
c, the algorithm calculates i
j
=
π
k
1
(
j
)
,
a
j
=
f
k
2
(
j
) and (
W
i
j
)
l
=
n
a
m
e
l
∥
i
j and computes aggregate authentication identifier σ
Q
=
∏
l
=
1
Q
‍
σ
l. Finally, the algorithm verifies the following equation:(13)
∏
l
=
1
Q
e
∏
j
=
1
c
H
W
i
j
l
a
j
,
v
l
·
e
u
,
μ
l
=
e
σ
Q
,
gWe validate the correctness of batch audition scheme below and show that the honest CSPs will pass the audition successfully if they follow the protocol.(14)
∏
l
=
1
Q
e
∏
j
=
1
c
H
W
i
j
l
a
j
,
v
l
·
e
u
,
μ
l
=
∏
l
=
1
Q
e
∏
j
=
1
c
H
W
i
j
l
a
j
u
μ
l
′
,
g
x
l
·
e
u
r
l
,
g
x
l
=
∏
l
=
1
Q
e
∏
j
=
1
c
σ
i
j
l
a
j
,
g
·
e
u
x
l
r
l
,
g
=
∏
l
=
1
Q
e
∏
j
=
1
c
σ
i
j
l
a
j
,
g
·
e
w
l
r
l
,
g
=
∏
l
=
1
Q
e
∏
j
=
1
c
σ
i
j
l
a
j
·
w
l
r
l
,
g
=
e
∏
l
=
1
Q
σ
l
,
g
=
e
σ
Q
,
g


## 7. Evaluation

In this section, we evaluate the performance of our proposed scheme in the following three aspects:(1)
Computational complexity: the cost of the setup phase, the cost of producing response proof by S, and the cost of verify response proof by an auditor.
(2)
Block complexity: S needs the number of file blocks to be accessed according to the challenge.
(3)
Communication complexity: the data size and bandwidth of communication between an auditor and a CSP.Suppose that the EoCo choosesc file blocks for audition and the security parameter is k. The large prime number p should be 2
k according to the analysis by Shacham et al. [5]. If the security level is 80 bits, then |
p
|
=
160 bits. This determines the required block size to achieve the desired security level. We compare the EoCo with the scheme in [5, 8, 9] in terms of computation complexity and communication complexity in this section.


### 7.1. Communication Complexity

We can see from Table3 that the number of bits required of SW-[5] is 2
n
|
p
|
+
2
|
p
| bits. The number of bits required of Wang-[8] is 2
n
|
p
|
+
3
|
p
| bits. The number of bits required of Worku-[9] is 6
|
p
| bits. The EoCo’ the number of bits required is 5
|
p
| bits. From this, we can see that the EoCo has the smallest communication overhead, which can greatly reduce the I/O burden of cloud providers and increase bandwidth utilization.Table 3
Communication complexity comparison.
SW-[5]
Wang-[8]
Worku-[9]
Our scheme
Challenge form and the number of bits required
{
(
i
,
ν
i
)
}
1
≤
i
≤
n
{
(
i
,
ν
i
)
}
1
≤
i
≤
n
(
c
,
k
1
,
k
2
)
(
c
,
k
1
,
k
2
)
2
n
|
p
|bits
2
n
|
p
|bits
3
|
p
|bits
3
|
p
|bits
Response form and the number of bits required
(
σ
,
μ
)
(
σ
,
μ
,
R
)
(
σ
,
μ
,
R
)
(
σ
,
μ
)
2
|
p
|bits
3
|
p
|bits
3
|
p
|bits
2
|
p
|bits
Entire Overhead
O
(
n
)
O
(
n
)
O
(
1
)
O
(
1
)


### 7.2. Computation Complexity

In order to calculate the cost of computing on both sides of the auditor and cloud service provider, we detail the operations on the basic computational symbols in Table4. We can see comparison of several schemes from Table 5 in three aspects.(i)
Server computation overhead: for cloud service providers, we see that the Worku-[9] is obviously less than Wang-[8]. While the EoCo is compared with the Worku-[9], the EoCo adds one more exponential operation, but reduces one hash operation. Generally speaking, one hash is more time-consuming than the exponential operation, so that the EoCo is more efficient on this side.
(ii)
Auditor computation overhead: for the auditor, Wang-[8] and Worku-[9] are only slightly different in efficiency; the latter uses one-time exponential operation less than the former. Although our scheme uses one-time bilinear mapping more than Worku-[9], our scheme uses one-time hash operation, three-time exponential operation and two-time multiplication operation less than Worku-[9]. In this respect, the EoCo has a great promotion.
(iii)
Setup phase overhead: because the schemes are based on BLS short signatures, the computational overhead of the setup phase is equal.Table 4
Notation of cryptographic operations.
Operations
Description
H
a
s
h
Z
p
t
t map-to-Z
p operations
H
a
s
h
G
t
t map-to-G operations
M
u
l
t
G
t
t multiplication in group G
M
u
l
t
Z
p
t
t multiplication in groupZ
p
E
x
p
G
t
t exponentiations in group G
B
M
G
t
t bilinear mappings among elements of G
A
d
d
G
t
t additions on group G
A
d
d
Z
p
t
t additions on groupZ
p
c
-
M
u
l
t
E
x
p
G
t
(
l
)
t c-term exponentiations in group G,l
≤
|
p
|Table 5
Computation comparison.
Our scheme
Wang-[8]
Worku-[9]
Server computation overhead
M
u
l
t
G
c
+
E
x
p
G
2
+
M
u
l
t
G
c
-
1
+
B
M
G
1
+
M
u
l
t
G
c
-
1
+
E
x
p
G
1
+
A
d
d
Z
p
c
+
M
u
l
t
Z
p
c
-
1
+
E
x
p
G
1
+
A
d
d
Z
p
c
+
M
u
l
t
Z
p
c
+
1
+
A
d
d
Z
p
c
+
M
u
l
t
Z
p
c
+
1
+
c
-
M
u
l
t
E
x
p
G
1
(
a
i
)
H
a
s
h
Z
p
1
+
c
-
M
u
l
t
E
x
p
G
1
(
ν
i
)
H
a
s
h
Z
p
1
+
c
-
M
u
l
t
E
x
p
G
1
(
ν
i
)
Auditor computation overhead
H
a
s
h
G
c
+
B
M
G
3
+
c
-
M
u
l
t
E
x
p
G
1
(
a
i
)
H
a
s
h
G
c
+
M
u
l
t
G
2
+
E
x
p
G
3
+
H
a
s
h
G
c
+
M
u
l
t
G
2
+
E
x
p
G
2
+
B
M
G
2
+
H
a
s
h
Z
p
1
+
B
M
G
2
+
H
a
s
h
Z
p
1
+
c
-
M
u
l
t
E
x
p
G
1
(
ν
i
)
c
-
M
u
l
t
E
x
p
G
t
(
l
)
Setup phase
M
u
l
t
G
n
+
H
a
s
h
G
n
+
M
u
l
t
G
n
+
H
a
s
h
G
n
+
M
u
l
t
G
n
+
H
a
s
h
G
n
+
overhead
E
x
p
G
2
n
E
x
p
G
2
n
E
x
p
G
2
nAccording to the theoretical analysis above, our scheme ensures the desired security properties with relatively low performance overhead.


## 7.1. Communication Complexity

We can see from Table3 that the number of bits required of SW-[5] is 2
n
|
p
|
+
2
|
p
| bits. The number of bits required of Wang-[8] is 2
n
|
p
|
+
3
|
p
| bits. The number of bits required of Worku-[9] is 6
|
p
| bits. The EoCo’ the number of bits required is 5
|
p
| bits. From this, we can see that the EoCo has the smallest communication overhead, which can greatly reduce the I/O burden of cloud providers and increase bandwidth utilization.Table 3
Communication complexity comparison.
SW-[5]
Wang-[8]
Worku-[9]
Our scheme
Challenge form and the number of bits required
{
(
i
,
ν
i
)
}
1
≤
i
≤
n
{
(
i
,
ν
i
)
}
1
≤
i
≤
n
(
c
,
k
1
,
k
2
)
(
c
,
k
1
,
k
2
)
2
n
|
p
|bits
2
n
|
p
|bits
3
|
p
|bits
3
|
p
|bits
Response form and the number of bits required
(
σ
,
μ
)
(
σ
,
μ
,
R
)
(
σ
,
μ
,
R
)
(
σ
,
μ
)
2
|
p
|bits
3
|
p
|bits
3
|
p
|bits
2
|
p
|bits
Entire Overhead
O
(
n
)
O
(
n
)
O
(
1
)
O
(
1
)


## 7.2. Computation Complexity

In order to calculate the cost of computing on both sides of the auditor and cloud service provider, we detail the operations on the basic computational symbols in Table4. We can see comparison of several schemes from Table 5 in three aspects.(i)
Server computation overhead: for cloud service providers, we see that the Worku-[9] is obviously less than Wang-[8]. While the EoCo is compared with the Worku-[9], the EoCo adds one more exponential operation, but reduces one hash operation. Generally speaking, one hash is more time-consuming than the exponential operation, so that the EoCo is more efficient on this side.
(ii)
Auditor computation overhead: for the auditor, Wang-[8] and Worku-[9] are only slightly different in efficiency; the latter uses one-time exponential operation less than the former. Although our scheme uses one-time bilinear mapping more than Worku-[9], our scheme uses one-time hash operation, three-time exponential operation and two-time multiplication operation less than Worku-[9]. In this respect, the EoCo has a great promotion.
(iii)
Setup phase overhead: because the schemes are based on BLS short signatures, the computational overhead of the setup phase is equal.Table 4
Notation of cryptographic operations.
Operations
Description
H
a
s
h
Z
p
t
t map-to-Z
p operations
H
a
s
h
G
t
t map-to-G operations
M
u
l
t
G
t
t multiplication in group G
M
u
l
t
Z
p
t
t multiplication in groupZ
p
E
x
p
G
t
t exponentiations in group G
B
M
G
t
t bilinear mappings among elements of G
A
d
d
G
t
t additions on group G
A
d
d
Z
p
t
t additions on groupZ
p
c
-
M
u
l
t
E
x
p
G
t
(
l
)
t c-term exponentiations in group G,l
≤
|
p
|Table 5
Computation comparison.
Our scheme
Wang-[8]
Worku-[9]
Server computation overhead
M
u
l
t
G
c
+
E
x
p
G
2
+
M
u
l
t
G
c
-
1
+
B
M
G
1
+
M
u
l
t
G
c
-
1
+
E
x
p
G
1
+
A
d
d
Z
p
c
+
M
u
l
t
Z
p
c
-
1
+
E
x
p
G
1
+
A
d
d
Z
p
c
+
M
u
l
t
Z
p
c
+
1
+
A
d
d
Z
p
c
+
M
u
l
t
Z
p
c
+
1
+
c
-
M
u
l
t
E
x
p
G
1
(
a
i
)
H
a
s
h
Z
p
1
+
c
-
M
u
l
t
E
x
p
G
1
(
ν
i
)
H
a
s
h
Z
p
1
+
c
-
M
u
l
t
E
x
p
G
1
(
ν
i
)
Auditor computation overhead
H
a
s
h
G
c
+
B
M
G
3
+
c
-
M
u
l
t
E
x
p
G
1
(
a
i
)
H
a
s
h
G
c
+
M
u
l
t
G
2
+
E
x
p
G
3
+
H
a
s
h
G
c
+
M
u
l
t
G
2
+
E
x
p
G
2
+
B
M
G
2
+
H
a
s
h
Z
p
1
+
B
M
G
2
+
H
a
s
h
Z
p
1
+
c
-
M
u
l
t
E
x
p
G
1
(
ν
i
)
c
-
M
u
l
t
E
x
p
G
t
(
l
)
Setup phase
M
u
l
t
G
n
+
H
a
s
h
G
n
+
M
u
l
t
G
n
+
H
a
s
h
G
n
+
M
u
l
t
G
n
+
H
a
s
h
G
n
+
overhead
E
x
p
G
2
n
E
x
p
G
2
n
E
x
p
G
2
nAccording to the theoretical analysis above, our scheme ensures the desired security properties with relatively low performance overhead.


## 8. Conclusion

In this paper, we proposed a secure and effective cloud data integrity verification scheme with privacy protection, EoCo, which is based on the BLS short signature. We presented a more practical data integrity protection model and introduced a ZK-privacy model to ensure the privacy preserving property in public audition. We theoretically analyzed our approach and prove the security of EoCo based on the CDH problem. We also demonstrated that our scheme ensures zero knowledge leakage through indistinguishable views of the attacker. We evaluated the performance of EoCo and made the comparison with related solutions. The analysis results show that our approach has relatively small communication and computational complexity.



---

*Source: 2615249-2018-11-19.xml*