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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

1 Scopus Citations
View graph of relations

Author(s)

  • Xiangyu Wang
  • Jianfeng Ma
  • Feng Li
  • Ximeng Liu
  • Yinbin Miao
  • And 1 others
  • Robert H. Deng

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)4909-4923
Journal / PublicationIEEE Transactions on Information Forensics and Security
Volume16
Online published8 Oct 2021
Publication statusPublished - 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 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.

Research Area(s)

  • hidden vector encryption, spatio-textual data, Structured encryption

Citation Format(s)

Enabling Efficient Spatial Keyword Queries on Encrypted Data with Strong Security Guarantees. / Wang, Xiangyu; Ma, Jianfeng; Li, Feng; Liu, Ximeng; Miao, Yinbin; Deng, Robert H.

In: IEEE Transactions on Information Forensics and Security, Vol. 16, 2021, p. 4909-4923.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review