GridSE: Towards Practical Secure Geographic Search via Prefix Symmetric Searchable Encryption (Full Version)

The proliferation of location-based services and applications has brought significant attention to data and location privacy. While general secure computation and privacy-enhancing techniques can partially address this problem, one outstanding challenge is to provide near latency-free search and compatibility with mainstream geographic search techniques, especially the Discrete Global Grid Systems (DGGS). This paper proposes a new construction, namely GridSE, for efficient and DGGS-compatible Secure Geographic Search (SGS) with both backward and forward privacy. We first formulate the notion of a semantic-secure primitive called $\mathit{\text{symmetric}}\mathit{\text{prefix}}\mathit{\text{predicate}}\mathit{\text{encryption}}$ (SP${}^2$E), for predicting whether or not a keyword contains a given prefix, and provide a construction. Then we extend SP${}^2$E for dynamic $\mathit{\text{prefix}}\mathit{\text{symmetric}}\mathit{\text{searchable}}\mathit{\text{encryption}}$ (pSSE), namely GridSE, which supports both backward and forward privacy. GridSE only uses lightweight primitives including cryptographic hash and XOR operations and is extremely efficient. Furthermore, we provide a generic pSSE framework that enables prefix search for traditional dynamic SSE that supports only full keyword search. Experimental results over real-world geographic databases of sizes (by the number of entries) from ${10}^3$ to ${10}^7$ and mainstream DGGS techniques show that GridSE achieves a speedup of $150\times$ - $5000\times$ on search latency and a saving of $99\mathrm{\%}$ on communication overhead as compared to the state-of-the-art. Interestingly, even compared to plaintext search, GridSE introduces only $1.4\times$ extra computational cost and $0.9\times$ additional communication cost. Source code of our scheme is available at https://github.com/rykieguo1771/GridSE-RAM.