Abstract
With the increasing popularity of cloud computing, more and more sensitive or private information has been outsourced onto the cloud server. For protecting data privacy, sensitive data usually has to be encrypted before outsourcing, which makes traditional search techniques based on plaintext useless. In response to the search over encrypted data, searchable encryption is a good solution in Information Security. However, most of existing searchable encryption schemes only support exact keyword search. That means they don't support searching for different variants of the query word, which is a significant drawback and greatly affects data usability and user experience. Recently, a fuzzy keyword search scheme proposed by some researchers aims at addressing the problems of minor typos and format inconsistence but couldn't solve the problem above. In this paper, we formalize the problem of semantic keyword-based search over encrypted cloud data while preserving privacy. Semantic keyword-based search will greatly improves the user experience by returning all the documents containing semantically close keywords related to the query word. In our solution, we use the stemming algorithm to construct stem set, which reduces the dimension of index. And the symbol-based trie is also adopted in index construction to improve the search efficiency. Through rigorous privacy analysis and experiment on real dataset, our scheme is secure and efficient.
Introduction
As organizations and individuals increasingly migrate sensitive data to cloud environments, encryption has become a standard practice to ensure data confidentiality. However, encrypting data renders it "opaque" to traditional search engines, which typically rely on plaintext indexing. While Searchable Encryption (SE) has emerged as a solution, most existing schemes are limited to exact keyword matching.
This limitation significantly hinders usability. For instance, a search for the term "walk" would fail to retrieve documents containing "walking" or "walked," despite their clear semantic relationship. While "fuzzy search" techniques have been proposed to handle typographical errors, they do not address these morphological variations. This paper proposes a novel SE scheme that enables semantic keyword-based search—specifically targeting word variants—without compromising the privacy of the data or the search queries against an "honest-but-curious" cloud provider.
System Architecture and Methodology
The proposed system involves three primary entities: the Data Owner, the Cloud Server, and the Data User. The Data Owner encrypts documents and builds a searchable index before outsourcing them to the cloud. The Data User generates secure "trapdoors" to search for specific terms, and the Cloud Server performs the search and returns relevant encrypted documents.
To achieve efficient semantic search, the methodology utilizes two core components:
1. Stemming Algorithm
The system employs the Porter Stemming Algorithm to reduce keywords to their base root forms, or "stems." For example, the words "services," "servicing," and "service" are all reduced to the stem "servic." By applying this algorithm during both index construction and query generation, the system can match different morphological variants of a word to a single index entry. This approach not only enables semantic matching but also significantly reduces the dimensionality of the keyword set.
2. Symbol-based Trie Index
Rather than using a flat list or a standard hash table, the searchable index is structured as a Symbol-based Trie (prefix tree). In this structure, each node represents a symbol from a predefined alphabet. A path from the root to a leaf node represents a specific hashed stem.
This trie structure offers several advantages:
- Search Efficiency: The cloud server can navigate the tree based on the symbols in the user's trapdoor. If a symbol mismatch occurs early in the path, the search can be terminated immediately, making the process highly efficient for non-existent terms.
- Privacy Preservation: To prevent the server from inferring word lengths or frequencies from the tree's shape, dummy nodes are added to create a "full" tree, and nodes contain meaningless symbols rather than plaintext characters.
Experimental Evaluation
The scheme was evaluated using the Enron Dataset, a collection of real-world emails. The researchers randomly selected 10,000 documents and extracted keywords using the TF-IDF method. This process yielded a keyword set of 20,419 words, which the stemming process successfully reduced to 18,711 distinct stems.
Key Performance Metrics
- Index Construction: Building the trie index for the entire set of 18,711 stems took approximately 4.6 seconds.
- Query Generation: The time required for a user to generate a secure trapdoor for a single keyword is roughly 2.5 milliseconds.
- Search Throughput: The cloud server is capable of processing approximately 10,000 search requests (trapdoors) per second.
- Scalability: Experimental results showed that both stemming and index construction times scale linearly with the number of keywords and stems, indicating the system's suitability for large-scale cloud deployments.
Conclusion
This paper presents an efficient and secure scheme for semantic keyword search over encrypted cloud data. By integrating the Porter Stemming Algorithm with a symbol-based trie index, the proposed solution provides a flexible search experience that accounts for morphological word variants while maintaining high performance and robust privacy. Future work will explore personalized search capabilities and expanding the system to handle sentence-level natural language queries.
Summary updated