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.
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.
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