Wildcard Keyword Searchable Encryption (WKSE) has grown into a ubiquitous tool. It enables clients to search desired files with wildcard expressions. Although promising, previous schemes confront three barriers: (1) An adversary can launch a correlation attack to acquire the similarity between keywords. (2) The WKSE schemes exhibit false positives which can lead to wrong search results. (3) Existing feature extraction strategies limit the flexibility of search expressions. In this paper, we propose a Multi-Character Searchable Encryption scheme (MCSE) that overcomes the aforementioned barriers. To resist correlation attacks, we design the randomize pad model to encrypt the vector. To eradicate false positives, we apply the vector space model and complete feature extraction strategies so that a feature set uniquely identifies a keyword or expression. To enhance search flexibility, we introduce three distinct feature extraction strategies for keyword expressions, wildcard expressions, and logical expressions, enabling effective multi-character search. These strategies enable indexes to accom modate the search of diverse expressions. Finally, we prove that MCSE is indistinguishable against chosen-feature attacks and implement MCSE on two real datasets. Compared with state-of the-art schemes, the experiment results show that MCSE achieves good performance.

Edit distance, also known as Levenshtein distance, is a very useful tool to measure the similarity between two strings. It has been widely used in many applications such as natural language processing and bioinformatics. In this paper, we introduce a new type of fuzzy public key encryption called Edit Distance-based Encryption (EDE). In EDE, the encryptor can specify an alphabet string and a threshold when encrypting a message, and a decryptor can obtain a decryption key generated from another alphabet string, and the decryption will be successful if and only if the edit distance between the two strings is within the pre-defined threshold. We provide a formal definition and security model for EDE, and propose an EDE scheme that can securely evaluate the edit distance between two strings embedded in the ciphertext and the secret key. We also show an interesting application of our EDE scheme named Fuzzy Broadcast Encryption which is very useful in a broadcasting network.