Enabling Efficient Spatial Keyword Queries on Encrypted Data with Strong Security Guarantees

Structured Encryption (STE), which allows a server to provide secure search services on encrypted data structures, has been widely investigated in recent years. To meet expressive search requirements in practical applications, a large number of STE constructions have been proposed either on textual keywords or spatial data. However, STE on spatio-textual data, which are widely used in location-based services, has not been fully investigated. In this paper, we formally define the notion of Spatial Keyword Structured Encryption (SKSE) and propose several concrete SKSE constructions with various efficiency-security trade-offs. Firstly, we propose a basic construction with linear search complexity, which only leaks the private files matching both spatial range query and all query keywords. Then, to improve the search efficiency on large-scale datasets, we present a novel tree-based construction with sub-linear search complexity. Finally, we introduce a post-validation approach to remove false positives and further improve storage and search performance. Our constructions are general in the sense that they can be constructed from any hidden vector encryption schemes, including public-key setting and symmetric-key setting, which can meet different sharing requirements. Our rigorous security analysis and comprehensive performance evaluation demonstrate that the proposed constructions are secure and outperform the start-of-the-art solutions.