Privacy-Preserving Shortest Path Queries on Encrypted Attributed IIoT Graphs

Cryptographic technologies are increasingly utilized to secure private data in outsourcing scenarios. In particular, enabling queries on encrypted attributed graphs with rich information and broad practical applications has garnered wide attention. However, most existing studies primarily address keyword queries within simple graph structures, such as neighbor relationship, severely limiting graph utility. Notably, there has been no prior work that supports shortest path queries - an essential graph algorithm - with attribute constrains on encrypted graphs. In this paper, we introduce SAGES (Static Attributed Graph Searchable Encryption), the first scheme designed to facilitate shortest path queries under specific attribute requirements. SAGES employs symmetric searchable encryption (SSE) to enhance en/de-cryption speeds, and constructs an encrypted structure to enable rapid query execution through efficient index retrieval. In addition, we implement a compression algorithm to minimize server storage overhead. We also formalize leakage functions and provide a rigorous security proof under reasonable leakage assumptions, ensuring that the shortest path structure remains protected against the latest query recovery attacks. Simulated experiments using eight real-world graph datasets demonstrate the effectiveness of our graph compression and the computational efficiency of both setup and query processes. Notably, we achieve an average compression ratio of 79.69%, and query times across all test datasets remain below 700 us.