Fuzzy Keyword Search over Encrypted Data in Cloud Computing

[attachment=18361]

Abstract—

As Cloud Computing becomes prevalent, more and
more sensitive information are being centralized into the cloud.
For the protection of data privacy, sensitive data usually have to
be encrypted before outsourcing, which makes effective data utilization
a very challenging task. Although traditional searchable
encryption schemes allow a user to securely search over encrypted
data through keywords and selectively retrieve files of interest,
these techniques support only exact keyword search. That is,
there is no tolerance of minor typos and format inconsistencies
which, on the other hand, are typical user searching behavior
and happen very frequently. This significant drawback makes
existing techniques unsuitable in Cloud Computing as it greatly
affects system usability, rendering user searching experiences
very frustrating and system efficacy very low.



I. INTRODUCTION
As Cloud Computing becomes prevalent, more and more
sensitive information are being centralized into the cloud, such
as emails, personal health records, government documents, etc.
By storing their data into the cloud, the data owners can be
relieved from the burden of data storage and maintenance so
as to enjoy the on-demand high quality data storage service.
However, the fact that data owners and cloud server are not in
the same trusted domain may put the oursourced data at risk,
as the cloud server may no longer be fully trusted. It follows
that sensitive data usually should be encrypted prior to outsourcing
for data privacy and combating unsolicited accesses.
However, data encryption makes effective data utilization a
very challenging task given that there could be a large amount
of outsourced data files. Moreover, in Cloud Computing, data
owners may share their outsourced data with a large number
of users. The individual users might want to only retrieve
certain specific data files they are interested in during a given
session.


PROBLEM FORMULATION
A. System Model
In this paper, we consider a cloud data system consisting
of data owner, data user and cloud server. Given a collection
of n encrypted data files C = (F1, F2, . . . , FN) stored
in the cloud server, a predefined set of distinct keywords
W = {w1,w2, ...,wp}, the cloud server provides the search
service for the authorized users over the encrypted data C. We
assume the authorization between the data owner and users
is appropriately done. An authorized user types in a request
to selectively retrieve data files of his/her interest. The cloud
server is responsible for mapping the searching request to a set
of data files, where each file is indexed by a file ID and linked
to a set of keywords. The fuzzy keyword search scheme returns
the search results according to the following rules: 1) if the
user’s searching input exactly matches the pre-set keyword, the
server is expected to return the files containing the keyword1;
2) if there exist typos and/or format inconsistencies in the
searching input, the server will return the closest possible
results based on pre-specified similarity semantics (to be
formally defined in section III-D).


CONCLUSION
In this paper, for the first time we formalize and solve the
problem of supporting efficient yet privacy-preserving fuzzy
search for achieving effective utilization of remotely stored
encrypted data in Cloud Computing. We design an advanced
technique (i.e., wildcard-based technique) to construct the
storage-efficient fuzzy keyword sets by exploiting a significant
observation on the similarity metric of edit distance. Based
on the constructed fuzzy keyword sets, we further propose
an efficient fuzzy keyword search scheme. Through rigorous
security analysis, we show that our proposed solution is secure
and privacy-preserving, while correctly realizing the goal of
fuzzy keyword search.