1918 IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 10, NO. 9, SEPTEMBER 2015
Security Analysis on One-to-Many Order
Preserving Encryption-Based Cloud Data Search
Ke Li, Weiming Zhang, Ce Yang, and Nenghai Yu
Abstract—For ranked search in encrypted cloud data, order
preserving encryption (OPE) is an efficient tool to encrypt
relevance scores of the inverted index. When using determinis-
tic OPE, the ciphertexts will reveal the distribution of relevance
scores. Therefore, Wang et al. proposed a probabilistic OPE,
called one-to-many OPE, for applications of searchable encryp-
tion, which can flatten the distribution of the plaintexts. In this
paper, we proposed a differential attack on one-to-many OPE
by exploiting the differences of the ordered ciphertexts. The
experimental results show that the cloud server can get a good
estimate of the distribution of relevance scores by a differential
attack. Furthermore, when having some background information
on the outsourced documents, the cloud server can accurately
infer the encrypted keywords using the estimated distributions.
Index Terms—Searchable encryption, order preserving
encryption, privacy, cloud computing.
I. INTRODUCTION
N
OWADAYS users connected to the Internet may store
their data on cloud servers and let the servers manage
or process their data. They can enjoy convenient and efficient
service without paying too much money and energy, as one of
the most attractive feature of cloud computing is its low
cost [1].
However, no matter how advantageous cloud computing
may sound, large number of people still worry about the
safety of this technology. If cloud server get direct access
to all these users’ data, it may try to analyse the documents
to get private information. The initial purpose of this action
may be kind. The server wants to provide better service by
digging into these data and then displaying customer-oriented
advertisement, which could be convenient but also annoying.
Besides, when we consider sensitive data such as personal
health records and secret chemical ingredients, the situation
becomes even more serious [2]. Theoretically, the server is
not supposed to have access to sensitive data at all; therefore
we should ensure the server has no access to leaking these
Manuscript received January 14, 2015; revised March 19, 2015; accepted
May 3, 2015. Date of publication May 20, 2015; date of current version
July 22, 2015. This work was supported in part by the National Natural
Science Foundation of China under Grant 61170234 and Grant 60803155, in
part by the Strategic Priority Research Program through the Chinese Academy
of Sciences under Grant XDA06030601, and in part by the Funding of Science
and Technology on Information Assurance Laboratory under Grant KJ-13-02.
The associate editor coordinating the review of this manuscript and approving
it for publication was Prof. Wanlei Zhou.
The authors are with the CAS Key Laboratory of Electromagnetic
Space Information, University of Science and Technology of China,
Hefei 230026, China (e-mail: lee0525@mail.ustc.edu.cn; zhangwm@
ustc.edu.cn; yangce@mail.ustc.edu.cn; ynh@ustc.edu.cn).
Color versions of one or more of the figures in this paper are available
online at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TIFS.2015.2435697
data to an untrusted third party. Thus, sensitive data have to
be encrypted before being outsourced to a commercial public
cloud [3].
However, encryption on sensitive data presents obstacles
to the processing of the data. Information retrieval becomes
difficult in the encrypted domain because the amount of
outsourced files can be very large and traditional search
patterns can not be deployed to ciphertext retrieval directly.
Users need to download all the data, decrypt it all, and then
search keywords like plaintext retrieval. To overcome this,
Searchable Encryption (SE) [4] was proposed to make query
in the encrypted domain possible while still preserving users’
privacy. There are several problems in searchable encryption:
fuzzy search, ranked search, multi-keyword search and so on.
Song et al. [5] first proposed a search scheme only supporting
single Boolean keyword search. After that plenty of searchable
encryption methods [6]–[9] arose to improve efficiency and
reduce communication overhead.
Applying order preserving encryption (OPE) [10] is one
practical way of supporting fast ranked search. This algorithm
was first proposed in 2004 to solve encrypted query problems
in database systems. OPE is a symmetric cryptosystem,
therefore it is also called order-preserving symmetric
encryption (OPSE). The order-preserving property means that
if the plaintexts x
1
< x
2
, then the corresponding ciphertexts
E(x
1
) and E(x
2
) satisfy E(x
1
)<E(x
2
).
Boldyreva et al. initiated the cryptographic study of
OPE schemes [11], [12], in which they defined the security of
OPE and proposed a provably secure OPE scheme. However,
the security definition and the constructions of OPE
in [11] and [12] are based on the assumption that OPE
is a deterministic encryption scheme which means that a
given plaintext will always be encrypted as a fixed ciphertext.
However, deterministic encryption leaks the distribution of
the plaintexts, so it cannot ensure data privacy in most
applications. For instance, in privacy-preserving keywords
search, OPE is used to encrypt relevance scores in the inverted
index [16]. As noted by Wang et al. [16], when using a deter-
ministic OPE, the resulting ciphertext shares exactly the same
distribution as the relevance score, by which the server can
specify the keywords [14], [15]. Therefore, Wang et al. [16]
improved the OPE in [11] and proposed a “One-to-Many OPE”
in their secure keyword search scheme, where they tried to
construct a probabilistic encryption scheme and conceal the
distribution of the plaintexts.
However, we discover that the One-to-Many OPE [16]
cannot ensure the expected security. In fact, although the
ciphertexts of One-to-Many OPE conceals the distribution
1556-6013 © 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.