Fuzzy Keyword Search over Encrypted Data in Cloud Computing

By Jin Li, Qian Wang, Cong Wang, Ning Cao, Kui Ren, Wenjing Lou. 2010 Proceedings IEEE INFOCOM, 2010

595 citations recorded by the source corpus.

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. In this paper, for the first time we formalize and solve the problem of effective fuzzy keyword search over encrypted cloud data while maintaining keyword privacy. Fuzzy keyword search greatly enhances system usability by returning the matching files when users' searching inputs exactly match the predefined keywords or the closest possible matching files based on keyword similarity semantics, when exact match fails. In our solution, we exploit edit distance to quantify keywords similarity and develop an advanced technique on constructing fuzzy keyword sets, which greatly reduces the storage and representation overheads. Through rigorous security analysis, we show that our proposed solution is secure and privacy-preserving, while correctly realizing the goal of fuzzy keyword search.

Subfields: Artificial Intelligence, Information Systems

View Paper: https://www.semanticscholar.org/paper/a3072a044575760e0a6fd20e353f3f44d86f692d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

Enabling Personalized Search over Encrypted Outsourced Data with Efficiency Improvement (2016, background): “The new contributions in this paper compared with [11], [12], [13], [14], [15], [16], [19], [32], [33] are summarized as follows: 1) For the first time, we explore the problem of personalized multi-keyword ranked search over encrypted cloud data.”
Securing Fog Computing for Internet of Things Applications: Challenges and Solutions (2018, methodology): “In symmetric searchable encryption, some works extended single keyword search and Boolean query to support various search patterns, including fuzzy keyword search [166]”
Efficient verifiable fuzzy keyword search over encrypted data in cloud computing (2013, methodology): “We compare the proposed algorithm with Li’s scheme [15] and Chai’s scheme [9].”
Blockchain Meets Cloud Computing: A Survey (2020, methodology): “[101] replaced exact matching by the fuzzy keyword search, which returned the result with the highest”
Achieving usable and privacy-assured similarity search over outsourced cloud data (2012, methodology): “technique proposed in our preliminary work [12].”
Enabling Secure and Efficient Ranked Keyword Search over Outsourced Cloud Data (2012, unknown): “in [29].”
Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud (2014, methodology): “2) In contrast to previous fuzzy keyword search solutions [12]–[14], which require expanded storage for wild-card based fuzzy keyword set, our scheme exploits localitysensitive hashing to provide efficient fuzzy search with constant size index regardless the number of keywords associated with the…”
Toward Efficient Multi-Keyword Fuzzy Search Over Encrypted Outsourced Data With Accuracy Improvement (2016, methodology): “However, the cloud server is honest-but-curious as in [12]–[14].”
Data Security and Privacy Protection for Cloud Storage: A Survey (2020, background): “Therefore, how to enable users to search for speciﬁc keywords on encrypted ﬁles securely in the cloud has become the concern of many scholars [5], [46], [48], [52], [76].”
Privacy-preserving multi-keyword ranked search over encrypted cloud data (2011, methodology): “Computation time (also called "running time") is the length of time required to perform a computational process for example searching a keyword, generating trapdoor etc. Computation overhead is related to CPU utilization in terms of resource allocation measured in time.”
A Survey of Provably Secure Searchable Encryption (2014, unknown): “Li et al. [2010] (LWW+) propose a search scheme for fuzzy keyword searches based on prespecified similarity semantics using the Edit distance (number of operations (substitution, deletion, insertion) required to transform one word into another).”
Verifiable symmetric searchable encryption for semi-honest-but-curious cloud servers (2012, background): “Various searchable encryption schemes, e.g., [6] [5] [10] [3] [1] [2] [8], have been proposed to fight against a computationally bounded adversary called honestbut-curious server, who (1) stores the outsourced data without tampering it; (2) honestly executes every search operation and returns…”
Privacy-Preserving Multi-Keyword Ranked Search over Encrypted Cloud Data (2014, background): “Traditional single keyword searchable encryption schemes [7], [8], [9], [10], [11], [12], [13], [14], [15], [25], [26] usually build an encrypted searchable index such that its content is hidden to the server unless it is given appropriate trapdoors generated via secret key(s) [4].”
DACC: Distributed Access Control in Clouds (2011, background): “Efficient and secure keyword searches are required in clouds, which maintain large amounts of sensitive data [14], [15].”
Secure Ranked Keyword Search over Encrypted Cloud Data (2010, background): “Very recently, aiming at tolerance of both minor typos and format inconsistencies in the user search input, fuzzy keyword search over encrypted cloud data has been proposed by Li. et al in [22].”