Title: Spatial Dynamic Searchable Encryption with Forward Security
Authors: Xiangyu Wang, Jianfeng Ma, Ximeng Liu, Yinbin Miao and Dan Zhu
Abstract: Nowadays, spatial search services bring unprecedented convenience in people's daily life (e.g., location-based services, social networking) and are becoming more and more popular. To protect the privacy of outsourcing data, several schemes have been proposed to achieve secure search over encrypted spatial databases. However, most existing schemes cannot support dynamic updates, which seriously hinders the practical application of spatial databases. To address this issue, in this paper, we propose two novel Spatial Dynamic Searchable Encryption (SDSE) constructions for outsourcing spatial databases, which achieve various security guarantees. First, we present a basic construction supporting dynamic update with sub-linear search complexity based on the order-revealing encryption and Quadtree. Then, to ensure that updates do not reveal any information underlying the prior modifications beyond some explicit leakage (i.e., forward security), we further give an improved construction according to constrained pseudo-random functions. Both the nearest neighbor search and geometric search are supported in our constructions, which meet almost all spatial search needs. The experiments using real-world dataset demonstrate that our constructions are efficient and feasible in practice.
