RASK: Range Spatial Keyword Queries on Massive Encrypted Geo-Textual Data
Zhen Lv, Kaiyu Shang, Hongwei Huo, Ximeng Liu, Yanguo Peng, Xiangyu Wang, Yaorong Tan
Abstract
Spatial keyword queries have attracted much attention over the past decade due to the popularity of location-based services and social networks, which brings great economic benefits. Geo-textual data are encrypted-and-delegated to public clouds for efficient management and utilization while preventing potential data leakage. However, it is still challenging to solve secure <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ra</u> nge <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</u> patial <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</u> eyword queries on encrypted data since existing works are either vulnerable or inefficient. In this paper, a secure hybrid index is built to implement efficient filtering, by embedding nodes’ paths in a novel symmetrical kd-tree into inverted indexes and employing only lightweight cryptographic techniques. A concrete scheme RASK is constructed on the secure index by utilizing only a little storage and computing resources of clients. Furthermore, RASK+ is proposed based on secure virtual technology by migrating all storage burdens from clients to public clouds. Both schemes are theoretically proved to be <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">indistinguishable under adaptive chosen keyword attacks</i> (IND-CKA2). Through experimental evaluations on three real datasets within consistent environments, both schemes reduce the response time by about 50%-80% compared to state-of-the-art solutions (i.e., SKSE, LSKQ, etc.). The storage overheads for the cloud are also reduced by about 0.5-2 orders of magnitude.