Structural Leakage in Graph Encryption: Attacks and Defenses

Structural Leakage in Graph Encryption: Attacks and Defenses Hua Shen1 (nancy78733@126.com) Renzhi Chen1 (13914373958@163.com) Ge Wu2 (gewu@seu.edu.cn) Willy Susilo3 (wsusilo@uow.edu.au) Jing Chen4 (chenjing@whu.edu.cn) Mingwu Zhang1 (csmwzhang@gmail.com) 1 Hubei University of Technology 2 Southeast University 3 University of Wollongong 4 Wuhan University

arXiv:2608.13981v1 [cs.CR] 14 Aug 2026

Abstract Graph encryption schemes (GES) enable secure outsourcing of graph data while supporting efficient queries. This report provides a comprehensive analysis of structural leakage in GES for single-pair shortest path (SPSP) queries, integrating findings from two recent works. First, we analyze PathGES, a scheme designed to resist query recovery attacks through heavy-light decomposition (HLD) and canonical fragment encoding. Our analysis reveals that PathGES suffers from significant imbalances in HLD decomposition, with over 99% of token-path mappings being one-toone on real-world datasets, enabling both the Falzon-Paterson attack and side-channel inference of path lengths. Second, we present Fragment Tree attack that exploits these structural weaknesses to recover query contents, achieving up to 10.24% exact recovery on sparse graphs. Third, we introduce BlindGES, an enhanced scheme incorporating a Merge-and-Divide mechanism and two-level multimap index that reduces one-to-one mappings to below 20%, cuts setup time by 50%, reduces storage overhead by 32%, and limits path length leakage to under 1%. This report systematically presents attack methodologies, defense mechanisms, security proofs, and experimental evaluations on seven real-world datasets.

Keywords: Graph Encryption, Structure Leakage, Shortest Path Query, Query Recovery Attack, Heavy-Light Decomposition

1

Contents 1 Introduction 1.1 Backgroud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Evolution of Graph Encryption Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Contributions of This Report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Report Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 4 4 4 5

2 Preliminaries 2.1 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Graph Encryption Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Multimap Encryption Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Tree Isomorphism and Canonical Names . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 6 6 7

3 GKT Scheme Review and Falzon-Paterson Attack 3.1 GKT Scheme Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Core Vulnerability of GKT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Falzon-Paterson Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Precomputation (Attack Preparation) . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Query Observation and Query Tree Construction . . . . . . . . . . . . . . . . . . . 3.3.3 Building Mapping Dictionary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.4 Query Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 7 7 8 8 8 8 8

4 In-depth Analysis of PathGES 4.1 Overview of PathGES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Overall Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 HLD-based Path Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.3 Canonical Segment Encoding and Label Assignment . . . . . . . . . . . . . . . . . 4.1.4 Two-Level Index Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.5 Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.6 Defense Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Structural Leakage Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 HLD Imbalance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Side-Channel Leakage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Subpath Structure Leakage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 9 10 10 11 11 12 12 13 13 13 13 14

5 Our Attack: Fragment Tree Attack Methodology 5.1 Threat Model and Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Overview of Attack Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Fragment Tree Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Definition of Fragment Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Fragment Tree Construction Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Query Tree Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Background: Query Tree Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.2 Token Sorting via Bucket-Based Method . . . . . . . . . . . . . . . . . . . . . . . . 5.4.3 Query Tree Generation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Isomorphism Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5.2 Core Lemmas and Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5.3 PathName-Based Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Attack Effectiveness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6.1 Graph Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6.2 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14 14 14 15 15 15 15 15 16 17 18 18 19 19 20 20 21

2

6 BlindGES Defense Scheme 6.1 Design Goals and Workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Merge-and-Divide Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Two-Level Index Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5.1 Leakage Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5.2 Security Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5.3 Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Empirical Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6.1 Performance Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6.2 Security Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23 23 23 23 28 29 29 29 30 30 31 31

7 Limitations and Future Work

33

8 Conclusion

35

3

1

Introduction

1.1

Backgroud

Graphs can intuitively represent relationships among multiple entities and are widely used in social networks [17, 12, 28], geographic information systems (GIS) [30, 34], financial transactions [9], and communication networks [11, 18]. The rapid growth of graph scale has driven enterprises and users to increasingly outsource graph datasets to cloud servers [20, 27]. However, graph outsourcing, while operationally advantageous, introduces privacy vulnerabilities. Attacks on compromised infrastructure or untrusted server behaviors could lead to unauthorized disclosure of clients’ sensitive information, such as social connectivity patterns, geolocation trajectories, and financial transaction histories. To address this issue, graphs are typically encrypted before being outsourced to cloud servers [7, 25, 24]. Graph Encryption scheme (GES) is a specialized form of structured encryption (STE) [15, 21, 10, 7, 4]. STE [3] can realize efficient and private server-side queries and belongs to searchable symmetric encryption (SSE) [19]. GES first needs to design a specific structure (such as SP-matrix [7], 2-hop labeling [14], bi-directional index [13], Multimap chaining [3, 19, 4]) to redescribe a graph or to represent the calculation results of a graph. Then, GES encrypts the structure while enabling efficient queries on the encrypted structure. The queries include adjacency relationship queries [33, 23], graph pattern matching queries [32, 1], subgraph matching queries [26, 8, 35], shortest distance queries [15, 21], and shortest path queries [31, 24, 7, 4]. Shortest path queries are fundamental in areas such as navigation, logistics, and network optimization.

1.2

Evolution of Graph Encryption Schemes

In 2021, Ghosh, Kamara, and Tamara [7] introduced the first graph encryption scheme (GES) supporting single-destination shortest path (SDSP) queries. Their approach constructs a dictionary (SPDX) representing the shortest-path matrix of a graph. A critical limitation is the strict one-to-one mapping between tokens and paths. In 2022, Falzon and Paterson [5] exploited this mapping to recover client queries, demonstrating that an adversary with knowledge of the plaintext graph and access to query leakage information can recover the queried node pairs. In response, in 2024, Falzon et al. Falzon et al. [4] proposed PathGES, which associates each token with a canonical segment—a path segment whose length is a power of two. For exponents ≥ 2, one token may correspond to multiple paths, thereby reducing the risk of query recovery. The concept of query recovery was first introduced in [16], with the core goal of recovering the plaintext queries issued by the client through the exploitation of leakage information generated during the query process. However, our analysis reveals that PathGES suffers from significant imbalances in the number of heavy and light edges in its HLD decomposition, as well as structural flaws in its token-path mapping architecture. These weaknesses result in a substantial number of one-to-one mappings, making it ineffective against the Falzon-Paterson attack and vulnerable to shortest path length leakage.

1.3

Contributions of This Report

This report integrates two complementary works: BreakingGES (attack) exposes critical vulnerabilities in PathGES and develops an attack to exploit them; BlindGES (defense) proposes a defense scheme to address these vulnerabilities. Fragment Tree Attack (BreakingGES): • In-depth analysis of PathGES design, revealing that over 99% of token-path mappings remain one-to-one on real-world datasets • Introduction of Fragment Tree structure for managing path fragments and capturing leakage information • Development of query tree generation algorithm that captures logical relationships between tokens • Rigorous proof of isomorphism between fragment trees and query trees • Experimental validation on seven datasets demonstrating effective query recovery, with up to 10.24% of queries exactly recovered and an additional 10% narrowed to 2-5 candidates

4

BlindGES Defense (BlindGES): • Discovery that at least 84% of shortest path lengths can be inferred via side-channel attacks on PathGES • Proposal of Merge-and-Divide mechanism to address the mismatch between HLD (a classic tree decomposition algorithm) and its canonical segment encoding, which together cause over 99% oneto-one token-path mappings on real-world graphs • Design of novel two-level multimap index structure for secure shortest path queries • Experimental demonstration showing that, compared to PathGES, BlindGES reduces one-to-one mappings from over 99% to below 20%, limits path length leakage to under 1%, and cuts setup time by 50% and storage overhead by 32%

1.4

Report Organization

Section 2 presents preliminaries. Section 3 reviews GKT and the Falzon-Paterson attack. Section 4 provides in-depth analysis of PathGES. Section 5 presents the Fragment Tree attack methodology. Section 6 introduces BlindGES defense scheme. Section 7 presents experimental evaluations. Section 8 discusses findings. Section 9 concludes.

2

Preliminaries

We use [n] to denote {1, 2, · · · , n}, p1 ∥ p2 to represent the concatenation of path fragments p1 and p2 , and λ to denote the security parameter.

2.1

Data Structures

Graph. A graph G = (V , E) consists of a non-empty finite vertex set V and a finite edge set E. |V | indicates the number of vertices in G, and |E| represents the number of edges. Single-Destination Shortest Path Tree (SDSP-Tree) [6]. For a given graph G, an SDSP-tree records the information of the shortest paths from the other vertices in the graph to the root vertex (the destination). After using a shortest path algorithm (such as the Floyd-Warshall [29] algorithm or Dijkstra’s algorithm) to find out the shortest paths between all pairs of vertices, we can generate |V | SDSP-trees of G. For any r ∈ V , we use Tr to represent the SDSP-tree rooted at r. Heavy-Light Decomposition (HLD) [22]. Heavy-light decomposition is a method for decomposing a tree into disjoint subpaths using heavy and light edges in a breadth-first search (BFS) manner. Given a rooted tree Tr , the size sizeTr (v) of a node v is the number of nodes in the subtree rooted at the node v. We use parent(v) to denote the parent node of v. If sizeTr (v) > 12 sizeTr (parent(v)), the edge (v, parent(v)) is a heavy edge, otherwise it is a light edge. For any node in Tr , there is at most one heavy edge among the edges connecting it with its children. The input of HLD algorithm is a rooted tree Tr and its output is a disjoint path set P setr . Fig. 3 illustrates the processing procedure of this algorithm through an example. Multimap. A multimap M is a data structure that is an extension of a dictionary. A traditional dictionary maps each label to a single value; the relationship between label and value is one-to-one. A multimap maps each label lab to a set of values valSet; the relationship between label and value is one-to-many. Each label is unique. The multimap structure supports an insert operation that adds a pair (lab, valSet) into M and a visit operation that, given a label lab, returns the associated valSet. If M does not hold the search label lab, M [lab] returns ⊥. We denote by |M | the size of M (the number of (lab, valSet) pairs) and by |M [lab]| the size of valSet. Query Tree. The query tree Q = (T K, E ′ ) is a tree constructed by the server after collecting all leaked tokens. T K is the set of all leaked tokens in the queries, with each token corresponding to a node of the query tree. The edges of E ′ represent the connection relationships between tokens. Suppose there exists two mappings tk1 7→ p1 and tk2 7→ p2 , where p1 and p2 are two paths. If these two paths can be linked into a longer path, (i.e., p1 ∥ p2 ), then there exists a directed edge (tk1 , tk2 ) ∈ E ′ in the query tree to represent this relationship.

5

GES λ λ Figure 1: Games RealGES A (1 ) and IdealA,Sim (1 )

2.2

Graph Encryption Scheme

A graph encryption scheme (GES) includes five algorithms [4]: • GES.KeyGen: Its input is a security parameter λ, and its output is a secret key K. • GES.Encrypt: Its inputs include K and a graph G; its output is an encrypted database ED. • GES.Token: It takes K and a query q and returns the corresponding token tk. • GES.Search: It uses tk to search ED and returns a response resp. • GES.Reveal: It takes resp and K and outputs the plaintext of the query result. Except for GES.Search, the client executes all the other algorithms, and the server performs the algorithm GES.Search. GESs realize queries on ED in sublinear time by leaking some information. Describe the information leaked during constructing ED by defining the leakage function LS , and characterize the information revealed during retrieving ED with the leakage function LQ . In other words, LS and LQ define the maximum amount of information that GESs can allow to be leaked. Like [4], we define and prove the security of BlindGES using the real-ideal paradigm concerning a server that learns the outputs of LS and LQ , knows (or even chooses) the graph G, and tries to infer the plaintext queries. Definition 1 (Adaptive (LS , LQ )-secure GES [3, 7, 4]). Let GES be a graph encryption scheme, LS and LQ be leakage algorithms. We say that GES is (LS , LQ )-secure against adaptive chosen-query attacks if for any PPT adversary A and for all λ ≥ 1, there exists a PPT S and a negligible function negl(λ) such that GES λ λ |P r[RealGES A (1 ) = 1] − P r[IdealA,Sim (1 ) = 1]| ≤ negl(λ). GES λ λ and the definitions of games RealGES A (1 ) and IdealA,Sim (1 ) are shown in Figure 1.

2.3

Multimap Encryption Scheme

Multimap encryption schemes fall into response-hiding encryption (EMM-RH) and response-revealed encryption (EMM-RR). An EMM-RH scheme is a tuple of five algorithms EMM-RH = (KeyGen, Encrypt, Token, Get, Reveal), and an EMM-RR is a tuple of four algorithms EMM-RR = (KeyGen, Encrypt, Token, Get): • EMM-RH.KeyGen: It takes as input a security parameter λ and outputs a secret key K. • EMM-RH.Encrypt: It takes as input a key K and a multi-mapping M and outputs an encrypted multimap EM . • EMM-RH.Token: It takes as input a key K and a label lab and outputs a token tk. • EMM-RH.Get: It takes as input a token tk and an encrypted multimap EM . It outputs a response resp. 6

• EMM-RH.Reveal: It takes as input a response resp and outputs a set of plaint values V alSet. Within the five algorithmic tuples described above, only the EMM-RH.Get algorithm is executed by the server, whereas all remaining algorithms are executed by the client. In contrast to the EMM-RH algorithm suite, the EMM-RR suite omits the reveal algorithm because EMM-RR.Get directly returns V alSet. Therefore, the EMM-RR algorithm suite directly exposes the query results to the server. M −RR M −RR M −RH Like [4], we assume EMM-RR to be (LEM , LEM )-secure and EMM-RH to be (LEM , S Q S P |M | EM M −RH EM M −RR EM M −RH LQ )-secure. The setup leakages LS (M ) and LS (M ) are |M | and i=1 |V alSeti |. M −RR EM M −RR EM M −RR The query leakage LEM (M , lab , · · · , lab ) is (QP , AP ), and the query leakage 1 k Q EM M −RH EM M −RH EM M −RH EM M −RR LQ (M , lab1 , · · · , labk ) is (QP , V ol ). QP (M , lab1 , · · · , labk ) and QP EM M −RH (M , lab1 , · · · , labk ) are the query pattern that reveals whether two queries are equal. The pattern is a k × k matrix of bits. If labi = labj , a 1 is set at location (i, j) of the matrix. AP EM M −RR (M , lab1 , · · · , labk ) = {M [lab1 ], · · · , M [labk ]} is the access pattern that reveals the individual values returned Pk for each query. V olEM M −RH (M , lab1 , · · · , labk ) = i=1 |M [labi ]| is the volume pattern that reveals the number of the values returned for each query.

2.4

Tree Isomorphism and Canonical Names

Graph Isomorphism Let G1 = (V1 , E1 ) and G2 = (V2 , E2 ) be two graphs. If there exists a bijection ϕ: V1 → V2 such that for any u, v ∈ V1 , we have ϕ(u), ϕ(v) ∈ V1 , and if (u, v) ∈ E1 , we have (u, v) ∈ E1 ⇐⇒ (ϕ(u), ϕ(v)) ∈ E2 , then G1 and G2 are isomorphic, denoted G1 ∼ = G2 . In this case, ϕ is called an isomorphism between the two graphs. Let Tr1 = (Vr1 , Er1 ) and Tr2 = (Vr2 , Er2 ) be rooted trees. An isomorphism between Tr1 and Tr2 is a graph isomorphism φ: Vr1 → Vr2 such that φ(r1 ) = r2 . Canonical Name. The Falzon–Paterson attack uses canonical names to encode each node in a tree, reflecting the structure of its subtree. Canonical names are built recursively in a bottom-up manner: the canonical name of a leaf node is designated as the fixed string "10". For an internal node, the first step is to sort the canonical names of all its child nodes in ascending order based on their length. These sorted names are then concatenated with the delimiters "1" and "0" added at the beginning and end, respectively. The formal method for calculating a canonical name is Name(v) = "1 || children names || 0". This naming method depends solely on the subtree structure, ensuring that structurally identical subtrees yield identical canonical names. PathName. In a rooted tree Tr with r as the root, a path name associated with a node v (denoted as P athN ame(v)) encodes the path structure from v to the root node r. To construct it, we first calculate the canonical name of each node. Then, we perform a depth-first traversal from the root node, using a stack to determine the path names for all nodes. For the root r, PathName(r) = h(Name(r)); for a nonroot node v, suppose its parent is u, PathName(v) = h(Name(v) || PathName(u)). Here, h(·) denotes a hash function (e.g., truncated SHA-256) used to compress the length of the path name to O(log n). This construction ensures that PathName(v) encodes both a local structure of Tr and the information of the path from v to r. Therefore, such path names are suitable for structural matching and encrypted query recovery tasks.

3

GKT Scheme Review and Falzon-Paterson Attack

3.1

GKT Scheme Overview

In 2021, Ghosh, Kamara, and Tamara [7] introduced the first graph encryption scheme (GES) supporting single-destination shortest path (SDSP) queries. Their approach constructs a dictionary (SPDX) representing the shortest-path matrix (SP-matrix) of a graph, where each entry SPDX[(u, v)] = (w, v) indicates that the next hop from u to v is w. To enable recursive traversal on encrypted data, the structure is modified to SPDX′ , where each value becomes a tuple (tk(w,v) , ct(w,v) ) containing a token and a ciphertext. A distinctive feature of GKT is that the encrypted structure enjoys the same asymptotic setup time, query time, and space as the plaintext SP matrix.

3.2

Core Vulnerability of GKT

A critical limitation is the strict one-to-one mapping between tokens and paths. Suppose the query request is (u, v), and the shortest path from u to v is (u, w0 , w1 , w2 , w3 , v). The client sends the 7

token tk(u,v) corresponding to (u, v) to the server. The server retrieves the encrypted SP-matrix and will successively obtain tk(w0 ,v) , tk(w1 ,v) , tk(w2 ,v) , tk(w3 ,v) , and tk(v,v) . As a result, the server can observe all the tokens involved in a query process as well as the relationships between these tokens.

3.3

Falzon-Paterson Attack

Falzon and Paterson [5] developed a query recovery attack that exploits the one-to-one mapping between tokens and paths in GKT. The attack consists of four phases: precomputation, query observation and query tree construction, mapping dictionary building, and query recovery. 3.3.1

Precomputation (Attack Preparation)

Before observing any client queries, the server precomputes necessary information based on the plaintext graph G: • Build SDSP trees: For each vertex r ∈ V , construct the SDSP tree Tr rooted at r, representing the shortest paths from all other vertices to r. • Compute PathNames: For each node in every SDSP tree Tr , calculate its PathName. As defined in Section 2.4, PathName encodes the path structure from the node to the root, computed recursively using canonical names. • Construct mapping table M : Build a mapping table M indexed by PathNames. For each node u in Tr with PathName pn, the entry M [pn] stores the candidate query pair (u, r). Queries corresponding to nodes with the same PathName are grouped together in the same row of M . This precomputation is performed once before any attack execution. 3.3.2

Query Observation and Query Tree Construction

After responding to a sufficient number of query requests from the client, the server constructs a query tree that represents the query structure observed during the query process. For a fixed destination vertex v, the server constructs query tree Qv as follows: • The root of Qv is the token tk(v,v) • If a token tk(w,v) is observed to be followed by tk(v,v) in a query sequence, a directed edge is added from tk(w,v) to the root • Recursively, if tk(u,v) is followed by tk(w,v) , a directed edge is added from tk(u,v) to tk(w,v) 3.3.3

Building Mapping Dictionary

After the query tree is built, the server calculates the path name of each node in the query tree. It records the node value (i.e., the token) and its corresponding PathName in a mapping dictionary D, where the token serves as the key of the dictionary and the PathName as the value (i.e., D : token → PathName). 3.3.4

Query Recovery

The server uses both M (from precomputation) and D (from query observation) to launch the query recovery attack: • For a target query token tk, retrieve its PathName from D : pn = D[tk] • Use this PathName to query the mapping table M , obtaining the set of candidate query pairs: M [pn] • The candidate set contains all possible (u, v) pairs whose corresponding node in the SDSP tree shares the same PathName

8

Fig. 2 illustrates an example of the Falzon-Paterson attack. The strings marked in blue in the figure are the canonical names corresponding to the nodes. When the server receives the query token tk(5,1) , it retrieves D to obtain the corresponding path name h(10||P athN ame(4)). Then, the server retrieves M based on h(10||P athN ame(4)) to get the candidate query (5,1) that matches the query token tk(5,1) . Since there is only one candidate query, the server can determine that the query corresponding to tk(5,1) is this candidate query. When the server receives the query token tk(8,1) , it retrieves D to obtain the corresponding path name h(10||P athN ame(1)). Subsequently, the server retrieves M according to h(10||P athN ame(1)) and finds that the candidate queries matching the query token tk(8,1) are (8, 1) and (7, 1), narrowing the target range to a small candidate set. From the above analysis, it can be found that the Falzon-Paterson attack does not break the underlying encryption primitives; rather, it solely leverages the structural leakage inherent in GKT to recover query pairs or precisely reduce them to a minimal candidate set.

Figure 2: An example of the Falzon-Paterson attack. Attack Effectiveness. According to [5], the Falzon-Paterson attack can directly recover up to 21.9% of query plaintexts in GKT, and for approximately 50% of the queries, the candidate set can be reduced to no more than three options. These results are based on experiments conducted on the p2p-Gnutella08 and p2p-Gnutella04 datasets.

4

In-depth Analysis of PathGES

4.1

Overview of PathGES

PathGES [4] can be viewed as an enhanced version of GKT[7] designed to resist the Falzon-Paterson attack [5]. In GKT, there exists a strict one-to-one mapping between tokens and paths, allowing the server to observe all tokens and their relationships during the query process. The Falzon-Paterson attack exploits this one-to-one mapping to recover query contents. The core problem that PathGES needs to solve is: design a mechanism that breaks the unique binding between tokens and paths while still enabling correct recovery of shortest paths. To achieve this goal, PathGES employs the following core techniques: • Decomposing shortest paths using the Heavy-Light Decomposition (HLD) algorithm • Normalizing path fragments into canonical segments (lengths that are powers of two) 9

• Designing a labeling method for normalized fragments • Constructing a two-level multimap index structure 4.1.1

Overall Architecture

For a given graph G, PathGES first needs to construct the SDSP forest {Tr }r∈V and decomposes each SDSP tree Tr into disjoint paths P Setr using HLD. After that, PathGES encodes each path in P Setr and converts it into a set of canonical segments. Following this, PathGES generates a token for each canonical segment and constructs a two-level index using two multimaps, M1 and M2 : • M2 is used to retrieve canonical segments • M1 is used to retrieve tokens that search M2 PathGES uses the tokens corresponding to SDSP queries to retrieve M1 . Finally, PathGES encrypts M1 and M2 and stores them on the server. 4.1.2

HLD-based Path Decomposition

For relevant definitions of HLD, please refer to Section 2.1. Given a graph G, PathGES first needs to construct an SDSP tree for each vertex in the graph. Suppose the SDSP tree Tv corresponding to vertex Tv is as shown in Fig. 3. Fig. 3 illustrates the process of fragmenting the shortest paths represented by Tv using the HLD algorithm, resulting in a set of path fragments denoted as P Setv . The path fragments in P Setv are mutually disjoint. First, PathGES calculates the size of the subtree for each node in Tv , then distinguishes between heavy edges and light edges within Tv and performs fragmentation processing on the paths to obtain the corresponding set of fragmented paths P Setv . If the currently visited node is connected to its child via a light edge, this light edge is pushed into a queue; if the currently visited node is connected to its child via a heavy edge, the current path fragment continues to grow downward along this heavy edge. Otherwise, the growth stops, and the path fragment is merged into P Setv . At this point, it is determined whether the queue is empty. If it is empty, the fragmentation process ends; otherwise, an edge is removed from the queue, and the above process is repeated with the next node in the edge as the currently visited node.

Figure 3: An example of the HLD algorithm.

10

4.1.3

Canonical Segment Encoding and Label Assignment

After obtaining the disjoint path set P Setv through HLD decomposition, PathGES normalizes each path fragment by padding it with dummy nodes to make its length a power of two. A path fragment whose length is a power of two is called a canonical fragment. Example. suppose (u′ , w4′ , w3′ , w2′ , w1′ , v ′ ) is a disjoint path of Tv , where v ′ is the node among these nodes that is closest to the root v of Tv . In this path fragment, the edge (w1′ , v ′ ) may be a light or heavy edge, and others are heavy. This path is encoded into 4 canonical segments: (w1′ , v), (w2′ , w1′ , v), (w4′ , w3′ , w2′ , w1′ , v), and (p, p, u, w4′ , w3′ , w2′ , w1′ , v), where ‘p’ is a padding node. These segments are stored as the values of the label/value pairs in M2 , and the label determines the storage location. The labels of the four fragments are: (r, u, v, 0), (r, u, v, 1), (r, u, v, 2), (r, u, v, 3), respectively. Their tokens are tk(r,u,v,0) , tk(r,u,v,1) , tk(r,u,v,2) , and tk(r,u,v,3) . One-to-Many Mapping. The key innovation of PathGES is that a token can correspond to multiple paths: • tk(r,u,v,0) corresponds to (w1′ , v) • tk(r,u,v,1) corresponds to (w2′ , w1′ , v) • tk(r,u,v,2) corresponds to two paths: (w3′ , w2′ , w1′ , v) and (w4′ , w3′ , w2′ , w1′ , v) • tk(r,u,v,3) corresponds to (u, w4′ , w3′ , w2′ , w1′ , v) Fig. 4 illustrates the process of normalizing and assigning labels to this path fragment. Generally, the label (r, u, v, j) represents a canonical fragment in the rooted tree with root r, where the fragment has a length of 2j , starts at u, and ends at v. tk(r,u,v,j) can correspond to at most 2j − 2j−1 paths. The relationship between tokens and paths is no longer necessarily one-to-one, which is intended to help PathGES resist the Falzon-Paterson attack.

Figure 4: An example of normalizing and assigning labels.

4.1.4

Two-Level Index Structure

PathGES constructs a two-level index structure consisting of two mapping tables, M1 and M2 : M2 (Second Level). The canonical segments are stored in M2 . The token for retrieving the canonical fragment with the label (r, u, v, j) from M2 is M2 . Note that M2 achieves a one-to-many mapping from tokens corresponding to canonical fragments to paths (see Section 4.1.3). A token tk(r,u,v,j) can correspond to multiple paths. M1 (First Level). For the SDSP query (u, v), PathGES stores the search tokens of the canonical fragments related to the query in the position indicated by (u, v) in M1 . The token for retrieving these related tokens from M1 is tk(u,v) . Note that M1 achieves a one-to-many mapping from SDSP query tokens to tokens corresponding to canonical fragments. A token tk(u,v) can correspond to multiple canonical fragment tokens. Fig. 5 shows an example of the two-level index structure of PathGES. M1 and M2 of Fig. 5 correspond to the example in Fig. 3. To ensure the non-interactive way of queries, PathGES employs a responserevealing multimap encryption (EMM-RR) to encrypt M1 and a response-hiding multimap encryption (EMM-RH) to encrypt M2 . The encrypted M1 and M2 are denoted as EM1 and EM2 , respectively.

11

Figure 5: An example of the two-level index structure of PathGES. 4.1.5

Query Processing

The query processing in PathGES proceeds as follows: • Token Generation. The client generates a token tk(u,v) for the SPSP query (u, v) using the secret key. • Search. The server uses tk(u,v) to retrieve from M1 the set of second-level tokens {tk(r,u,v,j) } associated with the query. • Fragment Retrieval. The server then uses each second-level token to retrieve the corresponding canonical segment from M2 . • Response. The server returns all retrieved canonical segments to the client. • Reveal. The client reconstructs the shortest path by concatenating the canonical segments in the correct order. 4.1.6

Defense Mechanism

PathGES aims to mitigate the structural leakage risks inherent in GKT, where tokens are in one-to-one correspondence with paths. The defense mechanism of PathGES relies on two key insights: • 1. Path Fragmentation. By decomposing shortest paths into smaller fragments using HLD, PathGES ensures that no single token represents an entire path. • 2. Canonical Segment Encoding. By normalizing fragments to powers-of-two lengths, PathGES enables one-to-many mappings between tokens and paths, obscuring the exact path structure from the server. Example of Defense. Consider that the shortest path corresponding to an SDSP query is decomposed via HLD and normalized, yielding two canonical fragments of lengths 1 and 4 (e.g., the SDSP query (w7 , v) in Fig. 5). tk(w7 ,v) corresponds to two canonical fragment tokens tk(r,w7 ,w8 ,0) and tk(r,w8 ,v,2) . A canonical fragment token for j = 2 may correspond to a path of length 3 or a path of length 4, partially obscuring the path structure. The server cannot distinguish whether the original path had 3 edges or 4 edges.

12

4.2

Structural Leakage Problems

4.2.1

HLD Imbalance

Our analysis across six datasets (Table 1) reveals that over 98% of decomposed subpaths have length 1 or 2 (each being a canonical segment itself) and 99% of decomposed subpaths have length 1, 2, and 3 (each also being a canonical segment itself). This implies that in PathGES, at least 99% of tokens map to only one segment. As a result, if a shortest path consists solely of such short segments, its total length is directly exposed. Table 1: Statistics on path fragments lengths Data |V | |E| Density Total Fragments ShortFragment I Percentage ShortFragment II Percentage 1d=

internetRouting 35 323 0.543 1,141 1,141 100% 1,141 100%

Ca-GrQc 46 1,030 0.995 2,069 2,069 100% 2,069 100%

email-EU-core 1,005 16,706 0.02 878,147 875,638 99.71% 877,940 99.98%

facebook-combined 4,309 88,234 0.011 16,281,762 16,276,777 99.97% 16,281,560 99.99%

p2p-Gnutella08 6,301 20,777 0.001 34,619,060 33,997,988 98.21% 34,578,445 99.88%

p2p-Gnutella04 10,876 39,994 0.0006 101,440,282 99664466 98.25% 101,354,239 99.92%

2|E| represents the density of the graph. |V |2 −|V |

2 ShortFragment I refers to these short fragments with lengths of 1 and 2. 3 ShortFragment II refers to these short fragments with lengths of 1, 2, and 3. 4 Percentage indicates the proportion of the short fragments among all fragments.

4.2.2

Side-Channel Leakage

M −RH M −RH PathGES causes additional information leakage during the process of using a (LEM , LEM )S Q EM M −RH secure EMM-RH scheme, where LQ = (QP EM M −RH , V olEM M −RH ), V olEM M −RH (M2 , lab) = |M2 [lab]|. The value of M2 [lab] is the ciphertext of a canonical path fragment. The canonical fragment encoding method used in PathGES makes the length of the path fragments stored in M2 exhibit a regularity, that is, being a power of 2. Therefore, the size of the corresponding ciphertext also shows a certain regularity. By observing all the ciphertexts in M2 or listening to multiple responses, an adversary can consider the smallest ciphertext size as the ciphertext size corresponding to a path of length 1. Then, by observing the target response, the adversary can infer the path length of the query path based on the size of the ciphertext contained in the target response. The standardization (i.e., the regularity shown) of path fragments brought about by the canonical fragment encoding makes it possible to conduct sidechannel attacks on PathGES. We have verified this through experiments as well. This information leakage athGES . Therefore, we consider that PathGES has vulnerabilities to side-channel is not defined in LP Q attacks. The Merge-and-Divide mechanism of BlindGES makes the lengths of the fragments stored in M2 be fixed at two lengths, l1 and l2 . Therefore, BlindGES will not cause additional information leakage during the use of a EMM-RH scheme.

4.2.3

Subpath Structure Leakage

PathGES pads a path with a length of l to a path of 2⌊log n⌋+1 . Then, ⌊log n⌋+2 canonical path fragments with lengths of 2j (j = 0, 1, · · · , ⌊log n⌋ + 1) are extracted, every time starting from the vertex (assumed to be v) closest to the root on this path. Suppose the length of this path is 2⌊log n⌋ + k, where 1 ≤ k ≤ 2⌊log n⌋+1 − 2⌊log n⌋ . The (2⌊log n⌋ + j)-th vertex on this path is vj , (j = 1, · · · , k), and assume that the token corresponding to the canonical path fragment with a length of 2⌊log n⌋+1 for this path is tk. By retrieving M1 , it is found that the token sets corresponding to the SPSP queries (v, vj ) (j = 1, · · · , k) all contain tk. For the query (v, v1 ), it obtains additional information: the shortest path information of (v, vj ′ ) (j ′ = 2, · · · , k). PathGES uses the multi-path fragment information contained in the canonical fragments to achieve a one-to-many mapping between tokens and paths. However, the canonical path fragments contain multiple path fragments with a sub-path structure (i.e., short paths are sub-paths of long paths), leading to additional information leakage.

13

4.3

Summary

PathGES fails to achieve its intended design goals. The prevalence of non-highly imbalanced trees in real-world graphs prevents generation of sufficiently long canonical fragments. Over 99% of tokens map to a single unique path fragment, creating a critical vulnerability that enables query recovery attacks.

5

Our Attack: Fragment Tree Attack Methodology

5.1

Threat Model and Assumptions

This section defines the threat model and assumptions underlying the Fragment Tree attack. We assume the server acts as an honest-but-curious adversary. While honestly answering SDSP queries, it also attempts to recover the underlying query content by leveraging available leakage. The attack aims to infer the plaintext values of executed queries based on the given graph and query-induced leakage. Following the security assumptions adopted in the Falzon-Paterson attack [5] and in PathGES [4], we assume the graph is public. That is, the server knows the original graph that was encrypted to produce EM1 and EM2 . As the adversary, the server can acquire all initial search tokens. Furthermore, since PathGES instantiates M1 using a response-revealing encrypted multimap scheme, the server can reconstruct M1 after observing a sufficient number of initial token queries. We also assume the server is familiar with standard shortest path algorithms and the HLD algorithm. The adversary aims to: 1) Query Recovery. For each observed query token tk, recover the corresponding source-destination pair (u, v) that the client queried. 2) Approximate Query Recovery. If exact recovery is impossible, narrow the candidate set to as few possibilities as possible (ideally 2-5 candidates). 3) Path Length Inference. Infer the length of the shortest path from the response size (side-channel attack).

5.2

Overview of Attack Process

The basic process of our attack is as follows: First, the server constructs an SDSP tree for each vertex based on a given graph, and executes the HLD algorithm on each SDSP tree to obtain the corresponding P Set (these two steps are the same as those in PathGES). Then, the server constructs fragment trees introduced in this paper based on P Set, while building query trees based on the leaked information of PathGES (for example, M1 ). Finally, the query recovery attack on PathGES is implemented by leveraging the isomorphic relationships between fragment trees and query trees. For example, Fig. 6 shows the fragment trees constructed based on P Setv derived from Fig. 3, as well as the query trees built from M1 in Fig. 5. If they are isomorphic, we can implement the following query recovery attack. By comparing the topology between the fragment trees and the query trees, we (2) (2) can determine that tk(v,w8 ,v,1) maps to the path fragment (w10 , w11 , v), tk(v,w3 ,w10 ,0) maps to (w3 , w10 ), (2)

(2)

(2)

tk(v,w8 ,v,0) maps to (w11 , v), tk(v,w2 ,w11 ,0) maps to (w2 , w11 ), tk(v,w8 ,v,2) maps to (w8 , w9 , w10 , w11 , v), (2)

(2)

(2)

tk(v,w7 ,w8 ,0) maps to (w7 , w8 ), and tk(v,w6 ,w7 ,0) maps to (w6 , w7 ). However, since the tokens tk(v,w1 ,w2 ,0) (2)

and tk(v,w0 ,w2 ,0) share the same topology, we cannot accurately distinguish their mappings to the path (2)

(2)

fragments (w1 , w2 ) and (w0 , w2 ). Similarly, the mappings between tk(v,w4 ,w9 ,0) , tk(v,w5 ,w8 ,0) and the path fragments (w4 , w9 ), (w5 , w8 ) cannot be distinguished either. Ultimately, we can uniquely recover the query pairs (w11 , v), (w2 , v), (w10 , v), (w3 , v), (w7 , v), and (w6 , v). The query pairs (w9 , v) and (w8 , v) are mapped by the same token, while the token sets for (w1 , v), (w0 , v), (w4 , v), and (w5 , v) are indistinguishable, thus they cannot be directly recovered. The above example illustrates that our query recovery attack method can effectively launch an attack on PathGES. The key factors enabling our attack method to achieve effective results include: What is a fragment tree? How to construct fragment trees based on P Set? How to build query trees based on M1 ? How can we prove that the constructed fragment trees and query trees are isomorphic? Below, we will clarify these key issues one by one in three subsections.

14

Figure 6: Examples of fragment trees and query trees constructed by our attack.

5.3

Fragment Tree Construction

5.3.1

Definition of Fragment Tree

A fragment tree is a binary tuple F = (P (F ), E(F )), where: • P (F ) is a set of nodes, each corresponding to a collection of disjoint path fragments • E(F ) a set of directed edges representing concatenation relationships between fragments The fragment tree takes disjoint path fragments as nodes, with the path fragment containing the destination vertex serving as the root. Suppose there are two disjoint path fragments, p1 = (w, · · · , w′ ) and p2 = (u, · · · , w), and they share a connecting anchor w. Thus, p1 is the direct predecessor of p2 (i.e., the relationship p1 || p2 exists). There is a directed edge from the node corresponding to p2 to the node corresponding to p1 in the corresponding fragment tree. 5.3.2

Fragment Tree Construction Algorithm

Given an SDSP tree Tv (rooted at v) of the given graph G, the server firstly executes the HLD algorithm on Tv and obtains the path fragment set P Setv . Then, it takes set P Setv and the root v as inputs and invokes Algorithm 1 to generate the corresponding fragment trees. Algorithm 1 consists of two phases: 1) preprocessing of path fragments (steps 2-10), and 2) queue-based tree construction (steps 11-27). Steps 2 to 10 of Algorithm 1 involve preprocessing P Setv . This preprocessing converts a long path fragment into multiple sub-path fragments of different lengths that share the same ending vertex. For example, a path fragment of length 4 with the last vertex being w will be converted into three sub-path fragments of lengths 1, 2, and 4 respectively, all ending with vertex w; a path fragment of length 6 with the last vertex being w will be converted into four sub-path fragments of lengths 1, 2, 4, and 6 respectively, all ending with vertex w. For another example, the path fragment (w8 , w9 , w10 , w11 , v) in Fig. 6 is converted into three sub-path fragments (w11 , v), (w10 , w11 , v), and (w8 , w9 , w10 , w11 , v). Among the preprocessed path fragments, more than one fragment may include the root v. Therefore, one P Setv corresponds to a fragment-tree forest.

5.4

Query Tree Construction

5.4.1

Background: Query Tree Definition

As defined in Section 2.1, a query tree Q = (T K, E ′ ) is a tree constructed by the server after collecting all leaked tokens, where: • T K is the set of all leaked tokens observed in the queries, with each token corresponding to a node 15

Algorithm 1: Building Fragment Trees Input: P Setv , the root v. Output: A set Fv of fragment trees. 1 Initialize P S = ∅; Fv = ∅; 2 while each path fragment p of P Setv do 3 if the length ofSP is 1 then 4 PS = PS {p}; 5 else 6 if 2j−1 < the length of P ≤ 2j then 7 for k = 0; k ≤ j − 1; k + + do 8 p′ ← The sub-fragment of length 2k at the rightmost end of p; S ′ 9 PS = PS {p }; S 10 PS = PS {p}; while P S is not empty do if there exists a path fragment ending with v in P S then 13 Initialize an empty fragment tree F = (P (F ), E(F )); 14 Initialize an empty queue Queue; 15 Remove this fragment from P S and insert it into Queue; 16 while Queue is not empty do 17 p2 ← Delete the front element of Queue; Create a node node2 based on p2 and incorporate it into P (F ); 18 if node2 is the first node to be created then 19 Use it as the root of F ;

11

12

while there exists a path fragment p1 in P S such that p1 || p2 holds do Remove p1 from P S and insert it into Queue; Create a node node1 based on p1 and incorporate it into P (F ); Add an edge from node1 to node2 into E(F ); p2 ← p1 ; node2 ← node1 ; S Fv = F v {F }; else break;

20 21 22 23 24 25 26 27 28

Return Fv .

• E ′ is a set of directed edges representing concatenation relationships between tokens For a fixed destination vertex v, the query tree Qv has tk(v,v) as its root. If a token tkw,v is observed to be followed by tk(v,v) in a query sequence, a directed edge is added from tkw,v to the root. 5.4.2

Token Sorting via Bucket-Based Method

After successfully constructing fragment trees, we need to build query trees that are isomorphic to them. Since EM1 adopts a response-revealing multi-map encryption algorithm, after the client completes all SDSP queries, the server can obtain full information about M1 . Our attack method use M1 to construct query trees isomorphic to fragment trees. The key challenge is how to discover the direct predecessor relationships between the tokens stored in M1 . We have designed a bucket-based multi-round local sorting algorithm for M1 (see Algorithm 2) to address this critical issue. Example. we take the M1 in Fig. 5 as an example to elaborate on the basic idea of this algorithm. The specific processing process is shown in Fig. 7. First, we perform bucketing processing on M1 based on the number of stored tokens. Storage locations with the same number of tokens belong to the same bucket, and duplicate entries within the bucket are removed (see Fig. 7 (a) → (b)). We use Dz to denote the set of storage locations that store z tokens, and T Kjz to denote the set of tokens stored in the j-th storage location within Dz . Next, we sort the tokens in each storage location within each bucket. When M1 is divided into Z buckets, a total of Z − 1 rounds of part-range sorting will be performed. In the z-th (z = 2, · · · , Z)

16

Algorithm 2: Bucket-based Token Sorting Input: M1 . Output: Sorted Buckets D1 , · · · , DZ . 1 Bucketing and deduplicating M1 yields D1 , · · · , DZ ; 2 for z = 2; z ≤ Z; z + + do 3 for j = 1; j ≤ |Dz−1 |; j + + do 4 for k = 1; k ≤ |Dz |; k + + do 5 if T Kkz ⊃ T Kjz−1 then 6 T Kkz ← Merge the ordered sequences T Kjz−1 and T Kkz − T Kjz−1 ; 7

Return D1 , · · · , DZ .

round of local sorting, the tokens stored in each location of Dz are sorted based on the pre-sorted tokens z−1 in Dz−1 . The so-called ordered bucket Dz−1 means that all T K1z−1 , · · · T K|D are ordered sequences. z−1 | It is important to note that the tokens in each storage location of D1 are already in a trivial order. The rule for sorting Dz based on the pre-sorted Dz−1 is (see Fig. 7 (b) → (c), (c) → (d)): For each storage location in Dz , identify the tokens that appear in Dz−1 , arrange them in the order they appear in Dz−1 at the front, and place the remaining token in that location at the end. Obviously, the number of tokens stored in each location of Dz is exactly one more than that stored in each location of Dz−1 .

Figure 7: Illustrates the process of bucket-based token sorting.

5.4.3

Query Tree Generation Algorithm

After obtaining the ordered D1 , · · · , DZ , the server generates query trees in a layer-by-layer manner using Algorithm 3). The nodes corresponding to the tokens in D1 are the roots of query trees. Then, a node is generated for the z-th token in each token set within Dz , and a directed edge is subsequently added from this node to the node corresponding to its immediate predecessor token in the token set (i.e., the (z − 1)-th token). Example. Taking the ordered buckets in Fig. 7(d) as an example, we will explain how to construct the query trees shown in Fig. 6. The fact that there are three token sets in D1 in Fig. 7(d) means that three query trees Q1 , Q2 , and Q3 will be generated, with the tokens tk(v,w8 ,v,1) , tk(v,w8 ,v,2) , and tk(v,w8 ,v,0) in these three token sets serving as their respective roots. Because there are five token sets in D2 in Fig. 7(d), there are a total of five nodes in the second layer, which correspond to the second tokens of these five token sets respectively. Three of them point to the root node corresponding to tk(v,w8 ,v,2) , one of them points to the root node corresponding to tk(v,w8 ,v,1) , and one points to the root node corresponding to tk(v,w8 ,v,0) . By analogy, there are three nodes in the third layer, which correspond to the third tokens of the three token sets in D3 respectively. Among them, two point to the second-layer node corresponding to tk(v,w2 ,w11 ,0) , and one points to the second-layer node corresponding to tk(v,w7 ,w8 ,0) .

17

Algorithm 3: Building Query Trees Input: M1 . Output: Query Trees Q1 , · · · , Q|D1 | . 1 D1 , · · · , DZ ← Bucket-basedTokenSorting(M1 ); 2 for i = 1; i ≤ |D1 |; i + + do 3 Create a node for the token in T Ki1 to serve as the root of Qi ; for z = 2; z ≤ Z; z + + do for j = 1; j ≤ |Dz |; j + + do 6 Create a node for the z-th token in T Kjz ; 7 Add a directed edge from this node to the node corresponding to the (z − 1)-th token in T Kjz ;

4

5

8

Return Q1 , · · · , Q|D1 | .

5.5

Isomorphism Proof

This section establishes the theoretical foundation for the attack by proving the isomorphism between fragment trees and query trees. 5.5.1

Definitions

Definition 5.1 (Consistency). Let G = (V, E) be a graph, and let the query sequence q = (q1 , q2 , . . . , qk ) denote the k shortest path queries issued by the client, where each query qi corresponds to a node pair (u, v). Let T K = (T K11 , T K21 , . . . , T Kkx ) denote the sequence of token sets leaked for all queries. If there exists an assignment π : T K → V × V is a mapping from token set to SDSP queries,such that L(G, q) = L(G, π(T K)), then the mapping π is said to be consistent with the leakage L(G, q). Informally, consistency requires that each query (u, v) can correspond to an observable leaked token set. Definition 5.2 (Query Recovery). Given a query set q = (q1 , q2 , . . . , qk ), where each qi denotes a shortest path query, and the corresponding leaked token sets are T K = (T K11 , T K21 , . . . , T Kkx ), Π is the set of all query-token mappings consistent with L(G, q). If the adversary is able to output a n mapping such that for any leaked token set T Km ∈ T K, it can provide a set of possible original queries n {π(T Km ) | π ∈ Π}, then we say the adversary achieves Query Recovery (QR). n n ) to determine can be mapped through π(T Km Informally, query recovery requires that each T Km a set of approximate queries consistent with the leakage. Although the approximate query set may not be unique, the correct query pair must be contained within each approximate query set. To explain our query recovery, we take an example from Fig. 6 and Fig. 7: (2) (2) (2) Example. In Fig.7, we observe the token leaked T K11 = {tk(v,w8 ,v,0) }, T K52 = {tk(v,w8 ,v,0) , tk(v,w2 ,w11 ,0) }, (2)

(2)

(2)

(2)

(2)

(2)

T K23 = {tk(v,w8 ,v,0) , tk(v,w2 ,w11 ,0) , tk(v,w1 ,w2 ,0) } and T K33 = {tk(v,w8 ,v,0) , tk(v,w2 ,w11 ,0) , tk(v,w0 ,w2 ,0) }. Attackers can use these leaked tokens to construct the query tree Q3 shown in Fig. 6, which is isomorphic to F1 .To achieve query recovery, the attacker must produce the following outputs: {

T K11 : {(w11 , v)}

T K52 : {(w2 , v)}

T K23 : {(w0 , v), (w1 , v)}

T K33 : {(w0 , v), (w1 , v)}

}.

Among the above four outputs, T K11 and T K52 can be accurately recovered, while T K23 and T K33 cannot uniquely determine the corresponding query pairs due to indistinguishable topology. It is worth noting that the failure to precisely recover a query pair may result not only from indistinguishable topological structures, but also from ambiguity caused by overly long path segments. For example, if the leaked token (2) tk(v,w8 ,v,2) is mapped to the path segment (v, w11 , w10 , w9 , w8 ), we can determine that the destination is v, but it is difficult to distinguish whether the starting point is w8 or w9 . Definition 5.4 (Fully Query Recovery). If the adversary has achieved query recovery (QR) and satisfies |Π| = 1, then the adversary is said to have achieved fully query recovery (FQR). Informally, Fully Query Recovery (FQR) refers to a precise form of query recovery, where the approximate query set recovered by the attacker contains only one unique query pair. We further elaborate on the properties of isomorphic trees and prove that two trees with identical path name sets are isomorphic. In the Falzon-Paterson attack, consider two shortest path trees Tr = 18

(V, E) and Tr′′ = (V ′ , E ′ ) rooted at different nodes r and r′ , respectively. Suppose there exists a path Pu,r = (u, w1 , w2 , . . . , wt , r) from node u to root r in Tr , and a path Pu′ ,r′ = (u′ , w1′ , w2′ , . . . , wℓ′ , r′ ) from node u′ to root r′ in Tr′′ . 5.5.2

Core Lemmas and Theorems

Theorem 5.1. If there exists a tree isomorphism φ : Tr → Tr′′ such that φ(u) = u′ , then it follows that the path lengths must be equal (i.e., t = ℓ), and for any i ∈ [1, t], we have φ(wi ) = wi′ . In other words, the paths strictly correspond one-to-one under the isomorphism. The Theorem 5.1 is proved in the Falzon-Paterson attack[5].The fragment tree we construct is essentially a structural compression of the original SDSP tree. It aggregates consecutive path nodes in the original tree into segments, forming a coarser-grained hierarchical structure. The root of the fragment tree corresponds to the segment containing the root node r and the fragment tree is logically equivalent to the SDSP tree. It still preserves the core properties of the SDSP tree: for example, the path from any node to the root is acyclic and unique within the fragment tree, and the path relationships between any two nodes remain unchanged. Let F = (P (F ), E(F )) and F ′ = (P ′ (F ′ ), E ′ (F ′ )) be two two isomorphic fragment trees. For F , there exists a path from a start node u to an end node r, whose sequence of path fragments is denoted by Pu,r = (pu , p1 , p2 , . . . , pa , pr ), where each pi consists of a sequence of several nodes, with the start node u ∈ pu and the end node r ∈ pr . Similarly, for F ′ , there exists a path from start node u′ to end node r′ , whose path fragment sequence is Pu′ ′ ,r′ = (p′u′ , p′1 , p′2 , . . . , p′b , p′r′ ), where each p′i consists of a sequence of several nodes, with u′ ∈ p′u′ and r′ ∈ p′r′ . Lemma 5.1. If there exists a fragment-to-fragment mapping φ : F → F ′ such that φ(pu ) = p′u′ , then it follows that a = b, and for all i ∈ [1, a], we have φ(pi ) = p′i . Proof. Given that φ(pu ) = p′u′ and according to the definition of rooted tree isomorphism, we also have φ(pr ) = pr′ . The isomorphism between graphs preserves edges; therefore, the mapping function φ must map the path fragment sequence Pu,r to Pu′ ′ ,r′ . In other words, the number of path fragments forming these two shortest paths must be equal, hence a = b. Combining the above observations, we obtain the correspondence between the edges of the two isomorphic trees as follows: (φ(pu ), φ(p1 )) = (p′u′ , p′1 ), (φ(p1 ), φ(p2 )) = (p′1 , p′2 ), . . . , (φ(pa ), φ(pr )) = (p′b , p′r′ ). Thus, it is proven that φ(pi ) = p′i . □ Let Q = (T K, E ′ ) be a query tree, and the leaked and sorted token set for the query (u′ , r′ ) be T K(u′ ,r′ ) = (tku′ , tk1 , tk2 , . . . , tkc , tkr′ ). To facilitate the description of the logical and quantitative relationship between the token tk(r,u,v,j) and the path fragment p, we abbreviate tk(r,u,v,j) as tki . The path fragment mapped by tku′ contains the start node u′ , and the path fragment mapped by tkr′ contains the root r′ . Based on Lemma 5.1, we can derive a similar conclusion as follows: Lemma 5.2. If there exists a mapping from fragments to tokens φ : F → Q suchs that φ(pu ) = tku′ , then it must hold that a = c, and for any i ∈ [1, a], we have φ(pi ) = tki . We use F [pi ] to denote the subtree rooted at the path fragment pi , and Q[tki ] to denote the subtree rooted at the token tki . Theorem 5.3. Let φ be an isomorphic mapping from F to Q. This holds if and only if there exists a perfect matching between each pi ∈ F and tki ∈ Q such that any subtree F [pi ] in F can be mapped to the subtree Q[tki ]. Proof. Suppose φ is an isomorphic mapping from F to Q, and (pi , pi+1 ) is an edge in the fragment tree. If φ(pi ) = tki and φ(pi+1 ) = tki+1 with pi , pi+1 ∈ F , then by the edge-preserving property of isomorphism, φ must ensure the existence of the edge (tki , tki+1 ), i.e., φ(pi , pi+1 ) = (tki , tki+1 ). Extending this property to subtrees yields F [pi ] ∼ □ = Q[tki ]. 5.5.3

PathName-Based Isomorphism

The computation of path names is the key to finding an isomorphic fragment tree for the query tree Q. Recall from Section 2.4 taht PathName encodes the path structure from a node to the root. We denote by P athN ameF (pi ) the pathname from a node pi to the root node pr in the fragment tree F . According to the definition of pathnames, we have: P athN ameF (pu ) = h(N ame(pu )∥P athN ameF (p1 )), P athN ameF (p1 ) = h(N ame(p1 )∥P athN ameF (p2 )), ... 19

P athN ameF (pc ) = h(N ame(pc )∥P athN ameF (pr )), P athN ameF (pr ) = h(N ame(pr )) Similarly, we denote by P athN ameQ (tki ) the pathname from a token tki to the root token tkr′ in the query tree Q. According to the definition of pathnames, we have: P athN ameQ (tku′ ) = h(N ame(tku′ )∥P athN ameQ (tk1 )), P athN ameQ (tk1 ) = h(N ame(tk1 )∥P athN ameQ (tk2 )), ... P athN ameQ (tkc ) = h(N ame(tkc )∥P athN ameQ (tkr′ )), P athN ameQ (tkr′ ) = h(N ame(tkr′ )) Theorem 5.2. If the fragment tree F = (P (F ), E(F )) and the query tree Q = (T K, E ′ ) are isomorphic, and the mapping function φ maps pu ∈ Pu,v to tku′ ∈ T Ku′ ,r′ , then it holds that P athN ameF (pu ) = P athN ameQ (tku′ ). Conversely, if P athN ameF (pu ) = P athN ameQ (tku′ ), then F ∼ = Q, and there exists a mapping function φ that maps pi to tki . Proof. For the forward direction, since Fpr and Qr′ are isomorphic, by Theorem 4.9 we know that F [pi ] ∼ = Q[tki ]. For any pi and tki , we have N ame(pi ) = N ame(tki ). Moreover, since pu is mapped to tku′ , by Lemma 4.7 we have a = c. Finally, by the definition of path names, the path name is the concatenation of the canonical names from the root to the start node in each tree. Hence, we conclude that P athN ameF (pu ) = P athN ameQ (tku′ ). For the reverse direction, from P athN ameF (pu ) = P athN ameQ (tku′ ) we obtain N ame(pu ) = N ame(tku′ ), N ame(p1 ) = N ame(tk1 ), · · · , N ame(pr ) = N ame(tkr′ ). Thus, F [pi ] ∼ = Q[tki ], and there□ fore F ∼ = Q. Hence, there exists a mapping function φ that perfectly matches pi and tki . Corollary 5.1. According to Theorem 4.8, if the fragment tree F and the query tree Q are isomorphic, and each path fragment pi in the fragment tree and each token tki in the query tree Q has a unique path name, then intuitively, every pi in F can only be mapped to the token tki in Q that has the same path name. Similarly, each token tki will also be mapped to the path fragment pi with the same path name.

5.6

Attack Effectiveness

We conducted the attack experiments on each dataset under the same environment using Python 3.10. The experimental server is equipped with six NVIDIA 8000-48G GPUs, each with 48GB VRAM. The GPU driver version is 535.104.12, supporting up to CUDA version 12.2. The CPU is an Intel Xeon E52699 v4 with 11 cores and 62.9GB memory. NetworkX (version 3.5) was used for graph-related operations, and the shortest paths were computed via a single-source shortest path algorithm. NumPy (version 2.3.1) was used for numerical computations. Matplotlib (version 3.10.3) was used for visualization. For cryptographic primitives, we used the Cryptography library (version 45.0.5). Symmetric encryption employed AES-CBC mode (with 16-byte keys), and SHA-256 was used as the hash function. Tokens were generated using HMAC-SHA256, truncated to 128 bits. The source code used to implement and evaluate the Fragment Tree attack is publicly available at: https://anonymous.4open.science/r/Fragment-Trees/ 5.6.1

Graph Datasets

We conducted attack experiments on seven datasets, which are the same datasets used in the Falzon–Paterson attack. All datasets are derived from real-world networks, with the number of vertices ranging from as few as 35 to as many as 22,687. The graph densities range from 0.0002 to 0.995. Below, we provide a brief description of these seven datasets. InternetRouting: This dataset originates from the University of Oregon Route Views Project and was extracted using the dense subgraph extraction algorithm proposed by Charikar[2], as adopted by Ambavi et al. Ca-GrQc: This dataset represents the collaboration network in the field of General Relativity and Quantum Cosmology on arXiv.org, covering the period from January 1993 to April 2003. It was also extracted as a subgraph using the dense subgraph extraction algorithm. email-Eu-core: This dataset captures email communications among researchers. An edge exists between two nodes if one sent an email to the other or received an email from the other. facebook: This dataset is derived from Facebook’s friendship network. An edge exists between two users if they are friends. p2p-Gnutella08, p2p-Gnutella04, p2p-Gnutella25: These three datasets describe snapshots of the Gnutella peer-to-peer (P2P) network collected on August 4 and August 8, and August 25, 2002, re-

20

spectively. Nodes represent hosts within the Gnutella network topology, and edges represent connections between these hosts. Note that PathGES also uses the six datasets listed above, except for p2p-Gnutella25.The datasets used in our evaluation are publicly available and can be accessed at:http://snap.stanford.edu/data. 5.6.2

Experimental Design

We conducted experiments in three aspects: 1) We executed the HLD algorithm on seven datasets to calculate the proportions of path fragments with lengths 1, 2, and 3, aiming to verify whether PathGES generates a large number of one-to-one mapping relationships during actual execution. 2) In the dimension of accurate query recovery attacks, we compared the attack effectiveness of the Falzon-Paterson attack on GKT and that of our attack method on PathGES (an enhanced version of GKT) based on seven datasets, thereby illustrating that our method can launch effective query recovery attacks against PathGES, which is resistant to the Falzon-Paterson attack. 3) Based on six datasets, we evaluated the effectiveness of our method in approximate query recovery when launching query recovery attacks against PathGES. The experimental results of the first aspect are shown in Table 2. These results indicate that PathGES indeed generates a large number of one-to-one mapping relationships when executed on realworld datasets, verifying the deficiency of PathGES in hiding topological structure information that we identified based on its implementation principle, and laying the foundation for the effective implementation of the attack method we proposed. Table 2: Statistics on the Number of Path Fragments with Different Lengths Data internetRouting Ca-GrQc email-EU-core facebook-combined p2p-Gnutella08 p2p-Gnutella04 p2p-Gnutella25 1 d=

|V | 35 46 1005 4309 6301 10876 22687

|E| 323 1030 16,706 88234 20777 39994 54705

d 0.543 0.995 0.02 0.011 0.001 0.0006 0.0002

Total Fragments 1141 2069 878147 16281762 34619060 101440282 472236309

Short Fragments 1141 2069 877940 16281560 34578445 101354239 472094187

Percentage 100% 100% 99.98% 99.99% 99.88% 99.92% 99.97%

2|E| represents the density of the graph. |V |2 −|V |

2 Short fragments refer to those with lengths of 1, 2, and 3. 3 Percentage indicates the proportion of the short fragments (lengths 1, 2, or 3) among all fragments.

The experimental results of the second aspect are shown in Table 3. The results show that, for the Falzon-Paterson attack and our attack method, the worst attack performance occurred on the Ca-GrQc graph, mainly due to its extremely high edge density of 0.995. In other words, most nodes in Ca-GrQc are almost directly connected, and the shortest path between any two nodes is often the direct edge connecting them. This results in a highly homogeneous topology for shortest paths, with path names being very similar across different paths, which severely weakens the distinguishability based on path names. The dataset with the best attack performance is p2p-Gnutella04, where approximately 10.236% of queries can be uniquely matched to the corresponding subpath fragments through leaked information. The effectiveness of our attack in achieving accurate query recovery against PathGES—which is equipped with defense mechanisms against such attacks—reaches approximately 50% of that achieved by the Falzon–Paterson attack against GKT, which lacks such defenses, across four datasets. On two datasets, our attack attains about 30% of the effectiveness of the Falzon–Paterson attack, while on one dataset, it reaches roughly 10%. The experimental results show that our method can exploit PathGES’s defense mechanism’s weakness in hiding topological structure information to launch effective query recovery attacks against it. The approximate query recovery attack is an attack where the target query cannot be accurately recovered; however, it can be confined to a limited range. To characterize this attack effect, we introduce the concept of query recovery capability. The query recovery capability for the accurate query recovery analyzed earlier is regarded as 100%. Suppose an attack can narrow the recovered target query down to two indistinguishable approximate queries, one of which is the target query. In that case, the query recovery capability of this attack is 50%. Similarly, a “33% query recovery capability” means that the attacker narrows the target query down to three indistinguishable approximate queries. “25%” and “20%” query recovery capabilities correspond to scenarios where the target query range is narrowed down to 21

Table 3: Comparison of Accurate Query Recovery Attack Effects Data

Total Query

internetRouting Ca-GrQc email-EU-core facebook-combined p2p-Gnutella08 p2p-Gnutella04 p2p-Gnutella25

1190 2070 1009020 16309482 39696300 118276500 514677282

Falzon-Paterson to GKT Unique Percentage 28 2.353% 3 0.145% 65659 6.507% 33634 0.206% 8519868 21.463% 25915785 21.911% 82736533 16.075%

Our Attack to PathGES Unique Percentage 5 0.420% 1 0.048% 20645 2.046% 19168 0.118% 3771341 9.500% 12106435 10.236% 45327736 8.807%

1 Unique indicates the number of query that can be precisely recovered during the attack. 2 Percentage represents the proportion of such queries among all queries.

four or five indistinguishable approximate queries, respectively. In other words, a query recovery attack with a query recovery capability of 100% is an accurate query recovery attack; a query recovery attack with a query recovery capability less than 100% is an approximate query recovery attack. The higher the query recovery capability, the higher the query recovery accuracy. The experimental results of the third aspect are shown as Fig. 8. The y-axis represents the proportion of queries that are successfully approximately recovered relative to the total number of queries. Fig. 8 shows that as the graph becomes sparser, the proportion of successful approximate queries with high recovery capability increases. Although these attacks cannot accurately recover the query, they confine the target query to a small range, posing a threat to PathGES. For example, in real-world scenarios, attackers often have access to additional side information, such as knowledge of the source vertex or commonly queried destinations. By leveraging such information, attackers can further reduce the approximate query set, thereby turning approximate recovery into exact recovery and exacerbating privacy risks.

Figure 8: The Situation of Successfully Launching Approximate Attacks on PathGES It should be noted that the graph represented by the Ca-GrQc dataset has an extremely high density. Therefore, the target query cannot be confined to a small range, making it impossible to mount effective approximate query recovery attacks. For this reason, the experiments of the third aspect were conducted on six datasets, excluding the Ca-GrQc dataset.

22

6

BlindGES Defense Scheme

6.1

Design Goals and Workflow

BlindGES is designed to accurately retrieve the shortest path between two nodes while effectively resisting the Falzon-Paterson attack. Moreover, it ensures that the adversary cannot infer the length of the shortest path from the query responses. In BlindGES, we construct a two-level index structure (see Algorithm 7) based on a Merge-andDivide mechanism (see Algorithm 6) that we introduced and the outputs P sets of the HLD algorithm for a given graph G. In addition, we design a corresponding algorithm (see Algorithm 8) to recover the final query results from the search results obtained based on the proposed two-level index structure. For ease of description, we take an SDSP tree Tr of G as an example below to elaborate on the core idea of BlindGES in constructing an index structure aimed at eliminating one-to-one mappings. As shown in Table2, the proportion of one-to-one mappings in BlindGES is reduced by at least 80% compared with PathGES.

6.2

Merge-and-Divide Mechanism

The merging target of the Merge-and-Divide mechanism is the paths of length 1 in P setr , and path concatenation is performed by introducing a dummy vertex ‘q’. The Merge-and-Divide mechanism adopts different division parameters l1 and l2 for merged paths and non-merged paths. Specifically, merged paths are divided into segments of length l1 , with the last segment padded with a dummy vertex ‘p’ if necessary; each non-merged path is divided into segments of length l2 , and the last segment is also padded with the dummy vertex ‘p’ if needed. The two-level index structure constructed by BlindGES consists of two mapping tables, M1 and M2 . The decomposed segments are stored in M2 . Therefore, BlindGES assigns a corresponding label to each segment. Suppose a segment is the j-th segment obtained by BlindGES decomposing a certain path, and assume that the first non-q vertex of this path is u and the last non-p vertex is v. Then, the label of this segment is lab(2) (r, u, v, j). Example. As shown in Fig.9, when merging the paths (v1 , v2 ), (v1 , v3 ), (v5 , v6 ), and (v8 , v9 ), we first insert the virtual vertex ‘q’ at the beginning of each of them and concatenate them to obtain a single path (q, v1 , v2 , q, v1 , v3 , q, v5 , v6 , q, v8 , v9 ). After executing ALM er (Algorithm 4), P set′r contains two types of paths: the merged paths that contain q (such as the lower path in Fig.9) and the non-merged paths (such as the upper path (u, w6 , w5 , w4 , w3 , w2 , w1 , v) in Fig.9). The client needs to set two parameter l1 and l2 to define the length of segment. l1 is an integer multiple of 3 and 1 < l2 < l1 . Note that, in this paper, we represent a path or segment using a vertex sequence. Therefore, l1 and l2 are number of vertices of a segment. The length of segment is l1 − 1 or l2 − 1. The client needs to pad the dummy vertex ‘p’ into merged (resp. non-merged) paths to make their length to be an integer multiple of l1 (resp. l2 ). A critical point is that when splitting a non-merging path, to prevent loss of path information, the starting vertex of the latter segment must overlap with the ending node of the previous segment. As shown in Fig.9, the path (p, p, u, w6 , w5 , w4 , w3 , w2 , w1 , v) should be split into (p, p, u, w6 ), (w6 , w5 , w4 , w3 ), and (w3 , w2 , w1 , v).

6.3

Two-Level Index Structure

In BlindGES, the two-level index structure consists of M1 and M2 , both encrypted to enable secure retrieval. M2 , encrypted via the EMM-RH algorithm, is accessed using tokens tk(r,u,v,j) stored within M1 . M1 itself, encrypted with EMM-RR, uses query tokens tk(u,v) corresponding to vertex pairs (u, v) to retrieve all relevant canonical fragment tokens associated with the shortest path from u to v. Thus, an SPSP query token tk(u,v) facilitates the recovery of all path segments constituting the shortest path between u and v through this encrypted two-level index. Note that, different from PathGES, the segments stored in each entry of M1 are not necessarily continuous segments, which means these segments, when pieced together, do not form a path, effectively avoiding the problem of excessive information leakage caused by returning redundant paths in PathGES. These segments contain the ones that the client truly needs. Therefore, the client can extract the actual required path from the returned segments.

23

Algorithm 4: Merge (ALM er ). Input: P setr . Output: The set of merged pairs P set′r . ′ 1 Initialize P setr ← ∅; buf f er ← ∅; 2 for path ∈ P setr do 3 if the length of path is one then 4 add “q” || path into buf f er; 5 6 7 8 9 10 11 12 13 14 15

else if buf f er ̸= ∅ then if buf f er has more than one path then Initialize merged path ← ∅; for bpath ∈ buf f er do merged path ← merged path||bpath; add merged path into P set′r ; clear buf f er; else single path ← buf f er[0]; delete q from single path; add single path into P set′r ; clear buf f er; add path into P set′r ;

if buf f er ̸= ∅ then if buf f er has more than one path then 18 for bpath ∈ buf f er do 19 merged path ← merged path||bpath;

16

17

20 21 22 23 24 25

add merged path into P set′r ; else single path ← buf f er[0]; delete q from single path; add single path into P set′r ; return P set′r ;

Figure 9: Example for the Merge-and-Divide mechanism.

24

Algorithm 5: Divide (ALDiv ). Input: P set′r , division parameters l1 and l2 . Output: The set of segment label pairs GP set′r . ′ 1 Initialize GP setr ← ∅; ′ ′ 2 for path ∈ P setr do 3 num edges ← |path′ | − 1; 4 if ‘q’ is the first vertex of path′ then 5 u ← the first non-q vertex of path′ ; 6 v ← the last non-q vertex of path′ ; 7 num ← ⌊num edges/l1 ⌋; 8 for j = 0 to num − 1 do 9 segment ← the subsequence of path′ , from the (j × l1 )-th vertex to the ((j+) × l1 − 1)-th vertex; (2) 10 add (segment, lab(r,u,v,j) ) into GP set′r ; 12

segment ← the subsequence of length |path′ | − num × l1 at the end of path′ ; Pad segment with ‘p’ to form a vertex sequence of length l1 ;

13

add (segment, lab(r,u,v,num) ) into GP set′r ;

11

14 15 16 17 18 19

20

(2)

else u ← the first vertex of path′ ; v ← the last vertex of path′ ; num ← ⌊num edges/l2 ⌋; for j = 0 to num − 1 do segment ← the subsequence of path′ , from the (j × l2 )-th vertex to the ((j+) × l2 − 1)-th vertex; (2) add (segment, lab(r,u,v,j) ) into GP set′r ;

22

segment ← the subsequence of length |path′ | − num × l2 at the end of path′ ; Pad segment with ‘p’ to form a vertex sequence of length l2 ;

23

add (segment, lab(r,u,v,num) ) into GP set′r ;

21

24

(2)

return GP set′r ;

Algorithm 6: Merge and Divide (ALM erDiv ). Input: P setr , division parameters l1 and l2 . Output: The set of segment label pairs GP set′r . ′ ′ 1 Initialize P setr ← ∅; GP setr ← ∅; ′ 2 P setr ← ALM er (P setr ); ′ ′ 3 GP setr ← ALDiv (P setr , l1 , l2 ); ′ 4 return GP setr ;

25

Algorithm 7: Index Structure Construction (ALIndex ). Input: {P setr }r∈V (G) , division parameters l1 and l2 , and K2 . Output: (M1 , M2 ). 1 Initialize M1 ← ∅, M2 ← ∅; 2 for each P setr ∈ {P setr }r∈V (G) do 3 GP set′r ← ALM erDiv (P setr , l1 , l2 ); 4 for each (segment, lab(2) ) ∈ GP set′ do 5 M2 [lab(2) ] ← segment; 6 tk ← EMM-RH.Token(K2 , lab(2) ); 7 w ← segment[0] (the first vertex of segment); 8 if w is not ‘q’ then 9 w ← the first non-p vertex of segment; 10 v ′ ← the third item of lab(2) ; 11 while w is not the last vertex of segment do 12 M1 [(w, r)] ← M1 [(v ′ , r)] ∪ [tk]; 13 shuffle(M1 [(w, r)]); 14 w ← the next vertex of segment; 15 16 17 18 19 20 21 22 23 24

25

else i ← 1; while i < l1 do w ← the i-th vertex of segment; v ′ ← the (i + 1)-th vertex of segment; if w is ‘p’ or v ′ is ‘p’ then break; M1 [(w, r)] ← M1 [(v ′ , r)] ∪ [tk]; shuffle(M1 [(w, r)]); i ← i + 3; return (M1 , M2 );

26

Algorithm 8: Shortest Path Recovery (ALReco ). Input: A set of fragments SegSet, the source vertex u, the destination vertex v. Output: the shortest path path(u,v) from u to v. 1 Initialize Edges ← ∅; 2 Initialize path(u,v) as a vertex sequence containing the vertex u; 3 for each segment ∈ SegSet do 4 for i from 0 to |f ragment— do 5 a ← f ragment[i]; 6 if a is ‘q’ then 7 continue; 8 9 10 11 12 13 14 15 16

else if a is ‘p’ then break; else b ← f ragment[i + 1]; if b is ‘p’ then break; else add (a, b) into Edges; i ← i + 1;

Set current ← u; while current ̸= v do 19 while (a, b) ∈ Edges is an unvisited edge do 20 if a == current then 21 current ← b; 22 add current into path(u,v) ; 23 break;

17 18

24

return path(u,v) ;

27

6.4

Query Processing

The construction of BlindGES is illustrated in detail in Fig. 10. In general, BlindGES consists of two phases: the setup phase and the query phase. The setup phase corresponds to the BlindGES.KeyGen algorithm and BlindGES.Encrypt algorithm. The client first generates various parameters by executing BlindGES.KeyGen. Then, the client constructs an encrypted two-level multimap index structure (as shown in Fig. 11) and sends it to the server. The query phase includes the BlindGES.Token algorithm, the BlindGES.Search algorithm, and the BlindGES.Reveal algorithm. The client generates a SPSP query by carrying out BlindGES.Token and sends the generated token to the server. The server executes BlindGES.Search based on the received token and the encrypted index structure to obtain the query result and returns it to the client. The client recover the corresponding shortest path from the received query result by executing BlindGES.Reveal.

Figure 10: BlindGES Implementation.

Figure 11: Workflow of setup phase in BlindGES.

28

6.5

Security Analysis

6.5.1

Leakage Functions

For a given graph G, suppose |G| = n. For each rooted SDSP tree of G, the length of the path is at most log n, the total number of tokens associated with a tree is at most (n − 1) log n. Therefore, the total number of entries of M1 is at most n(n − 1) log n. In the worst cast, all the edges in each SDSP tree are light edges. After performing HLD, for each tree, the number of paths in P Setr is at most n − 1. The lengths of these paths are all 1. In BlindGES, the lengths of fragments stored in M2 are l1 or l2 , where . To sum up, the upper bounds l1 > l2 . Therefore, the total number of entries of M2 is at most n(n−1) l2 of the sizes of M1 and M2 are (n − 2) log n and n(n−1) . For the convenience of the proof, we use these l1 EM M −RR EM M −RH upper bounds as LS (M1 ) and LS (M2 ), respectively. Given a multimap, the (lab, valSet) pairs within it are already determined and the labels in the multimap are all distinct. For M1 , one label corresponds to one SPSP query, and different labels correspond to different SPSP queries. Therefore, BlindGES leaks whether two queries are equal (that is EM M −RR QPM ). For M2 , one label corresponds one fragment, and different labels correspond to different 1 fragments. Therefore, BlindGES leaks whether two (encrypted) fragments in two responses are equal EM M −RH (that is QPM ). The query pattern (QP) is a k × k binary matrix A for a sequence of SPSP 2 queries q1 , · · · , qk . A[i][j] = 1 means that the ith query was the same as the jth query. Since BlindGES exploits an EMM-RR scheme for M1 and an EMM-RH scheme for M2 , BlindGES EM M −RR EM M −RH leaks the leaked information defined by APM and V olM . We can use a bipartite graph 1 2 ′ ′ BG = (V , E ) to describe these leaked information for BlindGES. Given a bipartite graph, its vertices are divided into two disjoint set V1′ and V2′ such that its every edge connects a vertex from set V1′ to a vertex from set V2′ , and there are no edges within the sets V1′ or V2′ themselves. The bipartite graph EM M −RR EM M −RH constructed according to APM and V olM is a structure pattern mentioned in [4]. We 1 2 ′ take the label set of M1 as V1 of BG and the label set of M2 as V2′ of BG. In other words, the vertices in V1′ correspond to SPSP queries, and the vertices of V2′ correspond to encrypted segments. For a lab, valSet pair in M1 , |valSet| represents the degree of the vertex corresponding to the label lab, which characterizes the number of edges incident to it. The values in the set valSet determine which |valSet| vertices in V2′ these |valSet| edges are connected to. Therefore, we can obtain the edge set E ′ of BG. Moreover, for a lab, valSet pair in M2 , since valSet is encrypted, we cannot obtain the values of the set valSet and can only know the size of the ciphertext. The size is taken as the weight of the vertex. There are only two values for the size of all ciphertexts, which correspond to the two grouping sizes l1 and l2 in the segmentation strategy of BlindGES. The degree of a vertex in V2′ indicates the number of times the fragment corresponding to the vertex appears in the query response. In conclusion, the setup leakage function of BlindGES is LBlindGES (G) = n, its query leakage S (G) = (A, BG). It should be noted that the above analysis process is refunction is LBlindGES Q EM M −RR versible. Therefore, QPM can be obtained according the query pattern A of LBlindGES (G), Q 1 EM M −RR EM M −RH EM M −RH and APM1 , QPM2 , and V olM2 can be obtained according to the structure pattern BG of LBlindGES (G). Q 6.5.2

Security Proof

M −RR M −RR M −RH Theorem 1. Suppose EMM-RR to be (LEM , LEM )-secure and EMM-RH to be (LEM , S Q S EM M −RH LQ )-secure. BlindGES is (LS , LQ )-secure according to Definition 1.

Proof : We denote the simulators of EMM-RR and EMM-RH as SimRR and SimRH , respectively. We need to construct a stateful simulator SimBlindGES to simulate the view of the adversary in the Ideal experiment of Definition 1 by using SimRR and SimRH and prove the view and BlindGES are computationally indistinguishable. The game hops of the hybrid argument are as follows: Hyb 0: This is exactly like the actual challenger. M −RH Hyb 1: It is the same as the previous Hyb, except for replacing EMM-RH.KeyGen with SimRH (LEM ). S If A can distinguish between the views before and after the replacement, A can compromise the adaptive security of EMM-RH with a non-negligible advantage. M −RR Hyb 2: It is the same as the previous Hyb, except for replacing EMM-RR.KeyGen with SimRR (LEM ). S If A can distinguish between the views before and after the replacement, A can compromise the adaptive security of EMM-RR with a non-negligible advantage.

29

Hyb 3: It is the same as the previous Hyb, except storing some additional state. Construct the bipartite graph BG and the binary matrix A based on the state information of executing the k queries (q1 , · · · , qk ). The distributions of this Hyb and the previous Hyb are equal. Hyb 4: It is the same as the previous Hyb, except for invoking the simulators SimRH (using M −RH LEM derived from LBlindGES ) instead of the EMM-RH. Q Q If A can distinguish between the views before and after the replacement, A can compromise the adaptive security of EMM-RH with a non-negligible advantage. Hyb 5: It is the same as the previous Hyb, except for invoking the simulators SimRR (using M −RR LEM derived from LBlindGES ) instead of the EMM-RR. Q Q If A can distinguish between the views before and after the replacement, A can compromise the adaptive security of EMM-RR with a non-negligible advantage. Hyb 6: It is the same as the previous Hyb, except for invoking the simulators SimBlindGES using M −RH M −RR LBlindGES instead of SimRH and SimRR . LBlindGES are equal to the tuple (LEM , LEM ). Q Q Q Q Thus this Hyb and the previous Hyb are computationally indistinguishable. The distribution Hyb 6 is identical to that of SimBlindGES . Therefore, A can distinguish the views in the Real and Ideal worlds with a negligible advantage, BlindGES is (LS , LQ )-secure. 6.5.3

Cryptanalysis

Additional information leakage caused during the use of the EMM-RH process: PathGES M −RH M −RH causes additional information leakage during the process of using a (LEM , LEM )-secure S Q EM M −RH EMM-RH scheme, where LQ = (QP EM M −RH , V olEM M −RH ), V olEM M −RH (M2 , lab) = |M2 [lab]|. The value of M2 [lab] is the ciphertext of a canonical path fragment. The canonical fragment encoding method used in PathGES makes the length of the path fragments stored in M2 exhibit a regularity, that is, being a power of 2. Therefore, the size of the corresponding ciphertext also shows a certain regularity. By observing all the ciphertexts in M2 or listening to multiple responses, an adversary can consider the smallest ciphertext size as the ciphertext size corresponding to a path of length 1. Then, by observing the target response, the adversary can infer the path length of the query path based on the size of the ciphertext contained in the target response. The standardization (i.e., the regularity shown) of path fragments brought about by the canonical fragment encoding makes it possible to conduct side-channel attacks on PathGES. We have verified this through experiments as well. This information leakage is not athGES . Therefore, we consider that PathGES has vulnerabilities to side-channel attacks. defined in LP Q The Merge-and-Divide mechanism of BlindGES makes the lengths of the fragments stored in M2 be fixed at two lengths, l1 and l2 . Therefore, BlindGES will not cause additional information leakage during the use of a EMM-RH scheme. Information leakage caused by the stored fragments: PathGES pads a path with a length of l to a path of 2⌊log n⌋+1 . Then, ⌊log n⌋ + 2 canonical path fragments with lengths of 2j (j = 0, 1, · · · , ⌊log n⌋ + 1) are extracted, every time starting from the vertex (assumed to be v) closest to the root on this path. Suppose the length of this path is 2⌊log n⌋ + k, where 1 ≤ k ≤ 2⌊log n⌋+1 − 2⌊log n⌋ . The (2⌊log n⌋ + j)-th vertex on this path is vj , (j = 1, · · · , k), and assume that the token corresponding to the canonical path fragment with a length of 2⌊log n⌋+1 for this path is tk. By retrieving M1 , it is found that the token sets corresponding to the SPSP queries (v, vj ) (j = 1, · · · , k) all contain tk. For the query (v, v1 ), it obtains additional information: the shortest path information of (v, vj ′ ) (j ′ = 2, · · · , k). PathGES uses the multi-path fragment information contained in the canonical fragments to achieve a one-to-many mapping between tokens and paths. However, the canonical path fragments contain multiple path fragments with a sub-path structure (i.e., short paths are sub-paths of long paths), leading to additional information leakage. The Merge-and-Divide mechanism of BlindGES ensures that the fragments finally stored in M2 are not necessarily all fragments with a sub-path structure, thus reducing the information leakage in the above-mentioned situation. Indeed, this information leakage will not pose an additional threat to the application scenarios where the querier is the graph owner. However, in application scenarios where the querier is not the graph owner, this information leakage will undermine the legitimate rights and interests of the graph owner, so it must be considered. Therefore, BlindGES is more likely to be extended to adapt to new application environments.

6.6

Empirical Evaluation

We conducted experiments on a workstation equipped with an NVIDIA GeForce RTX 5060 Ti GPU and an AMD EPYC 7K62 48-core processor (96 threads) with 251 GB of memory. The experiments were

30

implemented using Python version 3.10, along with the following libraries: • NetworkX 3.3: Used for graph representation and processing. We leveraged NetworkX to construct and manipulate graph structures and compute shortest paths. • Cryptography 42.0.8: Used to perform cryptographic operations. Our scheme adopts AES in CBC mode for symmetric encryption, with both block size and key length set to 16 bytes. Hashing operations use SHA-256, and search tokens are generated using HMAC based on SHA-256. In the experiments, all encryption processes were parallelized to fully utilize the device’s 48 physical cores (96 logical threads) of the AMD EPYC 7K62 processor, thereby maximizing computational efficiency. All experiments were conducted on this platform, leveraging Python’s parallel computing capabilities to accelerate the encryption procedures. The configuration of the experimental environment and the hardware conditions ensured the reliability and efficiency of the experimental results, providing a solid basis for validating the performance of our comparative evaluations. BlindGES was evaluated using the same social network datasets as those selected by Ghosh et al.[7] and Falzon et al. [4], ensuring consistency in the experimental setting. The more details of datasets can see Section 5.6.1. The source code used to implement and evaluate BlindGES is publicly available at: https://anonymous.4open.science/r/BlindGES/. 6.6.1

Performance Comparison

When running the BlindGES scheme, the segment length parameters for the two types of paths are configured as follows: l1 is set to 9, which corresponds to a merged path length of 8, and l2 is set to 5, which corresponds to a non-merged path length of 4. In the setup phase, we used Python’s os.path.getsize function to calculate the sizes of the two multimaps, M1 and M2 , and their encrypted data, EM1 and EM2 , for the six datasets. The setup phase also included the time for constructing the multimaps and encryption. For these six datasets, for the smallest dataset, internetRouting (n = 35), the total size of the two multimaps M1 and M2 was 200KB, and the total size of the encrypted data EM1 and EM2 sent to the server was 504KB, with the setup phase taking 1125 milliseconds. In contrast, for the largest dataset, p2p-Gnutella04 (n = 10876), the total size of M1 and M2 reached 37.09GB, and the total size of the encrypted data EM1 and EM2 was 66.6GB, with the setup phase taking 1.23 hours. In comparison, when running the PathGES scheme under the same conditions, the total size of the two multimaps M1 and M2 for the internetRouting dataset (n = 35) was 233KB, and the total size of the encrypted data EM1 and EM2 was 835KB, with the setup phase taking 1247 milliseconds. For the p2p-Gnutella04 dataset (n = 10876), the total size of M1 and M2 increased to 42.08GB, and the total size of the encrypted data EM1 and EM2 was 97.99GB, with the setup phase taking as long as 2.4 hours. Compared with PathGES, BlindGES demonstrates a clear advantage on complex graphs such as facebook-combined, p2p-Gnutella08, and p2p-Gnutella04. On these three datasets, the setup time of BlindGES is only half that of PathGES, and the total size of the two encrypted databases sent to the server is merely 59% ∼ 67% of that of PathGES. This improvement stems from the fact that PathGES stores a large number of duplicate canonical fragments, resulting in substantial storage redundancy. In contrast, BlindGES adopts a grouping strategy that partitions path fragments into two non-overlapping sets, thereby significantly reducing the storage overhead.The specific details of the two schemes during the setup stage are shown in Table 4. We measured the average query response time and reveal time of BlindGES and PathGES for each shortest-path length. As shown in the figure, across the six real-world datasets, both the response time and reveal time of BlindGES remain at the millisecond level. In particular, the query time does not exceed 0.4 milliseconds and is only half that of PathGES, while the reveal time is also slightly faster than that of PathGES. 6.6.2

Security Comparison

In this section, we compare BlindGES and PathGES in terms of the relationship between the shortest path length and the response. We argue that queries satisfying S = α · L will directly expose the length of the shortest path. Here, S represents the response returned by the query, α represents the response required for one edge in the shortest path, and L represents the length of the shortest path. For all responses in the PathGES scheme, the minimum value is Smin = 65B. Based on its multimap construction, an adversary can determine that a shortest path of length 1 requires a response of 65B, meaning that the response for one edge in the path fragment requires α = 65. If the response size S 31

Table 4: The performance of BlindGES and PathGES in the setup phase. PathGES

BlindGES

Data

M1

EM1

M2

EM2

time to comp MMs

enc time

setup time

internetRouting Ca-GrQc email-EU-core facebook-combined p2p-Gnutella08 p2p-Gnutella04

147KB 246KB 188MB 3.64GB 9.59GB 30.36GB

266KB 455KB 285.5MB 5.15GB 13.32GB 42.37GB

86KB 147KB 84.1MB 1.53GB 3.76GB 11.72GB

569KB 975KB 466.2MB 7.63GB 18.57GB 55.62GB

658ms 821ms 32s 6.8min 15.6min 42.9min

589ms 674ms 55s 14.3min 35.2min 100.8mmin

1247ms 1495ms 87s 21.1min 50.8min 143.7min

Data

M1

EM1

M2

EM2

time to comp MMs

enc time

setup time

internetRouting Ca-GrQc email-EU-core facebook-combined p2p-Gnutella08 p2p-Gnutella04

147KB 246KB 188MB 3.64GB 9.59GB 30.36GB

266KB 455KB 285.5MB 5.15GB 13.32GB 42.37GB

53KB 90KB 46.8MB 0.83GB 2.19GB 6.73GB

238KB 389KB 195.7MB 2.98GB 8.02GB 24.23GB

599ms 662ms 22.8s 3.6min 9.7min 25.6min

526ms 559ms 28.0s 6.4min 16.3min 48.3min

1125ms 1221ms 50.8s 10min 26min 73.9min

(a) The search time of PathGES

(b) The reveal time of PathGES

(c) The search time of BlindGES

(d) The reveal time of BlindGES

Figure 12: The search time and reveal time in PathGES and BlindGES

32

(a)

(b)

(c)

(d)

Figure 13: Relationship between shortest path length and response size in PathGES. The dots in the shaded area represent possible response values, and points on the line S = 65 · L indicate queries whose path lengths can be directly inferred. returned by the query satisfies S = 65 · L, it implies that the shortest path length of the query can be directly inferred. As shown in Fig.13, the points in the shaded area represent the possible response values corresponding to the shortest paths of different lengths. , and points on the line S = 65 · L represent queries where the shortest path length can be inferred. In the statistics of 100,000 random shortest path queries, at least 84% of the queries’ responses are linearly related to the shortest path length. This means that at least 84% of the queries will directly expose the shortest path length information. In contrast, our scheme is more effective in reducing the leakage of shortest path information in the response. This is because our scheme hides the response returned for the shortest path of length 1. In the BlindGES parameter setting, the minimum path fragment length mapped by each token is set to 4, and the minimum response Smin = 81B. However, for the adversary, they can only observe that the shortest path fragment requires 81B, without knowing how many edges are included in that fragment. Therefore, when the parameters change, even if the minimum response Smin is known, the adversary still finds it difficult to accurately deduce the true values of α and L. As shown in Fig.14, The points in the shaded area represent the possible response values corresponding to the shortest paths of different lengths. Points on the line S = 81 · L represent the inference based on a 81B response being considered as the response for one edge. In this case, fewer than 1% of the queries are likely to be accidentally guessed in the datasets.

7

Limitations and Future Work

While the Fragment Tree attack demonstrates the effectiveness of exploiting structural leakage in PathGES, and BlindGES provides a robust defense mechanism, both approaches have inherent limitations that point to directions for future research. Limitations of the Fragment Tree Attack. The attack assumes the server has knowledge of the complete plaintext graph and can observe all query tokens and their relationships over time. In scenarios where the graph is not known to the adversary or where query observation is limited, the attack’s effectiveness may be reduced. Additionally, the attack performs best on sparse graphs such as the Gnutella datasets, where approximately 10.24% of queries can be uniquely recovered. On dense

33

(a)

(b)

(c)

(d)

Figure 14: Relationship between shortest path length and response size in BlindGES. The dots in the shaded area represent possible response values, and points on the line S = 81 · L indicate queries whose path lengths can be directly inferred. graphs like Ca-GrQc, which has a density of 0.995, the attack achieves only 0.048% exact recovery because the high connectivity leads to highly homogeneous path names that are difficult to distinguish. The approximate query recovery capability, while narrowing queries to 2-5 candidates for about 10% of queries on sparse graphs, still requires additional side information to achieve exact recovery in many cases. Limitations of BlindGES. The Merge-and-Divide mechanism in BlindGES requires the client to predefine two division parameters, l1 and l2 which are set to 9 and 5 respectively in the experiments. These parameters may not be optimal for all graph types, and adaptive parameter selection based on graph density or structure could further improve performance. The setup phase of BlindGES, while significantly faster than PathGES on large graphs, still requires substantial computational resources for very large datasets—on p2p-Gnutella04, the setup time is approximately 73.9 minutes. Additionally, the security analysis assumes the underlying EMM-RR and EMM-RH schemes are secure, and any vulnerabilities in those primitives would affect BlindGES. Future Work Directions. Several promising directions emerge from this analysis. First, developing adaptive parameter selection mechanisms for BlindGES that automatically tune l1 and l2 based on graph characteristics could improve both security and efficiency across diverse graph types. Second, exploring alternative graph decomposition methods beyond HLD may yield better structural obfuscation for social networks where heavy edges are naturally scarce. Third, integrating differential privacy techniques with graph encryption could provide formal guarantees against side-channel attacks like the responsesize inference. Fourth, extending both the Fragment Tree attack and BlindGES to support dynamic graph updates—where vertices and edges are added or removed over time—remains an open challenge, as the current schemes assume static graphs. Fifth, investigating whether the isomorphism-based attack methodology can be applied to other structured encryption schemes beyond PathGES would help understand the broader implications of structural leakage. Finally, developing stronger leakage suppression techniques that go beyond the two-level index structure could further reduce the proportion of one-to-one mappings, ideally approaching zero while maintaining query efficiency

34

8

Conclusion

This report presents a comprehensive analysis of structural leakage in graph encryption schemes for shortest path queries, integrating findings from two complementary works. PathGES Analysis: We identify that PathGES, despite design intentions, maintains over 99% oneto-one token-path mappings on real-world datasets due to HLD imbalances. This enables both the Falzon-Paterson attack and side-channel inference of path lengths (84%+ of queries). Fragment Tree Attack: We present a novel attack methodology exploiting PathGES structural leakage. The attack constructs fragment trees from HLD decomposition and query trees from leaked tokens, proves their isomorphism, and recovers query contents. Experimental results show up to 10.24% exact query recovery on sparse graphs and candidate reduction to 2-5 possibilities for additional queries. BlindGES Defense: We present an enhanced scheme incorporating Merge-and-Divide mechanism and two-level multimap index. BlindGES reduces one-to-one mappings to below 20%, cuts setup time by 50%, reduces storage overhead by 32%, and limits path length leakage to under 1% while maintaining millisecond-level query response times. Together, these works demonstrate that structural leakage remains a critical vulnerability in graph encryption, that practical attacks can effectively exploit this leakage, and that careful design with mechanisms like Merge-and-Divide can substantially improve security without sacrificing efficiency.

References [1] Ning Cao, Zhenyu Yang, Cong Wang, Kui Ren, and Wenjing Lou. Privacy-preserving query over encrypted graph-structured data in cloud computing. In 2011 31st International Conference on Distributed Computing Systems, pages 393–402. IEEE, 2011. [2] Moses Charikar. Greedy approximation algorithms for finding dense components in a graph. In International workshop on approximation algorithms for combinatorial optimization, pages 84–95. Springer, 2000. [3] Melissa Chase and Seny Kamara. Structured encryption and controlled disclosure. In International conference on the theory and application of cryptology and information security, pages 577–594. Springer, 2010. [4] Francesca Falzon, Esha Ghosh, Kenneth G Paterson, and Roberto Tamassia. Pathges: An efficient and secure graph encryption scheme for shortest path queries. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, pages 4047–4061, 2024. [5] Francesca Falzon and Kenneth G Paterson. An efficient query recovery attack against a graph encryption scheme. In European Symposium on Research in Computer Security, pages 325–345. Springer, 2022. [6] Daniele Frigioni, Alberto Marchetti-Spaccamela, and Umberto Nanni. Semidynamic algorithms for maintaining single-source shortest path trees. Algorithmica, 22(3):250–274, 1998. [7] Esha Ghosh, Seny Kamara, and Roberto Tamassia. Efficient graph encryption scheme for shortest path queries. In Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security, pages 516–525, 2021. [8] Yunguo Guan, Rongxing Lu, Songnian Zhang, and Sean Lalla. Efficient and privacy-preserving subgraph matching queries in graph federation. In ICC 2023-IEEE International Conference on Communications, pages 2282–2287. IEEE, 2023. [9] Richard Henderson. Using graph databases to detect financial fraud. Computer Fraud & Security, 2020(7):6–10, 2020. [10] Mengdi Hu, Lanxiang Chen, Gaolin Chen, Yi Mu, and Robert H Deng. A pruned pendant vertex based index for shortest distance query under structured encrypted graph. IEEE Transactions on Information Forensics and Security, 2024. [11] Weiwei Jiang. Graph-based deep learning for communication networks: A survey. Computer Communications, 185:40–54, 2022.

35

[12] Shangqi Lai, Xingliang Yuan, Shi-Feng Sun, Joseph K Liu, Yuhong Liu, and Dongxi Liu. Graphse2 : An encrypted graph database for privacy-preserving social search. In Proceedings of the 2019 ACM Asia conference on computer and communications security, pages 41–54, 2019. [13] Mingyue Li, Chunfu Jia, Ruizhong Du, and Wei Shao. Forward and backward secure searchable encryption scheme supporting conjunctive queries over bipartite graphs. IEEE Transactions on Cloud Computing, 11(1):1091–1102, 2021. [14] Chang Liu, Liehuang Zhu, and Jinjun Chen. Graph encryption for top-k nearest keyword search queries on cloud. IEEE Transactions on Sustainable Computing, 2(4):371–381, 2017. [15] Xianrui Meng, Seny Kamara, Kobbi Nissim, and George Kollios. Grecs: Graph encryption for approximate shortest distance queries. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 504–517, 2015. [16] Kyriakos Mouratidis and Man Lung Yiu. Shortest path computation with no information leakage. arXiv preprint arXiv:1204.6076, 2012. [17] David F Nettleton. Data mining of social networks represented as graphs. Computer Science Review, 7:1–34, 2013. [18] You Peng, Zhuo Ma, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Xiaoshuang Chen. Efficiently answering quality constrained shortest distance queries in large graphs. In 2023 IEEE 39th International Conference on Data Engineering (ICDE), pages 856–868. IEEE, 2023. [19] Geong Sen Poh, Moesfa Soeheila Mohamad, and Muhammad Reza Z’aba. Structured encryption for conceptual graphs. In International Workshop on Security, pages 105–122. Springer, 2012. [20] D Selvaraj, SM Sankar, D Dhinakaran, and TP Anish. Outsourced analysis of encrypted graphs in the cloud with privacy protection. arXiv preprint arXiv:2304.10833, 2023. [21] Meng Shen, Baoli Ma, Liehuang Zhu, Rashid Mijumbi, Xiaojiang Du, and Jiankun Hu. Cloud-based approximate constrained shortest distance queries over encrypted graphs with privacy protection. IEEE Transactions on Information Forensics and Security, 13(4):940–953, 2018. [22] Daniel D Sleator and Robert Endre Tarjan. A data structure for dynamic trees. In Proceedings of the thirteenth annual ACM symposium on Theory of computing, pages 114–122, 1981. [23] Yunjiao Song, Xinrui Ge, Jia Yu, Rong Hao, and Ming Yang. Enabling privacy-preserving k-hop reachability query over encrypted graphs. IEEE Transactions on Services Computing, 2024. [24] Fuyi Wang, Zekai Chen, Lei Pan, Leo Yu Zhang, and Jianying Zhou. Cryptgraph: An efficient privacy-enhancing solution for accurate shortest path retrieval in cloud environments. In Proceedings of the 19th ACM Asia Conference on Computer and Communications Security, pages 1660–1674, 2024. [25] Qian Wang, Kui Ren, Minxin Du, Qi Li, and Aziz Mohaisen. Secgdb: Graph encryption for exact shortest distance queries with efficient updates. In International Conference on Financial Cryptography and Data Security, pages 79–97. Springer, 2017. [26] Songlei Wang, Yifeng Zheng, Xiaohua Jia, Hejiao Huang, and Cong Wang. Oblivgm: Oblivious attributed subgraph matching as a cloud service. IEEE Transactions on Information Forensics and Security, 17:3582–3596, 2022. [27] Songlei Wang, Yifeng Zheng, Xiaohua Jia, Hejiao Huang, and Cong Wang. Prigsim: Towards privacy-preserving graph similarity search as a cloud service. IEEE Transactions on Knowledge and Data Engineering, 35(10):10478–10496, 2023. [28] Songlei Wang, Yifeng Zheng, Xiaohua Jia, and Xun Yi. Pegraph: A system for privacy-preserving and efficient search over encrypted social graphs. IEEE Transactions on Information Forensics and Security, 17:3179–3194, 2022. [29] Eric W Weisstein. Floyd-warshall algorithm. https://mathworld. wolfram. com/, 2008.

36

[30] David J. Wu, Joe Zimmerman, Jeremy Planul, and John C. Mitchell. Privacy-preserving shortest path computation. In 23rd Annual Network and Distributed System Security Symposium, NDSS 2016, 2016. [31] Dong Xie, Guanru Li, Bin Yao, Xuan Wei, Xiaokui Xiao, Yunjun Gao, and Minyi Guo. Practical private shortest path computation based on oblivious storage. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pages 361–372. IEEE, 2016. [32] Lyu Xu, Byron Choi, Yun Peng, Jianliang Xu, and Sourav S Bhowmick. A framework for privacy preserving localized graph pattern query processing. Proceedings of the ACM on Management of Data, 1(2):1–27, 2023. [33] Mingyu Yang, Wentao Li, Wei Wang, Dong Wen, and Lu Qin. Querying numeric-constrained shortest distances on road networks. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pages 2463–2475. IEEE, 2024. [34] Junxiang Zhu, Heap-Yih Chong, Hongwei Zhao, Jeremy Wu, Yi Tan, and Honglei Xu. The application of graph in bim/gis integration. Buildings, 12(12):2162, 2022. [35] Xiangjian Zuo, Lixiang Li, Haipeng Peng, Shoushan Luo, and Yixian Yang. Privacy-preserving subgraph matching scheme with authentication in social networks. IEEE Transactions on Cloud Computing, 10(3):2038–2049, 2022.

37

Related documents

• Data-Free Graph Property Inference Attacks From Graph Embeddings: Data-Free Helps Data-Available#683334
• Empirical Auditing of Edge-Private Graph Generators#1051648
• Cryptanalysis of some nonabelian group-based key exchange protocols.#251240
• Improving the Selection Rule of Correlation Attacks for Remote Power Analysis#179408
• Certified Causal Attribution for Real-Time Attack Forensics in 6G Network Slicing#229434