Dynamic Multi-keyword Top-k Ranked Search over Encrypted Cloud Data

Xingming Sun, Xinhui Wang, Zhihua Xia, Zhangjie Fu, Tao LiInternational Journal of Security and Its Applications 2014 · DOI

Abstract

Nowadays, more and more people are motivated to outsource their local data to public cloud servers for great convenience and reduced costs in data management. But in consideration of privacy issues, sensitive data should be encrypted before outsourcing, which obsoletes traditional data utilization like keyword-based document retrieval. In this paper, we present a secure and efficient multi-keyword ranked search scheme over encrypted data, which additionally supports dynamic update operations like deletion and insertion of documents. Specifically, we construct an index tree based on vector space model to provide multi-keyword search, which meanwhile supports flexible update operations. Besides, cosine similarity measure is utilized to support accurate ranking for search result. To improve search efficiency, we further propose a search algorithm based on "Greedy Depth-first Traverse Strategy". Moreover, to protect the search privacy, we propose a secure scheme to meet various privacy requirements in the known ciphertext threat model. Experiments on the real-word dataset show the effectiveness and efficiency of proposed scheme.

Introduction

As organizations increasingly migrate data to cloud environments, encryption has become a fundamental requirement for maintaining privacy. However, standard encryption methods transform data into "opaque" blobs, rendering traditional search functionalities—such as keyword-based retrieval—ineffective.

Existing Searchable Symmetric Encryption (SSE) schemes often struggle with a trade-off between efficiency and functionality. Many support only single-keyword searches or require linear scans of document collections, which do not scale to large datasets. Furthermore, most early multi-keyword ranked search schemes were static; adding or deleting a document often required recomputing and re-uploading the entire index. This paper introduces a Dynamic Multi-keyword Ranked Search (DMRS) scheme designed to provide accurate Top-k ranking and efficient logarithmic search times while supporting seamless document updates.

System Architecture

The DMRS framework involves three main entities: the data owner, the data user, and the semi-trusted cloud server.

System architecture of the DMRS scheme showing the interaction between the data owner, cloud server, and data user.

The data owner encrypts the document collection and builds a searchable index tree before outsourcing them to the cloud. The data user generates encrypted search requests (trapdoors) and receives the top-k ranked results. The cloud server performs the search over the encrypted index without learning the underlying plaintext.

Methodology

Vector Space Model and MKRB Tree

The core of the DMRS scheme is the construction of a Modified Keyword Red-Black (MKRB) Tree. Documents and queries are represented as vectors using the Vector Space Model (VSM) with TF-IDF weighting. In the MKRB tree, leaf nodes represent individual documents, while internal nodes store a vector representing the maximum TF values of their children.

The MKRB tree structure and the Greedy Depth-first Search process, illustrating how branches are pruned during search.

Search and Pruning Strategy

To optimize search efficiency, the authors propose a "Greedy Depth-first Traverse Strategy." Because internal nodes provide a "best-case" score for their subtrees, the algorithm can prune branches if the maximum possible score in that branch is lower than the current Top-k results. This allows for sub-linear (logarithmic) search times as the dataset grows.

Privacy Preservation

To protect search privacy, document and query vectors are encrypted using a secure kNN technique involving random splitting and secret matrix multiplication. This allows the cloud server to calculate cosine similarity (via inner products) between a query and an index node without exposing the actual keyword values or document contents.

Key Results and Discussion

Evaluations using the Request for Comments (RFC) dataset demonstrate the scheme's efficiency. As the number of documents increased from 500 to 5,000, DMRS search time remained nearly flat (logarithmic growth), contrasting with the sharp growth seen in traditional linear search methods. Update performance is also a highlight; deleting a document from a collection of 4,500 files took less than 10 seconds, scaling logarithmically with the dataset size.

While robust in the known ciphertext model, the scheme faces challenges from statistical attacks and access pattern leakage in enhanced threat models. Future work will focus on hardening the system against these advanced threats and further optimizing the search algorithm for higher-dimensional keyword sets.

Conclusion

The DMRS scheme successfully bridges the gap between privacy and utility in cloud storage. By combining a tree-based index with secure kNN encryption, it provides a scalable, dynamic, and accurate multi-keyword search solution that meets the demands of modern data management.

Summary updated

Abstract

Nowadays, more and more people are motivated to outsource their local data to public cloud servers for great convenience and reduced costs in data management. But in consideration of privacy issues, sensitive data should be encrypted before outsourcing, which obsoletes traditional data utilization like keyword-based document retrieval. In this paper, we present a secure and efficient multi-keyword ranked search scheme over encrypted data, which additionally supports dynamic update operations like deletion and insertion of documents. Specifically, we construct an index tree based on vector space model to provide multi-keyword search, which meanwhile supports flexible update operations. Besides, cosine similarity measure is utilized to support accurate ranking for search result. To improve search efficiency, we further propose a search algorithm based on "Greedy Depth-first Traverse Strategy". Moreover, to protect the search privacy, we propose a secure scheme to meet various privacy requirements in the known ciphertext threat model. Experiments on the real-word dataset show the effectiveness and efficiency of proposed scheme.
BibTeX
@article{sun2014dynamic,
  author = {Xingming Sun and Xinhui Wang and Zhihua Xia and Zhangjie Fu and Tao Li},
  title = {{Dynamic Multi-keyword Top-k Ranked Search over Encrypted Cloud Data}},
  journal = {International Journal of Security and Its Applications},
  year = {2014},
  doi = {10.14257/ijsia.2014.8.1.30},
}
Figure