Forward-Secure Multi-User Graph Searchable Encryption for Exact Shortest Path Queries

The rapid development of cloud computing and increasing adoption of unstructured data impose higher requirements on cloud servers to deliver advanced query capabilities tailored for protected complex data. To provide outsourced graph privacy and support the shortest path query, a cornerstone of graph computing, various graph searchable encryption (GSE) schemes have been proposed. However, those GSE schemes are only for single-user setting and barely keep forward security, limiting data sharing and value extraction. Therefore, we propose a forward-secure GSE scheme for multi-user querying the exact shortest path. Specifically, our designed encryption structure seamlessly combines the randomizable distributed key-homomorphic pseudorandom function (RDPRF) for multi-user authentication and reduces database update. We then build a dual-server architecture with secure equality test protocol for query. To our knowledge, our GSE scheme is the first to guarantee forward security without a trusted proxy and support multi-user querying the exact shortest path. We formalize leakage functions and model the dynamic multi-user GSE scheme. Formal security proof is offered under reasonable leakage. Finally, we conduct experiments on ten real-world graph datasets with different scales and exemplify the feasibility of our scheme.