Privacy-preserving Multi-keyword Ranked Search over Encrypted Cloud Data Supporting Dynamic Update

Xingming Sun, Lu Zhou, Zhangjie Fu, Jin WangInternational Journal of Security and Its Applications 2014 · DOI

Abstract

With the development of cloud computing, the sensitive information of outsourced data is at risk of unauthorized accesses. To protect data privacy, the sensitive data should be encrypted by the data owner before outsourcing, which makes the traditional and efficient plaintext keyword search technique useless. Hence, it is an especially important thing to explore secure encrypted cloud data search service. Considering the huge number of outsourced data, there are three problems we are focused on to enable efficient search service: multi-keyword search, result relevance ranking and dynamic update. In this paper, we propose a practically efficient and flexible searchable encrypted scheme which supports both multi-keyword ranked search and dynamic update. To support multi-keyword search and result relevance ranking, we adopt Vector Space Model (VSM) to build the searchable index to achieve accurate search result. To improve search efficiency, we design a tree-based index structure which supports insertion and deletion update well without privacy leakage. We propose a secure search scheme to meet the privacy requirements in the threat model. Finally, experiments on real-world dataset are implemented to demonstrate the overall performance of the proposed scheme, which show our scheme is efficient.

Introduction

As organizations increasingly migrate their data to cloud environments, encryption has become the standard defense against unauthorized access. However, encrypting data typically renders it unsearchable by traditional means, creating a significant bottleneck for usability. Early Searchable Symmetric Encryption (SSE) schemes often struggled with three major limitations: they were restricted to single-keyword searches, lacked relevance ranking for results, and were static, requiring a full index rebuild for any document update. This paper addresses these challenges by introducing a dynamic, multi-keyword ranked search scheme that maintains high efficiency and privacy.

System Architecture

The proposed framework consists of three primary entities: the Data Owner, the Cloud Server, and the Data User.

System architecture of the proposed searchable encryption scheme.

The Data Owner is responsible for encrypting the document collection and constructing a secure searchable index tree. Both are then outsourced to the cloud. The Data User generates encrypted search queries, known as trapdoors, which are sent to the cloud. The Cloud Server then executes the search over the encrypted index and returns the top-$k$ most relevant documents to the user without ever learning the underlying plaintext data or keywords.

Methodology

Vector Space Model and Ranking

To provide accurate search results, the scheme employs the Vector Space Model (VSM) combined with the Term Frequency × Inverse Document Frequency (TF-IDF) rule. Each document and query is represented as a vector, where each dimension corresponds to a keyword's weight. This allows the cloud server to calculate relevance scores using cosine similarity, ensuring that the most pertinent documents are ranked highest.

Tree-Based Index Structure

The core innovation for efficiency is a balanced binary tree index. This structure allows the system to scale effectively with large datasets.

The tree-based index structure used for efficient multi-keyword ranked search.

As illustrated in Figure 2, leaf nodes ($d_1, d_2, \dots$) represent individual documents and store their encrypted relevance vectors. Internal nodes ($r_{11}, r_{12}, \dots$) store aggregated vectors that summarize the keyword information of their respective subtrees. During a search, the server can "prune" entire branches that do not meet a certain relevance threshold, reducing the search complexity from linear ($O(m)$) to approximately logarithmic ($O(r \log m)$), where $r$ is the number of matching documents.

Secure Search and Dynamic Updates

To protect privacy, the scheme uses a secure k-nearest neighbor (kNN) computation technique involving vector splitting and secret matrix multiplication. This ensures that the cloud server can compute similarity scores without knowing the actual vector values. Furthermore, the scheme supports dynamic updates—inserting or deleting documents—through a specialized protocol that modifies the tree structure and updates encrypted vectors without leaking information about the changes.

Performance Evaluation

The scheme was tested using the real-world RFC (Request for Comments) database, containing approximately 6,500 technical publications. Experiments with keyword dictionaries ranging from 2,000 to 10,000 words demonstrated the following:

  • Search Efficiency: For 2,000 documents, search time was approximately 40–50ms, scaling with the number of results rather than the total dataset size.
  • Update Performance: Document updates have a time complexity of $O(n \log m)$, a significant improvement over static schemes.
  • Index Construction: Building the initial index for 1,000 documents with a 4,000-keyword dictionary takes roughly 2 seconds.

Conclusion

This paper presents a robust searchable encryption scheme that balances the competing needs of privacy, search accuracy, and system efficiency. By combining a tree-based index with the Vector Space Model, the authors provide a solution that supports multi-keyword ranked searches and dynamic updates, making it a practical choice for secure cloud storage applications. Future work will focus on further reducing index construction overhead and enhancing protection against access pattern leakage.

Summary updated

Abstract

With the development of cloud computing, the sensitive information of outsourced data is at risk of unauthorized accesses. To protect data privacy, the sensitive data should be encrypted by the data owner before outsourcing, which makes the traditional and efficient plaintext keyword search technique useless. Hence, it is an especially important thing to explore secure encrypted cloud data search service. Considering the huge number of outsourced data, there are three problems we are focused on to enable efficient search service: multi-keyword search, result relevance ranking and dynamic update. In this paper, we propose a practically efficient and flexible searchable encrypted scheme which supports both multi-keyword ranked search and dynamic update. To support multi-keyword search and result relevance ranking, we adopt Vector Space Model (VSM) to build the searchable index to achieve accurate search result. To improve search efficiency, we design a tree-based index structure which supports insertion and deletion update well without privacy leakage. We propose a secure search scheme to meet the privacy requirements in the threat model. Finally, experiments on real-world dataset are implemented to demonstrate the overall performance of the proposed scheme, which show our scheme is efficient.
BibTeX
@article{sun2014privacy,
  author = {Xingming Sun and Lu Zhou and Zhangjie Fu and Jin Wang},
  title = {{Privacy-preserving Multi-keyword Ranked Search over Encrypted Cloud Data Supporting Dynamic Update}},
  journal = {International Journal of Security and Its Applications},
  year = {2014},
  doi = {10.14257/ijsia.2014.8.6.01},
}
Figure