Efficient Wildcard Searchable Symmetric Encryption with Forward and Backward Security

Wildcard Searchable Symmetric Encryption can achieve flexibility and pattern matching while protecting data privacy. There is a promising future for combining secure wildcard search with emerging technologies such as AI. However, there are challenges in reducing the communication cost and improving security. In this paper, we propose an efficient wildcard searchable symmetric encryption with forward and backward security. The complexity of communication costs in the search protocol is O(1), independent of the number of characters of wildcard keywords, or files in the search result. It is achieved by a double-compressed index in which the character set and file identifiers are encoded simultaneously. Then, the double-compressed index provides a possibility to achieve oblivious keyword query and update, so that the proposed scheme only reveals the query type (search or update) without anything else. It achieves forward and backward security using the distributed multi-point function and an additively homomorphic symmetric encryption scheme. Detailed security proof and the theoretical comparison show the improvement in security and efficiency. The acceptable overheads of the proposed scheme are presented by the extensive performance evaluation.