An Improved Privacy Preserving Construction for Data Integrity Verification in Cloud Storage

KSII Transactions on Internet and Information Systems (TIIS).
2014.
Oct,
8(10):
3607-3623

- Received : March 25, 2014
- Accepted : September 10, 2014
- Published : October 28, 2014

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

The increasing demand in promoting cloud computing in either business or other areas requires more security of a cloud storage system. Traditional cloud storage systems fail to protect data integrity information (DII), when the interactive messages between the client and the data storage server are sniffed. To protect DII and support public verifiability, we propose a data integrity verification scheme by deploying a designated confirmer signature DCS as a building block. The DCS scheme strikes the balance between public verifiable signatures and zero-knowledge proofs which can address disputes between the cloud storage server and any user, whoever acting as a malicious player during the two-round verification. In addition, our verification scheme remains blockless and stateless, which is important in conducting a secure and efficient cryptosystem. We perform security analysis and performance evaluation on our scheme, and compared with the existing schemes, the results show that our scheme is more secure and efficient.
“my file has been tampered!”
although he received a true proof which implies the correctness of the data integrity; Similarly, a dishonest cloud storage server can claim
“your file has never been modified!”
after he tampered the data or the data had unexpectedly been lost, while the user examined the
false
proof. Consequently, the new research problem is, how to design a secure and efficient data integrity verification system for cloud storage with the following two requirements:
(1) It has a flexible protection mechanism towards any user’s data integrity information. The DII should be indecipherable without the user’s private information, and only the user can see the fact of the DII in general cases.
(2) It supports public verifiability. In some special cases, it allows a TPA, not just the user (data owner), to challenge the cloud server for correctness of data storage. Storage server or a malicious user that disavows the fact of the DII. The TPA may further reveal the fact of the DII by issuing a piece of publicly verifiable information that can be checked by anyone.
In order to solve this problem, we introduce designated confirmer signatures (DCS) to replace the original ordinary signatures in the cloud storage architecture. The concept of DCS was initially proposed by Chaum and van Antwerpen
[21]
. In a DCS scheme, both the signer and a semi-trusted third party called the designated confirmer can confirm the validity of a signature by running some interactive protocols with a verifier. However, such a verifier cannot further convince other parties of the signature’s validity. In addition, the confirmer can selectively convert a designated confirmer signature into an ordinary signature so that it is publicly verifiable. With those special properties of a DCS scheme, we present a secure data integrity verification model which avoids the risk of DII leakage and enables public verifiability. A similar cryptographic primitive called “designated verifier signature” (DVS) can also protect the DII. Since the non-repudiation property is reduced in a DVS scheme where a signer convinces the designated verifier that the message the signer signed is authentic. However, neither the signer nor the designated verifier can convince any other party of the authenticity of that message. Therefore, DVS schemes cannot be used as a building block as it is incompatible with public verifiability in a cloud storage system.
an undeniable proof
. This undeniable proof will reveal the final result and can be checked by other users. Note such a final proof should satisfy these conditions: 1) the proof should be publicly verifiable; 2) the proof must show that the data have not been tampered indeed if a malicious user announces that his stored data files have been modified; 3) the proof must show that the data have been tampered if dishonest CSS denies occur.
Fig. 1
shows the high-level architecture of a data integrity verification system for cloud storage.
an architecture of a data integrity verification system
Comparing with previous architectures
[3
,
5]
in cloud storage, we emphasize that the TPA in our model plays a different role, which can be regarded as a judge to mediate disputes between CSS and a user. In fact, any other user except the data owner in the cloud, upon receiving the proof, can verify the proof and know the DII.
“UndeniableProof”
and
“TPAVerifyProof”
, which are both run by TPA. The
“Undeniable”
algorithm aims to resolve the dispute between the user and CSS, while the second algorithm serves as
“Verify Proof”
to check the correctness of a data integrity proof except that the secret input is TPA’s private key.
Definition 1 (Syntax).
A data integrity verification system involves three roles of parties, i.e., a user
U
, a third party auditor TPA, and a cloud storage server
CSS
consists of the following algorithms:
KeyGen
(1
^{k}
) → (
pk,sk
). This probabilistic algorithm is run by either the user or TPA. It takes the security parameter 1
^{k}
as input, and outputs a public key
pk
and a private key
sk
.
SigGen
(
sk_{U},F
) → (Փ,
sig
(
R
)). This probabilistic algorithm is run by the user. It takes the user’s private key
sk_{U}
, and an encoded file
F
which is an ordered collection of file blocks {
m_{i}
} as input, and outputs the signature set Փ, which is a set of signatures of challenging blocks {
σ_{i}
}. It also outputs a metadata signature
sig
(
R
) of the metadata
R
of the encoded file. Note the semantic feature of
R
could be either the file size or other easy-to-store metadata held by the user.
Gen
Pr
oof
(
F
,Փ,
chal
) →
P
. This algorithm is run by the server. It takes the user’s challenging message
chal
, an encoded file
F
, and the signature set Փ as input. It outputs a data integrity proof
P
with respect to the blocks specified by
chal
.
Verify
Pr
oof
(
chal, P, sk_{U}
) → {
TRUE ,FALSE
}. This algorithm is run by the user. It takes the user’s private key
sk_{U}
, a challenging message
chal
, and a data integrity proof
P
as input. It returns
TRUE
if the integrity of the file is verified to be correct, otherwise it returns
FALSE
.
Undeinable
Pr
oof
(
chal, P, sk_{TPA}
) →
π
. This algorithm is run by TPA. It takes TPA’s private key TPA
sk_{TPA}
, a challenging message
chal
, and a data integrity proof
P
as input. It returns a non-interactive proof
π
which reveals the correctness of
P
.
TPAVerify
Pr
oof
(
chal, P, sk_{TPA}
) → {
TRUE ,FALSE
}. This algorithm is run by the TPA. It takes TPA’s private key
sk_{TPA}
, a challenging message
chal
, and a data integrity proof
P
as input. It returns
TRUE
if the integrity of the file is verified to be correct, otherwise it returns
FALSE
. Note this algorithm can be viewed as a prepositive algorithm of
UndeniableProof
, which is usually invoked before the latter generating a final public evidence.
(Correctness)
We say a data integrity verification protocol is correct, if for all key pairs output by
KenGen
, for all files
F
= (
m_{0}
,...,
m_{i}
) where
for all challenge message
“chal”
generated by the user, and for any proof
P
output by an honest prover via
GenProof
, the verification algorithm always accepts:
(Soundness)
A data integrity verification protocol is sound if any cheating prover can convince the verification algorithm that it is storing a file is actually storing that file. It means that the cheating prover yields up the file to an extractor algorithm that interacts with it using the data integrity verification protocol. Note the formal definition of the soundness of a proof-of-retrievability protocol is presented in
[2]
.
Bilinear Maps
a lot of research works
[22
,
23
,
24
,
25]
have been put in elliptic curve cryptography (ECC) and many cryptosystems
[26
,
27
,
28]
have been proposed. Pairings were initially used for attacking the existing cryptosystems. In this context, pairings are cryptanalysis tools which regarded as a function that takes two points on an elliptic curve as input, and outputs an element of some multiplicative group.
Definition 2 (Bilinear Map).
Suppose that
G
and
G_{t}
be two multiplicative cyclic groups with the same prime order
q
, while
g
is a generator of
G
. A bilinear pairing on (
G
,
G_{t}
) is a bilinear map
e : G × G → G_{t}
, which satisfies the following properties:
Merkle Tree
We use a Merkle Tree to maintain all the stored data file. As a well studied authentication structure, a merkle tree intends to prove that a set of elements are undamaged and unaltered efficiently and securely. It is constructed as a binary tree where the leaves are the hashes of authentic data values. In this paper we further employ such a data structure to authenticate both the values and the positions of data blocks. We treat the leaf nodes as the left-to-right sequence, so any leaf node can be uniquely determined by following this sequence and the way of computing the root node in the Merkle Tree.
m
by using his private key, and then encrypts that signature under the confirmer’s public key. Such a ciphertext is usually regarded as a DCS signed on
m
. To verify such a DCS, the signer usually provides some proof show that “the ciphertext is an encryption of his signature under someone’s public key”. Also the confirmer with its private key can decrypt such a ciphertext, and verify the internal signature.
We propose a new construction based on BLS signatures
[30]
and ElGamal encryption schemes
[31]
. In fact, a single DCS in our data integrity verification system is computed by hiding a basic signature with ElGamal encryptions. We use the same construction as in
[3]
to compute the underlying basic signatures, which are homomorphic authenticators pre-computed by the user, and stored in CSS. To issuing a proof, CSS encrypts those BLS signatures with TPA’s public key to generate intermediate DCSs. The responding proof contains aggregated signatures which linearly combines those DCSs of challenging message blocks. Such a proof can only be checked by a verifier with its private key, i.e., either the user or the TPA.
To reduce the complexity of data management, we adopt the same techniques, i.e., a Merkle Tree, as in
[3
,
5]
to maintain the authentication structure.
into
F
, as in Wang et al.’s scheme
[3]
, by using Reed-Solomon codes, and divides
F
into
n
blocks:
m
_{1}
,
m
_{2}
,...,
m_{n}
, where
Let
e : G × G → G_{t}
be a bilinear map where
g
is a generator of
G
.
H
: {0,1}
^{*}
→
G
is a full-domain hash function. The procedure of our protocol executions are illustrated as follows.
Setup:
Initially,
KeyGen
is invoked to generate the entities’ public and private keys. By running
SigGen
, the homomorphic authenticators and the metadata are pre-processed.
KeyGen
(1
^{k}
) : The user
U
chooses a random value
and a random element
u
∈
_{R} G
, computes
The private key of
U
is
x_{U}
, and the public key of
U
is
(y_{U}, u )
. Similarly, the third party auditor TPA sets its private/public key pair as(
x_{TPA}, y_{TPA} = g^{xTPA}
), where
SigGen
(
sk_{U},F
) : On the encoded file
F
= (
m
_{1}
,
m
_{2}
, ...,
m_{n}
), the user
U
generates the authenticators for each blocks by computing
n
signatures as
σ_{i}
= (
H
(
m_{i}
) ·
u^{mi}
)
^{xu}
. Let Փ = {
σ_{i}
},1 ≤
i
≤
n
denote the set of signatures. Then
U
generates a root R based on the construction of a Merkle Tree, where the leave nodes represents an ordered set of hashes of “file tags”, i.e.
H
(
m_{i}
),1 ≤
i
≤
n
.
U
signs the root
R
with its private key
x_{U}
as a BLS signature
[30]
:
σ_{R}
=
H
(
R
)
^{xU}
. Eventually,
U
sends {
F
, Փ,
σ_{R}
} to the storage server
CSS
, and also deletes all values from its local storage.
Default Integrity Verification:
The user
U
can check the integrity of the outsourced data
m
by challenging the storage server
CSS
. To generate the challenging message,
U
chooses a random subset
I
= (
s
_{1}
,...,
s_{c}
), where
s_{i}
denotes the index of the message block
m_{i}
, and we assume
s
_{1}
≤
i
≤
s_{c}
. For each
s_{i}
∈
I, U
picks a random value
Eventually, U sends the challenging message
chal
= {(
s_{i}, r_{i}
)}
_{s1 ≤ i ≤ sc}
to
CSS
.
Gen
Pr
oof
(
F
, Փ,
chal
): To generate an integrity proof, CSS computes an aggregated DCS for the challenging blocks. Specifically, on receiving the challenge request
chal
= {(
s_{i}, r_{i}
)}
CSS
computes
In addition,
CSS
also provides the verifier (
U
) with a small amount of auxiliary information {Ω
_{i}
},
s
_{1}
≤
i
≤
s_{c}
, which denotes the sibling nodes on the path from the leaves
H
(
m_{i}
),
s
_{i}
≤
i
≤
s_{c}
to the root
R
in the Merkle Tree. Next,
CSS
responds
U
with proof
P
, including the
DCS
(
ς, μ
) and
θ
, the challenged leaves {
H
(
m_{i}
)}, and the auxiliary information {Ω
_{i}
}. We have
P
= {(
ς, μ, θ
), {
H
(
m_{i}
)}, {Ω
_{i}
},
σ_{R}
}, where
s
_{1}
≤
i
≤
s_{c}
.
Verify
Pr
oof
(
chal, P, sk_{U}
) : On receiving the responses from the prover
CSS
, the verifier
U
first generates the root
R
by using {
H
(
m_{i}
)} and {Ω
_{i}
}, where
s
_{1}
≤
i
≤
s_{c}
, and authenticates it by checking if the equation
e
(
σ_{R}, g
) ≡
e
(
H
(
R
),
y_{U}
) holds. If such a check fails,
U
rejects the proof with an output
“FALSE”
. Otherwise,
U
checks the following Equ.2.
If so,
U
outputs
“TRUE”
; otherwise,
U
outputs
“FALSE”
.
Undeniable Integrity Verification:
In case of the occurrence of a dispute occurs, that is the cloud storage server
CSS
denies a
false
proof
P
after
U
executing
with
“FALSE”
as output. The third party auditor TPA can verify the proof
P
and outputs an undeniable proof to reveal the fact that data were tampered.
On receiving the proof information from either
CSS
or the user, the TPA first generates the root
R
by using {
H
(
m_{i}
)} and {Ω
_{i}
}, where
s
_{1}
≤
i
≤
s_{c}
, and authenticates it by checking if the equation
e
(
σ_{R}, g
) ≡
e
(
H
(
R
),
y_{U}
) holds. If such a check fails,
U
rejects the proof with an output
“FALSE- 0”
. Otherwise,
U
checks the following Equ.3.
If Equ.3 holds, U outputs “TRUE”; otherwise, U outputs “FALSE -1”.
Undeinable
Pr
oof
(
chal, P, sk_{TPA}
) : At the beginning, TPA invokes the algorithm
TPAVerifyProof
.
Once a string
“FALSE- 0”
is output, TPA reveals part of the proof information, that is, {{
H
(
m_{i}
), {Ω
_{i}
},
σ_{R}
}
_{s1 ≤ i ≤ sc}
, so that anyone else can verify it.
Once a string
“TRUE”
is output, TPA can issue a non-interactive zero knowledge proof (NIZK)
π
_{1}
to show the correctness of the data storage. And such a NIZK actually proves the validity of the DCS(
ς, μ, θ
), and is publicly verifiable. Let
W
_{1}
=
e
(
μ, y_{TPA}
) /
e
(
ς, g
),
a NIZK
π
_{1}
is transformed from the zero knowledge proof of knowledge
In particular, we uses the techniques in
[32]
to generate
π
_{1}
from
TPA picks a random value
computes
and
s = v + cx_{TPA}
, where
is a secure cryptographic hash function. TPA issues a NIZK
π
_{1}
= (
W
_{1}
,
W
_{2}
,
s, c
). To verify such a NIZK proof, anyone with the inputs
π
_{1}
= (
W
_{1}
,
W
_{2}
,
s, c
), first computes
Then he computes
he accepts such a NIZK that shows the equality of two discrete logarithms, which further implies the validity of the
DCS
(
ς ,μ
).
Once a string “FALSE- 1” is output, TPA can issue a NIZK proof
π
_{2}
to show the incorrectness of the data storage. And such a NIZK actually proves the invalidity of the
DCS
(
ς ,μ
), and is publicly verifiable. Let
a NIZK
π
_{2}
is transformed from the zero knowledge proof of knowledge
In particular, we use the Fiat-Shamir heuristics
[33]
to transform the honest verifier zero-knowledge proof for showing the inequality of two discrete logarithms in
[34]
, into a non-interactive zero-knowledge proof. The detailed techniques can be found in
Fig. 2
.
A NIZK proof in the algorithm UndeniableProof
Remark 1.
It is noticed that our construction supports blockless verification. That is to say, for both efficiency and security concerns, no challenged file blocks should be retrieved by the verifier or TPA during the verification process. In addition, the user or TPA in the proposed scheme is fully stateless, which means that the verifier do not need to maintain the state information between audits throughout the long term of data storage.
Remark 2.
Our
UndeniableProof
algorithm actually relies on two NIZK protocols, which are also a DH-tuple witness hiding (WH) protocol and a non Diffie-Hellman(DH)-tuple WH protocol respectively. The concept of WH was introduced by Feige an3d Shamir
[35]
. Informally a two-party protocol between a prover and a verifier is witness hiding if at the end of the protocol the verifier cannot compute any new witness which he did not know before the protocol.
The correctness of Equ.3 analogously derives from the above analysis by replacing (
y_{TPA}, x_{U}
) with(
y_{U}, x_{TPA}
).
Soundness requires that, if any cheating prover that convinces the verification algorithm that storing a file
F
is actually storing that file, which we define that it yields the file
F
to an extractor algorithm that interacts with it using the data integrity verification protocol. We prove the soundness of our protocol in three theorems, while proofs for the second theorem and the third theorem are actually similar as the proofs in
[3]
, and therefore we give the proof sketch of the second and the third theorems.
Theorem 1.
If the underlying basic signature scheme is existentially unforgeable and the computational Diffie-Hellman problem is hard in bilinear groups, then in the random oracle model, except with negligible probability, no adversary against the soundness of our public-verification scheme ever causes the verifier to accept in a data integrity verification protocol instance, except by responding with
correctly computed values
.
Proof: Our proof consists of two steps. Firstly, we show the unforgeability of the underlying basic signature. Consider the underlying basic signature σ
_{0}
= (
H
(
m
_{0}
) ·
u^{mo}
)
^{xU}
on any encoded message
m
_{0}
. Since we use the same construction as
[2]
, the unforgeability is naturally satisfied due to the previous paragraph.
Secondly, we prove the theorem by using a sequence of games. The first game, Game 0, is simply the challenge game, which is similar to the
setup
game between the adversary
A
and the challenger (environment)
C
in
[2]
(in Section 2). Game 1 is almost the same as Game 0 with only one difference. The challenger
C
keeps a list of all signed tags ever issued as part of a store-protocol query. If
A
ever submits a tag either in initiating a data integrity verification protocol or as the challenge tag, the challenger will abort if it is a valid tag that has never been signed by the challenger. Based on the definition of Game 0 and Game 1, it is obviously that we can use the adversary to construct a forger against the signature scheme, if there is a difference in the adversary’s success probability between Game 0 and Game 1.
Game 2 is almost the same as Game 1, except that in Game 2 the challenger keeps a list of its responses to queries from the adversary. Now the challenger observes each instance of the data integrity verification protocol with the adversary. Let
P
= {(
ς, μ, θ
), {
H
(
m_{i}
)}, {Ω
_{i}
},
σ_{R}
} where
s
_{1}
≤
i
≤
s_{c}
is the expected response that would have been obtained from an honest prover. The correctness of
H
(
m_{i}
) can be verified through {
H
(
m_{i}
,Ω
_{i}
}
_{s1 ≤ i ≤ sc}
and
σ_{R}
. The correctness of the proof can be verified based on the equation
Assume the adversary’s response is P´. Because of the authentication in Merkle Tree, the second part in P´ should be the same as {
H
(
m_{i}
,Ω
_{i}
}
_{s1 ≤ i ≤ sc}
and
σ_{R}
. Suppose
P'
= {(
ς', μ', θ'
), {
H
(
m_{i}
)}, {Ω
_{i}
},
σ_{R}
} where
s
_{1}
≤
i
≤
s_{c}
is the adversary’s response. The verification of (
ς', μ', θ'
) is
Obviously,
And also we have
θ’ ≠ θ
, otherwise
μ' = μ
, which contradicts our assumption in this game.
Define Δ
θ = θ’ – θ
. With this adversary, the simulator could break the challenge Computational Diffie-Hellman (CDH) instance as follows: Given (
g, g^{a}, h
) ∈
G
, a CDH-adversary B is asked to output
h^{a}
. Initially, by picking a random value
and a random element
y_{TPA}
∈
G
,
B
sets
y_{U}
=
g^{a}
, and
u
=
gh^{b}
, which implies the private key of the user
U
is
x_{U}
=
a
and is not known by
B
.
B
could answer all signature queries with the similar method in
[1]
, by manipulating the random oracle:
Eventually,
A
outputs
where
s
_{1}
≤
i
≤
s_{c}
. We obtain
From this equation, we have
Therefore,
Unless evaluating the exponent
b
Δ
θ
causes a divide-by-zero. However, because
b
is chosen by the
B
and hidden from the adversary
A
, the probability that
b
Δ
θ
= 0 mod
q
will be only 1 /
q
, which is negligible.
Game 3 is the same as Game 2, with the following difference: as before, the challenger
C
observes the data integrity verification protocol instances. Suppose the file that causes the abort is that the signatures are {
σ_{i}
}.
Suppose (
i, v_{i}
) where
s
_{1}
≤
i
≤
s_{c}
is the query that causes the challenger to abort, and that
A
’s response to that query was
, where
s
_{1}
≤
i
≤
s_{c}
. Let
P
= {(
ς, μ, θ
), {
H
(
m_{i}
)}, {Ω
_{i}
},
σ_{R}
} where
s
_{1}
≤
i
≤
s_{c}
is the expected response obtained from an honest prover. We have proved in Game 2 that
μ' = μ
. It is only the values
θ
and
θ’
that can differ. Define Δ
θ = θ’ – θ
. Finally, the adversary outputs a forged signature
where
s
_{1}
≤
i
≤
s_{c}
. Now we can have:
In case of
ς’ = ς
, from Equ.5, we have 1 =
u
^{Δθ}
. In this case, Δ
θ
= 0 mod
q
. Therefore, we have
θ = θ’
mod
q
. As we analyzed above, there is only negligible difference probability between these games. This completes the proof.
Theorem 2.
Suppose a cheating prover on an
n
-block file
F
is well-behaved in the sense above, and that it is
ε
-admissible. Let
ω
= 1/#
B
+ (
pn
)
^{1}
/ (
n – C
+ 1)
^{c}
. Then, provided that
ε – ω
is positive and non-negligible, it is possible to recover a
ρ
-fraction of the encoded file blocks in
O
(
n
/(
ε – ρ
)) interactions with the cheating prover and in
0
(
n
^{2}
+ (1 +
εn
^{2}
) (
n
) / (
ε – ω
)) time overall.
Proof sketch: The verification process is similar with
[3]
. Therefore, we omit the details of the proof here. We can also prove that extraction always succeeds against a well-behaved cheating prover, with the same probability analysis given in
[3]
. For detailed discussion, we refer to the proof of Theorem 2 in
[3]
or Section 4.2 in
[2]
.
Theorem 3.
Given a fraction of the
n
-blocks of an encoded file
F
, it is possible to recover the entire original file
F
with all but negligible probability.
Proof sketch: By adopting the rate-
ρ
Reed-Solomon codes, this result can be easily achieved, since any
ρ
-fraction of encoded file blocks suffices for decoding. Again, we refer to Section 4.3 in
[2]
.
c
is the number of challenged data blocks. Let
pr
and
ex
denote the time for computing a pairing and an exponentiation in
G
and
G_{t}
, respectively. We compare our DCS-based data integrity verification scheme with three schemes. The first one is the public verifiable version in
[2]
(see the section 3.3 of
[2]
), the second one is the proposition in
[3]
, and the last scheme is the privacy-preserving public auditing scheme in
[5]
(see in scheme C). All compared schemes are based on elliptic curves, and are derived from the same origin, i.e., the framework of proofs of retrievability in
[2]
. We simply call these schemes, including our scheme, as “PoR”-type schemes. Also we mainly concern about the security and time complexity among four schemes, because our scheme adds one more layer comparing to the other schemes while process the remaining communicated messages under the same construction. In addition, we add two algorithms for supporting public verifiability, which slightly increases the computational and communication costs if invoking a TPA.
Table 1
gives the comparison of these schemes within several dimensions. Note that private verifiability means only the data owner can check the proof to know the data integrity information, while no other parties can know that fact. For the schemes in
[3]
and
[5]
, we suppose their TPAs are including the user itself because there is no key-pair for the TPA, and we think they support private verifiability in that case. We remark that in our scheme, a TPA is a semi-trusted party with its own key-pair, as we assume that it only runs the algorithms
TPAVerifyProof
and
Undeniableproof
to check and further publish the integrity information if a dispute occurs.
A comparison between four “PoR”-type schemes
Time A= the time of proof generation by cloud storage server, or the time of the proof verification by the prover in the scheme in
[2]
;
Time B=the time of proof verification by the user, or the time of the proof verification by the verifier in the scheme in
[2]
;
Time C= the time of proof verification by the third party auditor;
Time D=the time of undeniable proof generation by TPA;
Time E=the time of undeniable proof verification by other parties. Note the time cost in each cell is approximately evaluated by omitting minor factors such as multiplications in bilinear groups.
From the table, we can see that our protocols benefit from the lowest time cost in the verification phases, i.e., Time B and Time C. Our scheme takes only constant exponentiations, even though a bit more pairing-computation. Note our proof generation time is roughly twice as long as the other competitors'. This is because the listed three schemes adopt a variant of “aggregated BLS” signatures to hide the randomnesses in the challenge. However, our scheme employs an advanced version, by adding one more layer to hide the randomnesses via an Elgamal encryption, and thus it results in more time cost. In addition, we stress that our scheme is the first proposition that can effectively protect the data integrity information according to the first row.
Yingjie Xia received his Ph.D. Degree in the College of Computer Science, Zhejiang University in 2009. He was affiliated as a research scientist in National Center for Supercomputing Applications (NCSA), University of Illinois at Urbana-Champaign (UIUC), USA. Now he is an associate professor in Zhejiang University, Hangzhou, Zhejiang, P. R. China. He founded Intelligent Transportation and Information Security Lab (ITIS) in Hangzhou Normal University and serves as its director. His research interests cover distributed computing, high performance computing, data mining, and their applications in intelligent transportation systems. Prof. Xia has published more than 80 research papers.
Xuejiao Liu received her BSc in computer science and technology from Huazhong Normal University, Wuhan, in 2006; Ph.D. degree in network security from Huazhong Normal University, Wuhan, in 2011.She is currently a lecturer in Intelligent Transportation and Information Security Lab at Hangzhou Normal University. Her research interests include network security, applied cryptography and cloud storage security.
Fubiao Xia obtained his BSc in Software Engineering in Fudan Univerisity, and received his MSc in Computer Security, and Ph.D. in Computer Science in Univerisity of Birmingham, G.B. He is presently employed as a research engineer at Shanghai Fudan Microelectronics Group .co .Ltd. His research areas include applied cryptography, software security, embedded software system and security topics in cloud computing.
Xin Sun received his BSc and MSc in Zhejiang University. Now he is an Engineer in Electric Power Research Institute of State Grid, Zhejiang Electric Power Company, Hangzhou, Zhejiang, China. His research interests are in application security testing and penetration testing.
Yuncai Liu received the Ph.D. degree in electrical and computer science engineering from the University of Illinois at Urbana-Champaign in 1990. He worked as an associate researcher at the Beckman Institute of Science and Technology from 1990 to 1991. Since 1991, he had been a system consultant and then a chief consultant of research in Sumitomo Electric Industries Ltd., Japan. In October 2000, he joined the Shanghai Jiao Tong University, China, as a Distinguished Professor. His research interests are in image processing and computer vision, especially in motion estimation, feature detection and matching, and image registration. He also made many progresses in the research of intelligent transportation systems.
Yi Ge is an undergraduate student in school of foreign language, Hangzhou Normal University. She is currently a research student in Intelligent Transportation and Information Security Lab at Hangzhou Normal University. Her research interest is cloud storage security.

1. Introduction

The trends in developing and utilizing cloud computing affect almost every aspects of our society. The ever cheaper and more powerful processors, the increasing network bandwidth, the more reliable and flexible Internet connections
[1]
, together with the “software as a service” (SaaS) computing architecture, promote cloud computing to be the next-generation IT architecture. This promotion moves the software and databases to the centralized data centers, which naturally leads to a new security challenge that the management of the data and services may not be fully trusted.
Comparing with storing data in local, the data uploaded to the cloud will be stored in the remote data centers, which makes the user loss control of his data. So if the cloud experience Byzantine failures occasionally, it will hide the data errors from the users. What’s worse, for saving storage cost, the storage server may intentionally delete parts of rarely accessed data files which belongs to an ordinary user. In short, although outsourcing data in cloud reduces the cost of storage, it doesn’t offer any guarantee on data integrity. In order to solve this problem, a number of data integrity verification schemes
[2
,
3
,
4
,
5]
under different cryptographic primitives and security models have been carried out.
Although some of the existing schemes,
[3
,
5]
can support both public verifiability and dynamic data operations, they still have the risk of privacy leakage in the complicated communication environment in cloud storage. In fact, almost all of the data integrity verification schemes are insecure with the existence of a malicious sniffer. The reason is that the essential job to verify the data integrity proof on some challenge information is to verify an ordinary signature. Such a signature can be simply checked by a malicious sniffer if he has captured all transmitted messages. Note one scheme that can escape from the above risk by supporting private verifiability
[2]
. However, the scheme fails to support public verifiability, which is an important property when a dispute occurs between the prover and the verifier. Meanwhile, considering the tremendous size of stored data in the cloud and resource constraint of clients, another challenge is how can the client find an efficient way to periodically perform integrity verification without the local copy of data files.
Motivated by the problem and challenges in cloud storage, our work and contributions can be summarized in the following three aspects:
(1) By redefining the research problem of data integrity verification in cloud storage, we introduce a new model through both a high-level architecture and a formal syntax. In particular, our model redefines the role of the third party auditor (TPA) to make it more rational than traditional TPAs.
(2) Our scheme is designed to support public verification and data integrity information (DII) for any user. We include a TPA’s public key by adding one encryption layer during the proof generation. This work which concerns the so-called designated confirmer signatures (DCS), gives rise to a more flexible solution for ensuring data ingerity in cloud storage.
(3) We give a formal security proof and analyze the performance of our construction by comparing our scheme with the latest schemes.
The rest of the paper is organized as follows. In Section 2 we discuss related work. Section 3 introduces a new model considering a more complicated communication environment in clouds. We introduce some preliminaries of our work and propose a new practical scheme based on DCS in Section 4. Section 5 gives the security analysis and performance evaluation. Finally, Section 6 concludes the whole paper.
2. Related Work

There has been some work related to data privacy and integrity in cloud storage. Considering the scenario that, Alice uploaded an examination report to cloud storage, and did not want anyone else to know or modify the report, including the cloud administrator. Under such scenario, several access control schemes under cloud computing environments
[6
,
7]
are proposed. Also some cryptographic techniques
[8
,
9
,
10]
are used in cloud storage to implement data privacy and integrity. However, as the complexity of the user structure in cloud storage, it is more difficult to combine encrypting data for privacy with verifying integrity of the encrypted data to support both privacy and integrity.
Up to now, many people have proposed a number of methods for data integrity verification. Shah et al.
[11]
proposed a remote storage auditing method based on pre-computed challenge-response pairs. Ateniese et al.
[12]
proposed a “provable data possession” (PDP) model for ensuring possessions of files on untrusted stores, and they first introduced “homomorphic authenticators” for auditing outsourced data. Shacham and Waters
[2]
introduced a “proof of retrievability” (PoR) model, and presented a new scheme to ensure “possession”, “retrievability”, and “public verifiability” of remote data files. In 2009, Wang et al.
[3]
introduced another construction that possesses all the features of previous schemes, as well as provides dynamic data operations. As improvement, Wang et al.
[5]
presented a privacy-preserving public auditing cryptosystem with batch-auditing, which not only achieves privacy-preserving public auditing, but also enables TPA to perform multiple auditing tasks simultaneously. However, all the work above does not support privacy preserving of users’ data against external auditors, which may occur serious information leakage.
According to recent research, data integrity verification protocols in cloud storage are required to satisfy three features: data dynamics
[3
,
13
,
14]
, public verifiability
[2
,
3
,
5
,
15]
, and privacy against verifiers
[5]
. Hao et al.
[16]
proposed a protocol that supports public verifiability without help of a third party auditor. Zhu et al.
[17]
considered the existence of multiple cloud service providers to cooperatively store and maintain the clients’ data. They presented a cooperative PDP (CPDP) scheme based on homomorphic verifiable response and hash index hierarchy. Stefanov et al.
[18]
presented a practical and authenticated file system by using a large amount of client storage, which supports workloads from large enterprises storing data in the cloud and is resilient against potentially untrustworthy service providers. However, this method requires a large amount of audit cost. The scheme proposed by Cash
[19]
provided proofs of retrievability for dynamic storage. However, as it employs Oblivious RAM (ORAM) as a black box, it brings increased practical overhead. Elaine et al.
[20]
proposed a dynamic PoR scheme with constant client storage whose bandwidth cost is comparable to a Merkle hash tree, which outperforms the constructions of the above schemes.
As summary of this section, how to support both public verifiability of data integrity and privacy preserving remains a big problem in cloud storage.
3. A Secure Data Integrity Verification Model for Cloud Storage

Consider such a scenario in financial environment, a trade company uses a public cloud to maintain its business files. Before retrieving a stored file, the company always performs data integrity verification with the cloud. Once such verification fails, which implies the stored data has been tampered, the company needs some time to deal with the accident and is probably unwilling to reveal the gloomy news. However, in the traditional data integrity verification systems a malicious sniffer by sniffing the communication between the company and the cloud, can simply check the integrity proof since the validation process does not rely on any secret information regarding to the verifier.
To protect DII, it is necessary to seek a secure way to verify a data integrity proof. More specifically, we shall let a verifier with its secret information be able to check the proof which is generated with respect to the particular verifier. However, this again incurs another issue, that is how to handle a dispute between the prover (cloud storage server) and the verifier (the user). In particular, a malicious user can claim
- 3.1 High-level Description

We give an overview of our improved privacy preserving construction for data integrity verification in cloud storage. A user with mobile devices can create a connection with the cloud storage servers (CSS) to retrieve its stored data files. When receiving a request from the user, a CSS will generate a proof which can only be verified by the specific user or TPA. Whenever a dispute occurs, such a proof can again be sent to TPA, which will examine it and generate
PPT Slide

Lager Image

- 3.2 Security Model

We design the security model of a data integrity verification system by extending the model with non-trivial changes. In particular, we design two algorithms, namely
PPT Slide

Lager Image

PPT Slide

Lager Image

4. The Proposed Scheme

- 4.1 Preliminaries

We introduce two building blocks used in our construction.
- Bilinearity: For allu, v∈G, and for alla, b∈Zp, e(ua, vb) = e(u, v)ab.
- Non-degeneracy:e(g, g) ≠ 1 , where 1 is the multiplicative identity of groupGt.
- Computability:ecan be efficiently computed.

- 4.2 Intuition Behind

A common paradigm of constructing a DCS scheme is “sign-and-encrypt”
[29]
. For example, to generate a proper DCS, a signer firstly computes an ordinary signature on the target message
- 4.3 Our Construction

We assume the client encodes the raw file
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

5. Evaluation

We give formal security analysis and performance analysis for our DCS-based data integrity verification scheme. The results below show that our scheme is both secure and efficient. On the other hand, our scheme achieves high flexibility for balancing the public and private verifiability by using the means of designated confirmer signature.
- 5.1 Security Analysis

We analyze our construction in two dimensions, i.e., we shall guarantee that our data integrity verification protocol is both correct and sound.
As shown in the Equ.4, we simply show the correctness of our construction by showing the correctness of Equ.2.
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- 5.2 Performance Analysis

Recall
A comparison between four “PoR”-type schemes

PPT Slide

Lager Image

6. Conclusion and Future Works

To ensure cloud data storage security, we propose a new architecture of data integrity verification system which limits the public verifiability of data integrity proofs in a public cloud. By deploying designated confirmer signatures, we construct a new practical scheme to resist the risk of data integrity information leakage. On one hand, our scheme achieves a more flexible verification mechanism compared with the schemes in
[2]
. Note that all these schemes supporting “public verifiability” actually reveal the data integrity information for any user. Our scheme maintains two-levels, i.e., a private verification with regard to a specific user, and a public verification with regard to a TPA. On the other hand, our scheme still benefits from the features of being blockless and stateless. In fact, no local copies of the challenged data blocks in CSS will be retrieved by the verifier (or a TPA) during the verification process, and there is no need to maintain information in a single verification process between different audits throughout the long term of data storage.
In future work, we will improve the construction to support data dynamics. In particular, the scheme which can support block modification, insertion, and deletion is a significant step towards practicality. Moreover, we plan to further prove the efficiency and effectiveness of our scheme for data integrity verification in cloud storage.
BIO

Xia Y.
,
Zhu M.
,
Li Y.
2010
“Towards topology-and-trust-aware P2P grid,”
Journal of Computers
5
(9)
1315 -
1321
** DOI : 10.4304/jcp.5.9.1315-1321**

Shacham H.
,
Waters B.
2008
“Compact proofs of retrievability,”
in Proc. of the 14th International Conference on the Theory and Application of Cryptology and Information Security
90 -
107

Wang Q.
,
Wang C.
,
Li J.
,
Ren K.
,
Lou W.
2009
“Enabling public verifiability and data dynamics for storage security in cloud computing,”
in Proc. of the 14th European Symposium on Research in Computer Security
355 -
370

Juels A.
,
Kaliski B. S.
,
Pors
2007
“Proofs of retrievability for large files,”
in Proc. of the 14th ACM Conference on Computer and Communications Security
584 -
597

Wang C.
,
Wang Q.
,
Ren K.
,
Lou W.
2010
“Privacy-preserving public auditing for data storage security in cloud computing,”
in Proc. of the 29th Conference on Information Communications
525 -
533

Xia Y.
,
Kuang L.
,
Zhu M.
2010
“A hierarchical access control scheme in cloud using HHECC,”
Information Technology Journal
9
(8)
1598 -
1606
** DOI : 10.3923/itj.2010.1598.1606**

Liu X.
,
Xia Y.
,
Jiang Sh.
,
Xia F.
2013
“Hierarchical attribute-based access control with authentication to outsourced data in cloud computing,”
in Proc. of the 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications
477 -
484

Yoon Y.
,
Oh J.
,
Lee B.
2013
“The Establishment of Security Strategies for Introducing Cloud Computing,”
KSII Transactions on Internet and Information Systems
7
(4)
860 -
877
** DOI : 10.3837/tiis.2013.04.015**

Zhang L.
,
Hu Y.
2013
“New Constructions of Hierarchical Attribute-Based Encryption for Fine-Grained Access Control in Cloud Computing,”
KSII Transactions on Internet and Information Systems
7
(5)
1343 -
1356
** DOI : 10.3837/tiis.2013.05.023**

Kim J.
,
Park C.
,
Hwang J.
,
Kim H.
2013
“Privacy Level Indicating Data Leakage Prevention System,”
KSII Transactions on Internet and Information Systems
7
(3)
558 -
575
** DOI : 10.3837/tiis.2013.03.009**

Shah M. A.
,
Baker M.
,
Mogul J. C.
,
Swaminathan R.
2007
“Auditing to keep online storage services honest,”
in Proc. of the 11th USENIX Workshop on Hot Topics in Operating Systems
1 -
6

Ateniese G.
,
Burns R.
,
Curtmola R.
,
Herring J.
,
Kissner L.
,
Peterson Z.
,
Song D.
2007
“Provable data possession at untrusted stores,”
in Proc. of the 14th ACM Conference on Computer and Communications Security
598 -
609

Ateniese G.
,
Di Pietro R.
,
Mancini L. V.
,
Tsudik G.
2008
“Scalable and efficient provable data possession,”
in Proc. of the 4th International Conference on Security and Privacy in Communication Networks, No. 9

Erway C.
,
Küpçü A.
,
Papamanthou C.
,
Tamassia R.
2009
“Dynamic provable data possession,”
in Proc. of the 16th ACM Conference on Computer and Communications Security
213 -
222

Bowers K. D.
,
Juels A.
,
Oprea A.
2009
Proofs of retrievability: “Theory and implementation,”
in Proc. of the 16th ACM Workshop on Cloud Computing Security
43 -
54

Hao Z.
,
Zhong S.
,
Yu N.
2011
“A privacy-preserving remote data integrity checking protocol with data dynamics and public verifiability,”
IEEE Transactions on Knowledge and Data Engineering
23
(9)
1432 -
1437
** DOI : 10.1109/TKDE.2011.62**

Zhu Y.
,
Hu H.
,
Ahn G.
,
Yu M.
2012
“Cooperative provable data possession for integrity verification in multi-cloud storage,”

Stefanov E.
,
van Dijk M.
,
Juels A.
,
Oprea A.
,
Iris
2012
“A scalable cloud file system with efficient integrity checks,”
in Proc. of the 28th Annual Computer Security Applications Conference
229 -
238

Cash D.
,
Küpçü A.
,
Wichs D.
2013
“Dynamic proofs of retrievability via oblivious ram,” Advances in Cryptology–EUROCRYPT
279 -
295

Shi E.
,
Stefanov E.
,
Papamanthou C.
2013
“Practical dynamic proofs of retrievability,”
in Proc. of the 2013 ACM SIGSAC conference on Computer & Communications Security
325 -
336

Chaum D.
1995
“Designated confirmer signatures,” Advances in Cryptology
86 -
91

Lay G.-J.
,
Zimmer H. G.
1994
“Constructing elliptic curves with given group order over large finite fields,”
in Proc. of the 1st International Symposium on Algorithmic Number Theory
250 -
263

Menezes A. J.
,
Okamoto T.
,
Vanstone S. A.
1993
“Reducing elliptic curve logarithms to logarithms in a finite field,”
IEEE Transactions on Information Theory
39
(5)
1639 -
1646
** DOI : 10.1109/18.259647**

Semaev I.
1998
“Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p,”
Mathematics of Computation of the American Mathematical Society
67
(221)
353 -
356
** DOI : 10.1090/S0025-5718-98-00887-4**

Smart N. P.
1999
“The discrete logarithm problem on elliptic curves of trace one,”
Journal of Cryptology
12
(3)
193 -
196
** DOI : 10.1007/s001459900052**

Galbraith S. D.
,
Smart N. P.
1999
“A cryptographic application of weil descent,”
in Proc. of 7th Institute of Mathematics and its Applications International Conference
191 -
200

Zhang L.
,
Wu Q.
,
Hu Y.
2011
“New Constructions of Identity-based Broadcast Encryption without Random Oracles,”
KSII Transactions on Internet and Information Systems
5
(2)
247 -
276

Hitchcock Y.
,
Dawson E.
,
Clark A.
,
Montague P.
2003
“Implementing an efficient elliptic curve cryptosystem over gf(p) on a smart card,”
ANZIAM Journal
44
354 -
377

Wang G.
,
Xia F.
,
Zhao Y.
2011
“Designated confirmer signatures with unified verification,” Cryptography and Coding
469 -
495

Boneh D.
,
Lynn B.
,
Shacham H.
2001
“Short signatures from the weil pairing,”
in Proc. of Annual Cryptographical and Cryptoanalytic Conference
514 -
532

El Gamal T.
1985
“A public key cryptosystem and a signature scheme based on discrete logarithms,” Advances in Cryptology
10 -
18

Goh E.
,
Jarecki S.
2003
“A signature scheme as secure as the diffie-hellman problem,”
Lecture Notes in Computer Science
in Proc. of Annual International Conference on the Theory and Applications of Cryptographic Techniques
401 -
415

Fiat A.
,
Shamir A.
1987
“How to prove yourself: practical solutions to identification and signature problems,lecture notes in computer science,”
in Proc. of Annual Cryptographical and Cryptoanalytic Conference
186 -
194

Kurosawa K.
,
Heng S.-H.
2005
“3-move undeniable signature scheme,”
in Proc. of 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques
181 -
197

Feige U.
,
Shamir A.
1990
“Witness indistinguishable and witness hiding protocols,”
in Proc. of the 22th Annual ACM Symposium on Theory of Computing
416 -
426

Citing 'An Improved Privacy Preserving Construction for Data Integrity Verification in Cloud Storage
'

@article{ E1KOBZ_2014_v8n10_3607}
,title={An Improved Privacy Preserving Construction for Data Integrity Verification in Cloud Storage}
,volume={10}
, url={http://dx.doi.org/10.3837/tiis.2014.10.019}, DOI={10.3837/tiis.2014.10.019}
, number= {10}
, journal={KSII Transactions on Internet and Information Systems (TIIS)}
, publisher={Korean Society for Internet Information}
, author={Xia, Yingjie
and
Xia, Fubiao
and
Liu, Xuejiao
and
Sun, Xin
and
Liu, Yuncai
and
Ge, Yi}
, year={2014}
, month={Oct}