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