FETCH: A cloud-native searchable encryption scheme enabling efficient pattern search on encrypted data within cloud services

Searchable encryption (SE) is considered important as it provides both confidentiality and searchability for the data stored in semi-trusted environments such as cloud. However, it is rarely deployed because most SE schemes are not native to cloud services as they require database modifications. In this paper, we present an SE scheme called Frequency-Eliminated Trapdoor-Character Hopping (FETCH) that, based on novel common-conditioned-subsequence-preserving (CCSP) techniques, is able to work natively with off-the-shelf databases and supports wildcard-based pattern search on encrypted data thereof. In fact, with the CCSP techniques, we transform the problem of wildcard SE searching into a problem of subsequence searching, which is solved fast in most databases and thus fits well with cloud services in general. Although in our security analysis, CCSP removes the possibility of obtaining theoretical indistinguishability between indexed items, we show that FETCH does provide adequate confidentiality protection and fares much better than other existing wildcard SE schemes in terms of query performance, storage overhead, and deployment complexity. In particular, FETCH is able to efficiently handle data sets whose size is multiple orders of magnitude larger than those that existing schemes can comfortably support.