Publication Type
Journal Article
Version
acceptedVersion
Publication Date
1-2021
Abstract
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 efficiencysecurity 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.
Keywords
structured encryption, spatio-textual data, hidden vector encryption
Discipline
Databases and Information Systems | Information Security
Research Areas
Cybersecurity
Areas of Excellence
Digital transformation
Publication
IEEE Transactions on Information Forensics and Security
Volume
16
First Page
4909
Last Page
4923
ISSN
1556-6013
Identifier
10.1109/TIFS.2021.3118880
Publisher
Institute of Electrical and Electronics Engineers
Citation
WANG, Xiangyu; MA, Jianfeng; LI, Feng; LIU, Ximeng; MIAO, Yinbin; and DENG, Robert H..
Enabling efficient spatial keyword queries on encrypted data with strong security guarantees. (2021). IEEE Transactions on Information Forensics and Security. 16, 4909-4923.
Available at: https://ink.library.smu.edu.sg/sis_research/10136
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/TIFS.2021.3118880
