# A Scheme for Verification on Data Integrity in Mobile Multicloud Computing Environment

Authors: Laicheng Cao; Wenwen He; Xian Guo; Tao Feng
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

In order to verify the data integrity in mobile multicloud computing environment, a MMCDIV (mobile multicloud data integrity verification) scheme is proposed. First, the computability and nondegeneracy of verification can be obtained by adopting BLS (Boneh-Lynn-Shacham) short signature scheme. Second, communication overhead is reduced based on HVR (Homomorphic Verifiable Response) with random masking and sMHT (sequence-enforced Merkle hash tree) construction. Finally, considering the resource constraints of mobile devices, data integrity is verified by lightweight computing and low data transmission. The scheme improves shortage that mobile device communication and computing power are limited, it supports dynamic data operation in mobile multicloud environment, and data integrity can be verified without using direct source file block. Experimental results also demonstrate that this scheme can achieve a lower cost of computing and communications.


---

## Body

## 1. Introduction

Cloud computing is envisioned as the future IT service paradigm, it has attracted tremendous attention from academia and industry [1], and mobile cloud model is the future development trend of cloud computing [2, 3]; mobile cloud computing requires cloud data security assurance mechanisms, which can prevent leakage and loss of user data [3, 4]. However, CSP (the cloud service providers) are usually not trustworthy. They may conceal the data loss or error from the users for their own benefit. Even more, they might delete rarely accessed user data for saving storage space [4, 5]. As a result, many users are still hesitant to use cloud storage due to security and confidentiality threats toward their outsourced data.Therefore, how to verify the integrity of customer data under cloud storage environment is a serious problem. To solve this problem, [6] presented a data integrity verification scheme based on the RSA algorithm. This scheme made RSA exponentiation for the entire file, but it has the large computational overhead. Reference [7] proposed a scheme based on labeling, which can verify data integrity but does not support dynamic updates data. Reference [8] used homomorphic verify label scheme though to reduce communication overhead, but it does not support dynamic updates data. Considering the limited computing and storage capacity of mobile devices in mobile cloud computing environment, the complexity of the data integrity verification process on the mobile terminal is inappropriate. Therefore, [9–11] proposed a scheme that is suitable for verification on data integrity in mobile cloud computing environment. But these programs are the circumstances under a single cloud environment.For the general cloud storage case, owning to the security and control reasons, some data cannot be placed in the public cloud. In order to save costs, the user wishes to store the lower security level data on the public cloud; thereby it creates a hybrid cloud model. However, the mobile cloud users also face the issue that not all data can be placed in the public cloud. Therefore, a solution needs to be proposed to reduce the cost of mobile cloud computing and communications, but also to ensure safety and to apply for hybrid cloud environments. Based on these two needs identified above, we propose hybrid data integrity verification scheme for the mobile cloud environment. The scheme supports mobile end users to verify the cloud data integrity and update operations; what is more, it also supports third-party verification without the direct involvement of source file and saved authentication information state. Our scheme is suitable for mobile multicloud computing environments oriented application data.The rest of the paper is organized as follows. Section2 presents architecture and techniques. Section 3 describes the proposed scheme in detail. We also provide security analysis and performance evaluation in Sections 4 and 5. Section 6 concludes the proposed scheme.


## 2. Architecture and Techniques

### 2.1. The Architecture of System

Generally, a mobile multicloud data integrity verification scheme consists of the following components:(i)
Client, the owner of the data, who has a lot of data stored in the hybrid cloud;
(ii)
CSP, multiple cloud storage service providers that supply client with collaborative data storage services (there is an organizer, which manages cloud storage service providers and directly communicates with the verifier).
(iii)
TTP, public information that is stored when a trusted third-party verification is required.The client is installed on a mobile device and user can interact with the CSP, send a request to the CSP, and accept the data which CSP return. CSP consist of the cloud user interaction interface, data validation services (DVS), and user database. DVS performs specific validation algorithm logic. User databases store user information. TTP (trusted third party) is used to verify the integrity of user data and reduce the burden on the client computing. The system components of mobile multicloud data integrity verification (MMCDIV) scheme are shown in Figure 1.Figure 1
MMCDIV scheme system components.


### 2.2. Short Signature Technology Based on Elliptic Curve Bilinear BLS

In our scheme, elliptic curve bilinear pairing BLS (Boneh-Lynn-Shacham) short signature scheme [12] is used as the theoretical basis. BLS short signature scheme is based on bilinear mapping e: G
1
×
G
2
→
G
T. Among them, groups G
1 and G
2 are two Gap Diffie-Hellman (GDH) groups. Mapping e has three properties:(1)
Computability. Mapping e is an efficient algorithm to calculate the bilinear mapping e.
(2)
Bilinear. For any h
1
,
h
2
∈
G, a
,
b
∈
Z
p, Z
p is the nonnegative integers which is less than p and bilinear mapping e is(1)
e
h
1
a
,
h
2
b
=
e
h
1
b
,
h
2
a
=
e
h
1
,
h
2
a
b
.
(3)
Nondegenerative. Consider e
h
1
a
,
h
2
b
≠
1 and g is a generator of group G. When using BLS method, if the user client needs his message signature, he can make x as an any element of the collection of Z
p; then his public key is g
x. To sign the message, client must map his/her own message for an element h of group G and then generates a message signature h
x. Another user wants to verify this message; he needs to check whether e
h
,
g
x
=
e
δ
,
g is established. Only when the left is equal to the right of this formula, this user can verify this message.


### 2.3. Homomorphic Verifiable Response

Reference [13] extended state verification label HVT (Homomorphic Verifiable Tags) to the same state authentication response HVR (Homomorphic Verifiable Response), which can aggregate responses from many different CSP into a response. HVR method can reduce communication overhead but also hide the location information of user data.


### 2.4. Sequence-Enforced Merkle Hash Tree

The sMHT (sequence-enforced Merkle hash tree) [14] is a hash tree structure to solve the problem that the original BLS cannot verify whether the data of the service provider returned is the challenge specified data. This method makes the hash value of the file block labels from left to right in the order correspond to the hash leaves node and then orderly links two-level hash sequence and finally calculates the hash value of the root node. The process of verifying the 2nd data block is the following.To verifyT
2’s value and position, root(R
,
4) and Ω
2
=
{
(
h
1
,
1,1
)
,
(
h
b
,
2,0
)
} are used:(1)
Calculate rank ofA as h
a
=
h
h
T
2
∥
1
∥
h
1
∥
2.
(2)
Calculate rank of root asR
′
=
h
h
a
∥
h
b
∥
4.
(3)
Verify ifR
=
R
′.Note:Ω denotes auxiliary authentication information (AAI), 1 indicates the left sibling node, and  indicates the right one on the proof path. Left signifies all the rank of the left sibling node in Ω. The process of verifying the 2nd data block is shown in Figure 2.Figure 2
The process of verifying the 2nd data block.


## 2.1. The Architecture of System

Generally, a mobile multicloud data integrity verification scheme consists of the following components:(i)
Client, the owner of the data, who has a lot of data stored in the hybrid cloud;
(ii)
CSP, multiple cloud storage service providers that supply client with collaborative data storage services (there is an organizer, which manages cloud storage service providers and directly communicates with the verifier).
(iii)
TTP, public information that is stored when a trusted third-party verification is required.The client is installed on a mobile device and user can interact with the CSP, send a request to the CSP, and accept the data which CSP return. CSP consist of the cloud user interaction interface, data validation services (DVS), and user database. DVS performs specific validation algorithm logic. User databases store user information. TTP (trusted third party) is used to verify the integrity of user data and reduce the burden on the client computing. The system components of mobile multicloud data integrity verification (MMCDIV) scheme are shown in Figure 1.Figure 1
MMCDIV scheme system components.


## 2.2. Short Signature Technology Based on Elliptic Curve Bilinear BLS

In our scheme, elliptic curve bilinear pairing BLS (Boneh-Lynn-Shacham) short signature scheme [12] is used as the theoretical basis. BLS short signature scheme is based on bilinear mapping e: G
1
×
G
2
→
G
T. Among them, groups G
1 and G
2 are two Gap Diffie-Hellman (GDH) groups. Mapping e has three properties:(1)
Computability. Mapping e is an efficient algorithm to calculate the bilinear mapping e.
(2)
Bilinear. For any h
1
,
h
2
∈
G, a
,
b
∈
Z
p, Z
p is the nonnegative integers which is less than p and bilinear mapping e is(1)
e
h
1
a
,
h
2
b
=
e
h
1
b
,
h
2
a
=
e
h
1
,
h
2
a
b
.
(3)
Nondegenerative. Consider e
h
1
a
,
h
2
b
≠
1 and g is a generator of group G. When using BLS method, if the user client needs his message signature, he can make x as an any element of the collection of Z
p; then his public key is g
x. To sign the message, client must map his/her own message for an element h of group G and then generates a message signature h
x. Another user wants to verify this message; he needs to check whether e
h
,
g
x
=
e
δ
,
g is established. Only when the left is equal to the right of this formula, this user can verify this message.


## 2.3. Homomorphic Verifiable Response

Reference [13] extended state verification label HVT (Homomorphic Verifiable Tags) to the same state authentication response HVR (Homomorphic Verifiable Response), which can aggregate responses from many different CSP into a response. HVR method can reduce communication overhead but also hide the location information of user data.


## 2.4. Sequence-Enforced Merkle Hash Tree

The sMHT (sequence-enforced Merkle hash tree) [14] is a hash tree structure to solve the problem that the original BLS cannot verify whether the data of the service provider returned is the challenge specified data. This method makes the hash value of the file block labels from left to right in the order correspond to the hash leaves node and then orderly links two-level hash sequence and finally calculates the hash value of the root node. The process of verifying the 2nd data block is the following.To verifyT
2’s value and position, root(R
,
4) and Ω
2
=
{
(
h
1
,
1,1
)
,
(
h
b
,
2,0
)
} are used:(1)
Calculate rank ofA as h
a
=
h
h
T
2
∥
1
∥
h
1
∥
2.
(2)
Calculate rank of root asR
′
=
h
h
a
∥
h
b
∥
4.
(3)
Verify ifR
=
R
′.Note:Ω denotes auxiliary authentication information (AAI), 1 indicates the left sibling node, and  indicates the right one on the proof path. Left signifies all the rank of the left sibling node in Ω. The process of verifying the 2nd data block is shown in Figure 2.Figure 2
The process of verifying the 2nd data block.


## 3. The Proposed Scheme

In our scheme, we split a file inton blocks; each of block has a sector which is notated as s, so a file F can be expressed as the file with n
×
s section, F
=
m
i
,
j
j
∈
1
,
s
i
∈
1
,
n. We use t to describe the private key of the organizer CSP and use c to express the number of cloud storage files. δ describes the set of tags, δ
=
δ
i
i
∈
1
,
n. Q describes the set of index-coefficient pairs, Q
=
i
,
v
i. ρ describes the response for the challenge Q. C describes the set of CSP to store a file.


### 3.1. Setup Phase

The setup phase of data integrity verification parameter in MMCDIV scheme is shown as follows.Phase 1 (K
e
y
G
e
n
l).
Client takes a security parameterl as input and gets the return value of a public-secret key pair (
spk
,
ssk
) and then selects random β
∈
Z
p, at the same time selects s random elements u
1
,
u
2
,
…
,
u
s
⊂
G
1, calculates u
=
g
β, and finally makes sk
=
β
,
ssk, pk
=
(
u
,
spk
,
g
,
u
j
1
≤
j
≤
s
).Phase 2 (T
a
g
G
e
n
sk
,
F
,
C).
FileF is divided into n
×
s districts by client, F
=
m
i
,
j
j
∈
1
,
s
i
∈
1
,
n, the label of F is t
=
name
∥
n
∥
Sig
ssk
name
∥
n, and calculating file block of the signature is shown as follows:(2)
δ
i
k
=
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
β
1
≤
k
≤
c
,
m
i
∈
C
k
.According to H
m
i constructing sMHT with a root R, client uses the private key β for signature for R: Sig
sk
H
R
=
H
R
β. Finally, he sends m
i
,
δ
i
k
m
i
∈
C
k to each of the CSP, sends Sig
sk
H
R to the organizer, and deletes the local file.


### 3.2. Proof Phase

#### 3.2.1. Constructing Challenges of the Information

Data integrity can be verified by client and also can be verified by TTP for reducing the computation and storage burden of client. Firstly, TTP requires organizers to send the labelt of file to him and then uses public key pk of client to verify t. If this verification is not passed, the file label may be damaged. Otherwise, challenge is executed. TTP randomly selects subset I of set 1
,
n, for each i
∈
I, and selects a random number v
i
∈
Z
p to construct a challenge Q
=
i
,
v
i
i
∈
I, which is sent to a organizer. Lastly, the organizer sends Q
=
i
,
v
i
i
∈
I to each of the CSP.


#### 3.2.2. Performing Gen Proof

EachC
k obtains Q
k
=
i
,
v
i
m
i
∈
C
k
⊆
Q, selects s random elements r
j
,
k
∈
Z
p, j
∈
1
,
s, then calculates π
j
,
k
=
u
j
r
j
,
k, computes corresponding value μ
j
,
k
′
=
∑
‍
v
j
m
i
,
j for each data block, and at the same time calculates(3)
μ
j
,
k
=
μ
j
,
k
′
+
r
j
,
k
h
π
j
,
k
∈
Z
p
,
δ
k
=
∏
i
,
v
i
∈
Q
k
δ
i
k
v
i
,
π
k
=
∏
j
∈
1
,
s
π
j
,
k
h
π
j
,
k
.Then C
k returns ρ
k
=
μ
j
,
k
j
∈
1
,
s
,
δ
k
,
π
k to organizer. After receiving response from each of the CSP, organizer selects a random number γ
∈
Z
p and calculates H
=
v
γ
∈
G
2. Next, organizer aggregates these evidences μ
j
=
γ
∑
C
k
∈
C
‍
μ
j
,
k, δ
=
∏
C
k
∈
C
‍
δ
k
γ, and π
=
∏
C
k
∈
C
‍
π
k. Last, organizer sends C
=
H
m
i
,
Ω
i
i
∈
I
,
Sig
sk
H
R
,
ρ
,
H to TTP.


#### 3.2.3. Executing Algorithms Verify Proof

After receiving authentication informationC, TTP uses H
m
i
,
Ω
i
i
∈
I to reconstruct hash root node R and make the following two verifications:(4)
Verification
1
:
e
Sig
sk
H
R
,
g
=
e
H
R
β
,
g
.Proof.
If validation fails, it returns false. If the validation is successful, it indicates that the root nodeR and the signature Sig
sk
=
H
R are matched under the premise of root node Sig
sk
=
H
R given CSP. It can also show that the label of file block H
m
i
i
∈
I is intact and proceed to the next verification:(5)
Verification
2
:
e
δ
,
g
=
e
π
-
1
·
∏
i
∈
I
H
m
i
v
i
,
H
e
∏
j
=
1
s
u
j
μ
j
,
v
.Proof.
We just prove that left is equal to right (as shown in (6)): (6)
Left
=
e
∏
C
k
∈
C
∏
i
,
v
i
∈
Q
k
δ
i
k
v
i
γ
,
g
=
e
∏
C
k
∈
C
∏
i
,
v
i
∈
Q
k
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
β
v
i
γ
,
g
=
e
∏
i
∈
I
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
γ
v
i
,
g
β
=
e
∏
i
∈
I
H
m
i
γ
v
i
,
v
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
v
j
m
i
,
j
,
v
Right
=
e
∏
C
k
∈
C
π
k
-
1
·
∏
i
∈
I
T
i
v
i
,
v
γ
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
μ
j
,
k
,
v
=
e
∏
i
∈
I
H
m
i
γ
v
i
,
v
·
e
∏
C
k
∈
C
∏
j
=
1
s
π
j
,
k
-
h
π
j
,
k
,
v
·
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
v
j
m
i
,
j
·
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
γ
j
,
k
h
π
j
,
k
,
v
=
e
∏
i
∈
I
H
m
i
γ
v
i
,
v
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
v
j
m
i
,
j
,
v
Thus,  Left
=
Right
.
If the validation fails, it shows that documentation block is corrupt. It returns false. On the other hand, it shows that documentation block is complete.


### 3.3. Implementation of Dynamic Operation

(i) Constructing Updates Information. The i block data m
i is updated to m
i
∗
m
∗
1
,
m
∗
2
,
…
,
m
∗
s by client; the steps of constructing updates information are shown as follows.Step 1.
Client calculatesH
m
i
∗ (the hash value of m
i
∗) and computes δ
i
∗
k (label of m
i
∗).Step 2.
Client constructs update information (update =(
M
,
I
,
H
(
m
i
∗
)
)) and sends it to organizers.Step 3.
Client sendsM
,
I
,
m
i
∗
,
δ
i
∗
k to the corresponding CSP.(ii) Executing Update. After the updates information is constructed, client will execute update data; the process is described as follows.Step 1.
CSP replace blocksm
i
∗ and δ
i
∗, update the hash tree, generate a new node R
′ and updated authentication information C
update
=
Ω
i
,
H
m
i
,
Sig
sk
H
R
,
H
R
′, and then send it to the TTP.Step 2.
TTP usesΩ
i
,
H
m
i to reconstruct the root node R and verifies e
Sig
sk
H
R
,
g
=
e
H
R
,
v. If verification is passed, client continues to check whether CSP execute update data option and then uses Ω
i
,
H
m
i
∗ to structure updated value. Client sends m
i
∗ to TTP and compares m
i
∗ with R
′. If it is consistent, it shows that client completes the update operation.Step 3.
Client uses his private keysk to calculate the label (Sig
sk
H
R
′) of root node R
′ and then sends it to the CSP.Step 4.
CSP perform the insert operation. CSP first input the location of original file and the original file block label and requestF
,
δ
,
C
insert that client sends, and then produce outputs F
′
,
δ
′
,
C
insert.Step 5.
CSP perform the removal operation. CSP first input the deleted requestC
delete information which client sends and then produce outputs C
delete operations information.


## 3.1. Setup Phase

The setup phase of data integrity verification parameter in MMCDIV scheme is shown as follows.Phase 1 (K
e
y
G
e
n
l).
Client takes a security parameterl as input and gets the return value of a public-secret key pair (
spk
,
ssk
) and then selects random β
∈
Z
p, at the same time selects s random elements u
1
,
u
2
,
…
,
u
s
⊂
G
1, calculates u
=
g
β, and finally makes sk
=
β
,
ssk, pk
=
(
u
,
spk
,
g
,
u
j
1
≤
j
≤
s
).Phase 2 (T
a
g
G
e
n
sk
,
F
,
C).
FileF is divided into n
×
s districts by client, F
=
m
i
,
j
j
∈
1
,
s
i
∈
1
,
n, the label of F is t
=
name
∥
n
∥
Sig
ssk
name
∥
n, and calculating file block of the signature is shown as follows:(2)
δ
i
k
=
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
β
1
≤
k
≤
c
,
m
i
∈
C
k
.According to H
m
i constructing sMHT with a root R, client uses the private key β for signature for R: Sig
sk
H
R
=
H
R
β. Finally, he sends m
i
,
δ
i
k
m
i
∈
C
k to each of the CSP, sends Sig
sk
H
R to the organizer, and deletes the local file.


## 3.2. Proof Phase

### 3.2.1. Constructing Challenges of the Information

Data integrity can be verified by client and also can be verified by TTP for reducing the computation and storage burden of client. Firstly, TTP requires organizers to send the labelt of file to him and then uses public key pk of client to verify t. If this verification is not passed, the file label may be damaged. Otherwise, challenge is executed. TTP randomly selects subset I of set 1
,
n, for each i
∈
I, and selects a random number v
i
∈
Z
p to construct a challenge Q
=
i
,
v
i
i
∈
I, which is sent to a organizer. Lastly, the organizer sends Q
=
i
,
v
i
i
∈
I to each of the CSP.


### 3.2.2. Performing Gen Proof

EachC
k obtains Q
k
=
i
,
v
i
m
i
∈
C
k
⊆
Q, selects s random elements r
j
,
k
∈
Z
p, j
∈
1
,
s, then calculates π
j
,
k
=
u
j
r
j
,
k, computes corresponding value μ
j
,
k
′
=
∑
‍
v
j
m
i
,
j for each data block, and at the same time calculates(3)
μ
j
,
k
=
μ
j
,
k
′
+
r
j
,
k
h
π
j
,
k
∈
Z
p
,
δ
k
=
∏
i
,
v
i
∈
Q
k
δ
i
k
v
i
,
π
k
=
∏
j
∈
1
,
s
π
j
,
k
h
π
j
,
k
.Then C
k returns ρ
k
=
μ
j
,
k
j
∈
1
,
s
,
δ
k
,
π
k to organizer. After receiving response from each of the CSP, organizer selects a random number γ
∈
Z
p and calculates H
=
v
γ
∈
G
2. Next, organizer aggregates these evidences μ
j
=
γ
∑
C
k
∈
C
‍
μ
j
,
k, δ
=
∏
C
k
∈
C
‍
δ
k
γ, and π
=
∏
C
k
∈
C
‍
π
k. Last, organizer sends C
=
H
m
i
,
Ω
i
i
∈
I
,
Sig
sk
H
R
,
ρ
,
H to TTP.


### 3.2.3. Executing Algorithms Verify Proof

After receiving authentication informationC, TTP uses H
m
i
,
Ω
i
i
∈
I to reconstruct hash root node R and make the following two verifications:(4)
Verification
1
:
e
Sig
sk
H
R
,
g
=
e
H
R
β
,
g
.Proof.
If validation fails, it returns false. If the validation is successful, it indicates that the root nodeR and the signature Sig
sk
=
H
R are matched under the premise of root node Sig
sk
=
H
R given CSP. It can also show that the label of file block H
m
i
i
∈
I is intact and proceed to the next verification:(5)
Verification
2
:
e
δ
,
g
=
e
π
-
1
·
∏
i
∈
I
H
m
i
v
i
,
H
e
∏
j
=
1
s
u
j
μ
j
,
v
.Proof.
We just prove that left is equal to right (as shown in (6)): (6)
Left
=
e
∏
C
k
∈
C
∏
i
,
v
i
∈
Q
k
δ
i
k
v
i
γ
,
g
=
e
∏
C
k
∈
C
∏
i
,
v
i
∈
Q
k
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
β
v
i
γ
,
g
=
e
∏
i
∈
I
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
γ
v
i
,
g
β
=
e
∏
i
∈
I
H
m
i
γ
v
i
,
v
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
v
j
m
i
,
j
,
v
Right
=
e
∏
C
k
∈
C
π
k
-
1
·
∏
i
∈
I
T
i
v
i
,
v
γ
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
μ
j
,
k
,
v
=
e
∏
i
∈
I
H
m
i
γ
v
i
,
v
·
e
∏
C
k
∈
C
∏
j
=
1
s
π
j
,
k
-
h
π
j
,
k
,
v
·
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
v
j
m
i
,
j
·
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
γ
j
,
k
h
π
j
,
k
,
v
=
e
∏
i
∈
I
H
m
i
γ
v
i
,
v
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
v
j
m
i
,
j
,
v
Thus,  Left
=
Right
.
If the validation fails, it shows that documentation block is corrupt. It returns false. On the other hand, it shows that documentation block is complete.


## 3.2.1. Constructing Challenges of the Information

Data integrity can be verified by client and also can be verified by TTP for reducing the computation and storage burden of client. Firstly, TTP requires organizers to send the labelt of file to him and then uses public key pk of client to verify t. If this verification is not passed, the file label may be damaged. Otherwise, challenge is executed. TTP randomly selects subset I of set 1
,
n, for each i
∈
I, and selects a random number v
i
∈
Z
p to construct a challenge Q
=
i
,
v
i
i
∈
I, which is sent to a organizer. Lastly, the organizer sends Q
=
i
,
v
i
i
∈
I to each of the CSP.


## 3.2.2. Performing Gen Proof

EachC
k obtains Q
k
=
i
,
v
i
m
i
∈
C
k
⊆
Q, selects s random elements r
j
,
k
∈
Z
p, j
∈
1
,
s, then calculates π
j
,
k
=
u
j
r
j
,
k, computes corresponding value μ
j
,
k
′
=
∑
‍
v
j
m
i
,
j for each data block, and at the same time calculates(3)
μ
j
,
k
=
μ
j
,
k
′
+
r
j
,
k
h
π
j
,
k
∈
Z
p
,
δ
k
=
∏
i
,
v
i
∈
Q
k
δ
i
k
v
i
,
π
k
=
∏
j
∈
1
,
s
π
j
,
k
h
π
j
,
k
.Then C
k returns ρ
k
=
μ
j
,
k
j
∈
1
,
s
,
δ
k
,
π
k to organizer. After receiving response from each of the CSP, organizer selects a random number γ
∈
Z
p and calculates H
=
v
γ
∈
G
2. Next, organizer aggregates these evidences μ
j
=
γ
∑
C
k
∈
C
‍
μ
j
,
k, δ
=
∏
C
k
∈
C
‍
δ
k
γ, and π
=
∏
C
k
∈
C
‍
π
k. Last, organizer sends C
=
H
m
i
,
Ω
i
i
∈
I
,
Sig
sk
H
R
,
ρ
,
H to TTP.


## 3.2.3. Executing Algorithms Verify Proof

After receiving authentication informationC, TTP uses H
m
i
,
Ω
i
i
∈
I to reconstruct hash root node R and make the following two verifications:(4)
Verification
1
:
e
Sig
sk
H
R
,
g
=
e
H
R
β
,
g
.Proof.
If validation fails, it returns false. If the validation is successful, it indicates that the root nodeR and the signature Sig
sk
=
H
R are matched under the premise of root node Sig
sk
=
H
R given CSP. It can also show that the label of file block H
m
i
i
∈
I is intact and proceed to the next verification:(5)
Verification
2
:
e
δ
,
g
=
e
π
-
1
·
∏
i
∈
I
H
m
i
v
i
,
H
e
∏
j
=
1
s
u
j
μ
j
,
v
.Proof.
We just prove that left is equal to right (as shown in (6)): (6)
Left
=
e
∏
C
k
∈
C
∏
i
,
v
i
∈
Q
k
δ
i
k
v
i
γ
,
g
=
e
∏
C
k
∈
C
∏
i
,
v
i
∈
Q
k
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
β
v
i
γ
,
g
=
e
∏
i
∈
I
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
γ
v
i
,
g
β
=
e
∏
i
∈
I
H
m
i
γ
v
i
,
v
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
v
j
m
i
,
j
,
v
Right
=
e
∏
C
k
∈
C
π
k
-
1
·
∏
i
∈
I
T
i
v
i
,
v
γ
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
μ
j
,
k
,
v
=
e
∏
i
∈
I
H
m
i
γ
v
i
,
v
·
e
∏
C
k
∈
C
∏
j
=
1
s
π
j
,
k
-
h
π
j
,
k
,
v
·
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
v
j
m
i
,
j
·
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
γ
j
,
k
h
π
j
,
k
,
v
=
e
∏
i
∈
I
H
m
i
γ
v
i
,
v
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
v
j
m
i
,
j
,
v
Thus,  Left
=
Right
.
If the validation fails, it shows that documentation block is corrupt. It returns false. On the other hand, it shows that documentation block is complete.


## 3.3. Implementation of Dynamic Operation

(i) Constructing Updates Information. The i block data m
i is updated to m
i
∗
m
∗
1
,
m
∗
2
,
…
,
m
∗
s by client; the steps of constructing updates information are shown as follows.Step 1.
Client calculatesH
m
i
∗ (the hash value of m
i
∗) and computes δ
i
∗
k (label of m
i
∗).Step 2.
Client constructs update information (update =(
M
,
I
,
H
(
m
i
∗
)
)) and sends it to organizers.Step 3.
Client sendsM
,
I
,
m
i
∗
,
δ
i
∗
k to the corresponding CSP.(ii) Executing Update. After the updates information is constructed, client will execute update data; the process is described as follows.Step 1.
CSP replace blocksm
i
∗ and δ
i
∗, update the hash tree, generate a new node R
′ and updated authentication information C
update
=
Ω
i
,
H
m
i
,
Sig
sk
H
R
,
H
R
′, and then send it to the TTP.Step 2.
TTP usesΩ
i
,
H
m
i to reconstruct the root node R and verifies e
Sig
sk
H
R
,
g
=
e
H
R
,
v. If verification is passed, client continues to check whether CSP execute update data option and then uses Ω
i
,
H
m
i
∗ to structure updated value. Client sends m
i
∗ to TTP and compares m
i
∗ with R
′. If it is consistent, it shows that client completes the update operation.Step 3.
Client uses his private keysk to calculate the label (Sig
sk
H
R
′) of root node R
′ and then sends it to the CSP.Step 4.
CSP perform the insert operation. CSP first input the location of original file and the original file block label and requestF
,
δ
,
C
insert that client sends, and then produce outputs F
′
,
δ
′
,
C
insert.Step 5.
CSP perform the removal operation. CSP first input the deleted requestC
delete information which client sends and then produce outputs C
delete operations information.


## 4. Security Analysis

This MMCDIV scheme is based on the absence of an effective security algorithm; it can solve elliptic curve discrete logarithm problem and characteristics of GDH (Gap Diffie-Hellman).(1) Resisting Forgery Attack. Suppose the CSP to forge δ
csp select the same s random elements u
1
,
u
2
,
…
,
u
s
⊂
G
1 and a random number γ
∈
Z
p; they can calculate (7) in accordance with (5) and (6):(7)
Left
csp
=
e
δ
csp
,
g
=
e
∏
C
k
∈
C
∏
i
,
v
i
∈
Q
k
δ
i
,
csp
k
v
i
γ
,
g
=
e
∏
C
k
∈
C
∏
i
,
v
i
∈
Q
k
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
β
csp
v
i
γ
,
g
=
e
∏
i
∈
I
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
γ
v
i
,
g
β
csp
Right
csp
=
e
∏
i
∈
I
H
m
i
γ
v
i
,
v
·
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
v
j
m
i
,
j
,
v
.Equation (8) is obtained by (6) as follows:(8)
Left
=
e
∏
i
∈
I
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
γ
v
i
,
g
β
=
e
∏
i
∈
I
H
m
i
γ
v
i
,
v
·
e
∏
j
=
1
s
u
j
γ
∑
C
k
∈
C
v
j
m
i
,
j
,
v
=
Right
.Because the right of (8) is equal to the right (Righ
t
csp) of (7), the forgery attack is going to be carried out; only (9) is established:(9)
e
∏
i
∈
I
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
γ
v
i
,
g
β
csp
=
e
∏
i
∈
I
H
m
i
·
∏
j
=
1
s
u
j
m
i
,
j
γ
v
i
,
g
β
.So (10) is obtained by (9):(10)
g
β
csp
=
g
β
.The prerequisite of (10) establishment is β
csp
=
β; because of the hardness problem of GDH, the CSP cannot calculate the private key β of the client, so they cannot carry out the forgery attack.(2) Resisting Replacing Attack. According to (2), we suppose MAC
=
H
(
m
i
)
(
1
≤
k
≤
c
,
m
i
∈
C
k
), where the MAC is message authentication code, and the MAC of MD
5 (Message Digest Algorithm v5) is 128 bit; namely, MAC
=
128 and the CSP replace m
i as m
i
′.Because the hash function has WCR (Weak Collision Resistance) and SCR (Strong Collision Resistance), thus(11)
Pr
⁡
H
m
i
′
=
H
m
i
=
2
-
MAC
=
2
-
128
Pr
⁡
H
f
m
i
′
=
H
m
i
=
2
-
MAC
=
2
-
128
1
≤
k
≤
c
,
m
i
∈
C
k
,where Pr
⁡
[
x
] is the probability of x and f
(
x
) is a transformation of x.Equation (11) shows the probability of the CSP replacing m
i as m
i
′ is very small, so it is almost impossible that the CSP carry out replacing attack.


## 5. Performance Evaluation

In order to solve the problem that the original BLS cannot verify whether the data of the service provider returned is the challenge specified data, MMCDIV scheme adopts the sMHT; meanwhile, the computability and nondegeneracy of verification are obtained by using BLS short signature scheme.In integrity verification stage,e
Sig
sk
H
R
,
g
=
e
H
R
,
v is verified to determine whether CSP returns the original authentication information by comparing the root node R with R
′ which is stored in TTP. Our scheme does not directly use the BLS procedure to calculate δ
i
k but uses H
m
i
·
∏
j
=
1
s
‍
u
j
m
i
,
j
β to calculate δ
i
k. This is done, because the CSP may delete user data, leaving only H
m
i; they are not related when client verifies file blocks, so in case of the label intact, verification can still be carried out. But the actual data blocks may be deleted, so the file blocks must be generated as parameters into the calculation of the signature file blocks. In addition, MMCDIV supports outsourcing verification; client and TTP do not verify any results returned but can directly use, even if TTP and CSP deceit together client, user data and private information will not be leaked to the TTP; therefore e
Sig
sk
H
R
,
g
=
e
H
R
,
v and e
δ
,
g
=
e
π
-
1
·
∏
i
∈
I
‍
H
m
i
v
i
,
H
e
∏
j
=
1
s
‍
u
j
μ
j
,
v are the guarantee of the TTP’s reliability in our MMCDIV scheme.In client end, client needs to establish complete hash tree operations, signature for nonleaf nodes, and the root filling and usesn to describe unfilled leaf node (the number of uploaded file blocks). When constructing hash tree, (
2
n
-
1
) times operations need to calculate the hash value. The signature number is (
n
+
1
), so total time is T
total
=
2
n
-
1
·
T
hash
+
n
+
1
T
tag. For CSP, in GenProof stage, when traversing a hash tree, it needs to calculate T
μ and T
δ. So total time is T
total
=
c
2
L
+
1
-
1
·
T
hash
+
T
δ
+
T
μ and c is the number of AAI nodes and L represents the average height of the c node. Client (or TTP) requires reconstructing root and completing two verifications in verifying proof stage, so total time AAI is T
total
=
AAI
num
·
2
L
-
L
′
+
1
-
1
+
c
′
2
L
′
+
1
-
1
T
hash
+
T
test
1
+
T
test
2, num is the number of nodes AAI, L is the hash tree height, and L
′ represents the average height of the node where AAI is located. C
′ is the number of sibling nodes in the same subtree when challenge appears. Figures 3 and 4 denote the increase trends of server-side program (Intel Core i5 2.5 GHz, 8 G memory, Windows 7 operating system) and the client (armeabi-v7a, Android 2.3.3 system) with the actual running time file size which is 1024 bytes. As shown, when file size is 2 kb, 4 kb, 5 kb, 10 kb, 20 kb, 30 kb, 40 kb, and 50 kb, the constructing authentication information time (CAI-Time) steadily rises with rapid increase of the uploading and processing time (UP-Time), comparing Sheng [9] and Yan scheme [10]; the time complexity of MMCDIV scheme is much lower. In this process, the CAI-Time in client is much lesser than the UP-Time.Figure 3
Runtime of server.Figure 4
Runtime of client.


## 6. Conclusion

We use BLS short signature algorithm, homomorphic response technology, and sMHT to propose a MMCDIV scheme for verification on data integrity in mobile multicloud computing environment. The scheme improves shortage that mobile device communication and computing power are weak. Experimental results also demonstrate that this scheme can achieve a lower cost of computing and communications. At the same time, it also has the following advantages:(
1
) it supports third-party verification and reduces the computational burden of storage mobile terminal; (
2
) it is suitable for hybrid cloud environments; (
3
) it can be applied to verification without source files; no authentication information saved state; (
4
) it supports dynamic data update operations.



---

*Source: 9267608-2016-08-21.xml*