Secure and Flexible Wildcard Queries

Wildcard Keyword Searchable Encryption (WKSE) enables users to search desired encrypted files with wildcard queries. Previous schemes only enabled single-character wildcard queries or restricted multi-character wildcard queries. Even if the two types of queries are supported by several schemes, they are vulnerable to correlation attacks and composition attacks. In this paper, we propose a WKSE scheme Secure Flexible Wildcard Queries (SFWQ) that supports highly flexible wildcard queries and resists correlation and composition attacks. Specifically, we adopt the interval matching method instead of traditional position matching, so that SFWQ supports a variety of queries, including single-character wildcard queries, multi-character wildcard queries, and mixed wildcard queries that the combination of both single-character and multi-character wildcards within the same query. Moreover, the number and position of wildcards within wildcard keywords are adjustable according to user preference. To resist the correlation attack and composition attack, we leverage key aggregate searchable encryption (KASE) and key exchange protocol to process characters so that even the same characters of the same keyword behave as different ciphertexts. We define a security model for WKSE which catches the correlation attack and composition attack. Our proof validates SFWQ is secure under the security model. Finally, we implement SFWQ and compare it with state-of-the-art schemes. The experimental results demonstrate that our scheme is feasible and efficient.