An Efficient and Privacy-Preserving Semantic Multi-Keyword Ranked Search over Encrypted Cloud Data

Zhihua Xia, Li Chen, Xingming Sun, Jin Wang2013 · DOI

TL;DR

This paper introduces a novel method for searching encrypted data in the cloud that goes beyond exact keyword matching. By leveraging Latent Semantic Analysis (LSA) and secure k-Nearest Neighbor (k-NN) techniques, it enables semantic search over encrypted data, returning relevant documents even if they don't contain the exact query terms but are semantically related. This enhances search accuracy and privacy for cloud-stored sensitive data.

What Problem Does This Paper Address?

As more individuals and organizations move their data to cloud storage for convenience and cost-effectiveness, a critical challenge arises: how to search this data effectively while maintaining its privacy. Sensitive data is typically encrypted before being uploaded to the cloud to prevent unauthorized access. However, standard search techniques become unusable on encrypted data. Existing fuzzy search methods can handle minor typos but often fail to capture the deeper semantic relationships between words (like synonyms or related concepts), leading to missed relevant results. This paper tackles the problem of enabling efficient, privacy-preserving, and semantic multi-keyword ranked search over encrypted cloud data, aiming to retrieve not just exact matches but also conceptually related documents.

Methods

The proposed scheme combines two core techniques:

  • Latent Semantic Analysis (LSA): This technique is used to uncover the underlying semantic structure between terms and documents. LSA employs Singular Value Decomposition (SVD) on a term-document matrix to represent words and documents in a lower-dimensional "semantic space." This allows the system to identify relationships between terms that might not be explicitly present in the text, such as synonyms or related concepts. The paper uses LSA to build a searchable index that captures these latent semantic associations.
  • Secure k-Nearest Neighbor (k-NN): To perform the search securely over encrypted data, the paper adapts a privacy-preserving k-NN scheme. This technique is used to compute the similarity between the query and the encrypted documents in a way that prevents the cloud server from learning any information about the query or the data itself. The scheme involves building an encrypted index and generating a "trapdoor" for the query, both of which are then used to compute similarity scores without decryption.

The process involves the data owner building an encrypted index using LSA, encrypting the data, and uploading both to the cloud. A data user then submits a query, which is transformed into a trapdoor. The cloud server uses the trapdoor and the encrypted index to compute similarity scores and returns the top-ranked encrypted files.

Datasets

The paper evaluates its proposed technique on the MED dataset. The authors do not introduce a new benchmark dataset but rather use an existing one for their experimental evaluation.

Key Insights and Ideas

  • Semantic Search is Crucial for Cloud Data: The paper highlights that simply matching exact keywords is insufficient for effective search, especially when dealing with large, diverse datasets in the cloud. Capturing semantic relationships is key to retrieving truly relevant information.
  • LSA as a Foundation for Semantic Indexing: LSA provides a powerful way to automatically discover and represent the implicit semantic structure within a document collection, making it suitable for building richer, semantically aware indexes.
  • Combining LSA with Secure Search for Privacy: The core innovation lies in integrating LSA's semantic capabilities with secure k-NN techniques. This allows for semantic search without compromising the privacy of the encrypted data stored in the cloud.
  • Beyond Exact Matches: The scheme's ability to return documents that are semantically associated with query keywords, not just exact matches, is a significant advantage over traditional or even basic fuzzy search methods.

Key Results

The paper presents experimental results comparing their proposed LSA-based multi-keyword ranked search (LSA-MRSE) scheme with the original MRSE scheme. The key finding is that the LSA-MRSE scheme achieves a higher F-measure score than the original MRSE. This indicates improved performance in terms of both precision and recall. The authors attribute this improvement to their scheme's ability to capture semantic relationships, which allows it to retrieve relevant files that the original scheme, relying on exact matching, would miss. Figure 2 visually demonstrates this superior performance.

Limitations and Future Work

  • Limitations: The paper focuses on the core mechanism of semantic search over encrypted data. While it demonstrates improved performance, specific details on the computational overhead of LSA and secure k-NN in a large-scale cloud environment are not deeply explored in the provided excerpt. The security analysis is mentioned but not detailed in the excerpt.
  • Future Work: The paper suggests that their method is better than the original MRSE scheme. While not explicitly detailed in the excerpt, future work would likely involve further optimization of the LSA and secure k-NN components for greater efficiency, more comprehensive security analysis, and potentially extending the scheme to handle more complex query types or data structures.

Summary updated

Abstract

As so much advantage of cloud computing, more and more data owners centralize their sensitive data into the cloud. With a mass of data files stored in the cloud server, it is important to provide keyword based search service to data user. However, in order to protect the data privacy, sensitive data is usually encrypted before outsourced to the cloud server, which makes the search technologies on plaintext unusable. In this paper, we propose a semantic multi-keyword ranked search scheme over the encrypted cloud data, which simultaneously meets a set of strict privacy requirements. Firstly, we utilize the “Latent Semantic Analysis” to reveal relationship between terms and documents. The latent semantic analysis takes advantage of implicit higher-order structure in the association of terms with documents (“semantic structure”) and adopts a reduced-dimension vector space to represent words and documents. Thus, the relationship between terms is automatically captured. Secondly, our scheme employ secure “k-nearest neighbor (k-NN)” to achieve secure search functionality. The proposed scheme could return not only the exact matching files, but also the files including the terms latent semantically associated to the query keyword. Finally, the experimental result demonstrates that our method is better than the original MRSE scheme.
BibTeX
@misc{xia2013efficient,
  author = {Zhihua Xia and Li Chen and Xingming Sun and Jin Wang},
  title = {{An Efficient and Privacy-Preserving Semantic Multi-Keyword Ranked Search over Encrypted Cloud Data}},
  year = {2013},
  doi = {10.14257/astl.2013.31.58},
}
Figure