ParallelGSE: Efficient and Secure Shortest Path Search on Encrypted Graphs

Graph searchable encryption (GSE) for shortest path queries allows users to discover the closest connection between two individuals in encrypted social network graphs, while safeguarding both social data security and the privacy of user queries. The static GSE is commonly favored for its higher efficiency, while it faces significant challenges in resisting query recovery attacks. In contrast, the dynamic GSE is better suited for changing real world, but enhancing its search efficiency remains a formidable challenge. In this paper, we propose the ParallelGSE, a flexible graph partitioning and parallel search framework that supports both dynamic and static encrypted social graphs, striking a balance between query privacy and practical implementation. ParallelGSE partitions the original graph into multiple subgraphs, distributes them across several semi-honest servers, and performs searches in parallel without relying on a trusted server. Formal security reduction demonstrates ParallelGSE is resistant to isomorphic query recovery attacks. Simulated experiments on seven real-world graph datasets validate rationality of graph partition and improvements of storage, computation and communication costs. Especially, compared to the state-of-the-art (SOTA) static PathGES (ACM CCS 2024) and dynamic GraphShield (IEEE TKDE 2022), the search efficiency of static ParallelGSE can be 3 orders of magnitude faster than that of PathGSE, while dynamic ParallelGSE achieves over $20\times$ greater search efficiency than GraphShield.