GridSE: Towards Practical Secure Geographic Search via Prefix Symmetric Searchable Encryption

[sahrk]

GridSE: Towards Practical Secure Geographic Search via Prefix Symmetric Searchable Encryption
Ruoyang Guo
Stevens Institute of Technology
Jiarui Li
Stevens Institute of Technology
Shucheng Yu
Stevens Institute of Technology
Abstract
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 outstand- ing challenge is to provide near latency-free search and com- patibility with mainstream geographic search techniques, es- pecially the Discrete Global Grid Systems (DGGS). This paper proposes a new construction, namely GridSE, for ef- ficient and DGGS-compatible Secure Geographic Search (SGS) with both backward and forward privacy. We first formulate the notion of a semantic-secure primitive called symmetric prefix predicate encryption (SP2E), for predicting whether or not a keyword contains a given prefix, and pro- vide a construction. Then we extend SP2E for dynamic pre- fix symmetric searchable 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. Fur- thermore, we provide a generic pSSE framework that en- ables prefix search for traditional dynamic SSE that sup- ports only full keyword search. Experimental results over real-world geographic databases of sizes (by the number of entries) from 103 to 107 and mainstream DGGS techniques show that GridSE achieves a speedup of 150× - 5000× on search latency and a saving of 99% on communication overhead as compared to the state-of-the-art. Interestingly, even compared to plaintext search, GridSE introduces only 1.4× extra computational cost and 0.9× additional commu- nication cost. Source code of our scheme is available at https://github.com/rykieguo1771/GridSE-RAM.
2408.07916v1.pdf