Efficient and Secure Geometric Range Search Over Encrypted Spatial Data in Mobile Cloud

With the rapid development of mobile computing and the popularity of mobile devices equipped with GPS technology, massive spatial data have become available. Enterprises upload encrypted spatial data to the mobile cloud to save local storage and computation costs. However, the existing secure Geometric Range Search (GRS) solutions are inefficient in terms of building, updating index structure and querying processes. Moreover, the index structures of existing GRS schemes based on Order Preserving Encryption (OPE) leak location order, which may lead to reconstruction attacks. To solve these issues, we first propose an efficient and secure GRS scheme using Radix-Tree, namely GRSRT-I. Specifically, we construct an index structure based on Radix-tree to achieve efficient search and update, then use homomorphic encryption NTRU to resist chosen-plaintext attack, finally design a dual-server architecture to alleviate the burdens on mobile users caused by multiple rounds of interactions. Furthermore, we propose an enhanced scheme, GRSRT-II, by combining Order-Revealing Encryption and OPE, which greatly improves the search efficiency while slightly reducing the security. We formally prove the security of our proposed schemes, and conduct extensive experiments to demonstrate that GRSRT-I can improve the query efficiency by up to at least 1.5 times when compared with previous solutions and GRSRT-II can achieve a higher level of search efficiency.