Secure Cloud Storage Hits Distributed String
Equality Checking: More Efficient, Conceptually
Simpler, and Provably Secure
Fei Chen
∗¶
, Tao Xiang
†
, Yuanyuan Yang
‡
, Cong Wang
§
, Shengyu Zhang
¶
∗
Department of Computer Science and Engineering, Shenzhen University. Email:feichenn@gmail.com.
†
College of Computer Science, Chongqing University. Email: txiang@cqu.edu.cn.
‡
Department of Electrical and Computer Engineering, Stony Brook University. Email: yuanyuan.yang@stonybrook.edu.
§
Department of Computer Science, City University of Hong Kong. Email: congwang@cityu.edu.hk.
¶
Department of Computer Science and Engineering, The Chinese University of Hong Kong. Email:syzhang@cse.cuhk.edu.hk.
Abstract—Cloud storage has gained a remarkable success
in recent years with an increasing number of consumers and
enterprises outsourcing their data to the cloud. To assure the
availability and integrity of the outsourced data, several pro-
tocols have been proposed to audit cloud storage. Despite the
formally guaranteed security, the constructions employed heavy
cryptographic operations as well as advanced concepts (e.g.,
bilinear maps over elliptic curves and digital signatures), and
thus are inefficient to admit wide applicability in practice. In
this paper, we design a novel secure cloud storage protocol,
which is conceptually and technically simpler and significantly
more efficient than previous constructions. Inspired by a classic
string equality checking protocol in distributed computing, our
protocol uses only basic integer arithmetic (without advanced
techniques and concepts). As simple as the protocol is, it supports
both randomized and deterministic auditing to fit different
applications. We further extend the proposed protocol to support
data dynamics, i.e., adding, deleting and modifying data, using a
novel technique. As a further contribution, we find a systematic
way to design secure cloud storage protocols based on verifiable
computation protocols. Theoretical and experimental analyses
validate the efficacy of our protocol.
I. INTRODUCTION
With the increasing popularity of cloud computing, the
security of cloud storage has recently drawn considerable
attention from the research community [1]–[7]. Various pro-
tocols with different strengths and weaknesses which can
check the integrity of outsourced data have been proposed for
securing cloud storage [1]–[7]. One can categorize the existing
protocols from different perspectives. When functionality is
concerned, some protocols do not support full data dynamics
[1]–[3], [7], while the others do [4]–[6]. From the security
perspective, some protocols rely their security on standard
model [1], [2], [6], while others assume the random oracle
model (ROM) [3]–[5]. From the technical perspective, some
protocols employ only basic number theoretic operations [1]–
[3], [7], while others build heavily on bilinear parings over
The corresponding author is Tao Xiang (txiang@cqu.edu.cn).
elliptic curves [4], [5]; these different techniques incur differ-
ent efficiency.
For practical applicability of cloud storage with protection
for users against potentially malicious clouds, one desires
protocols without heavy cryptographic operations yet still
efficient and able to support data dynamics and third-party
auditing. In this paper, we provide a provably secure cloud
storage protocol with conceptual and technical novelty. At the
same time, the protocol does not need any heavy cryptographic
operation, yet supports data dynamics under a malicious cloud.
Our protocol is inspired by a classic protocol solving the
string equality checking problem in communication com-
plexity of distributed computing [8], [9]. Our protocol runs
basically as follows: 1) we model the data as a vector in some
vector space; 2) when the user checks the availability and
integrity of the outsourced data, the user asks the cloud to
compute an inner product of the data with some challenge
vector in a “verifiable” way; 3) the verifiability of the inner
product ensures the integrity of the cloud storage.
Our protocol enjoys several merits. First, it is very efficient
because it involves only integer additions and multiplications,
which enables a fast implementation. Besides, our protocol is
conceptually and technically very simple and does not rely
on heavy cryptograhic operations. The proposed protocol only
uses inner product of the input string and some randomly
chosen strings together with pseudorandom functions. Further-
more, our protocol is provably secure under a formal definition
with real-world motivations of security.
We further propose a novel method for supporting data
dynamics. In the protocol design, we associate with each data
block a unique sequence number to ensure verifiability of
outsourced data in the cloud. Supporting data insertion and
deletion is pretty challenging when modeling the cloud as
malicious. To solve the data dynamics problem, we employ
two ideas: the first is to increase the sequence number all
the time whenever new data is inserted; the second is to
re-normalize the sequence number periodically such that no