An efficient query recovery attack against a graph encryption scheme

Abstract

Ghosh, Kamara, and Tamassia (GKT) (ASIA CCS 2021) proposed a graph encryption scheme supporting shortest path queries. This work presents a query recovery attack against the scheme when the adversary is given the original graph and the leakage of certain subsets of queries. The attack falls within the security model used by GKT, and is the first targeting schemes supporting shortest path queries. The attack uses classical graph algorithms to compute the canonical names of the single-destination shortest path spanning trees of the underlying graph and uses these canonical names to precompute the set of candidate queries that match each response. When all shortest path queries to a single node have been observed, the canonical names for the corresponding query tree are computed, and the responses are matched to the candidate queries from the offline phase. The output is guaranteed to contain the correct query. For a graph on $n$ vertices, the attack runs in time $O(n^3)$ and matches the time complexity of the GKT scheme’s setup. The attack’s practicality is demonstrated through an implementation and evaluation on the real-world datasets used in the original paper and on random graphs.

1. Introduction

Graphs are a powerful tool that can be used to model many problems related to social networks, biological networks, geographic relationships, etc. Plaintext graph database systems have already received much attention in both industry (e.g. Amazon Neptune, ¹ Facebook TAO, ² Neo4j, ³ and GraphDB ⁴ ) and academia (e.g. Pregel, ⁵ GraphLab, ⁶ and Trinity ⁷ ).

With the rise of data storage outsourcing, there is an increased interest in graph encryption schemes (GESs). A GES enables a client to encrypt a graph, outsource the storage of the encrypted graph to an untrusted server, and later make certain types of graph queries to the server. Current GES typically only support one type of query, for example, adjacency queries, ⁸ neighbor queries, ⁸ approximate shortest distance queries, ⁹ and exact shortest path queries.^10,11

This article extends the work presented by Falzon and Paterson ¹² and takes a closer look at the security of the GES of Ghosh, Kamara, and Tamassia (GKT) from ASIA CCS 2021. ¹⁰ This scheme will henceforth be referred to as the GKT scheme. The GKT scheme encrypts a graph $G$ such that when a shortest path query $(u,v)$ is issued for some vertices $u$ and $v$ of $G$ , the server returns information allowing the client to quickly recover the shortest path between $u$ and $v$ in $G$ . The scheme precomputes a matrix called the SP-matrix from which shortest paths can be efficiently computed, and then creates an encrypted version of this matrix, which we refer to as the encrypted database ( $\mathsf{E}\mathsf{D}\mathsf{B}$ ). $\mathsf{E}\mathsf{D}\mathsf{B}$ is sent to the server. At query time, the client computes a search token for the query $(u,v)$ ; this token is sent to the server and is used to start a sequence of look-ups to $\mathsf{E}\mathsf{D}\mathsf{B}$ . Each look-up results in a new token and a ciphertext encrypting the next vertex on the shortest path from $u$ to $v$ . The concatenation of these ciphertexts is returned to the client, and decrypting this sequence reveals the vertices in the shortest path.

The GKT scheme of Ghosh et al. ¹⁰ is very elegant and efficient. For a graph on $n$ vertices, computing the SP-matrix takes time $O(n^3)$ and dominates the setup time. Building a search token involves computing a pseudo-random function. Processing a query $(u,v)$ at the server requires $t$ look-ups in $\mathsf{E}\mathsf{D}\mathsf{B}$ , where $t$ is the length of the shortest path from $u$ to $v$ . Importantly, thanks to the design of the scheme, query processing can be done without interaction with the client, except to receive the initial search token and to return the result. This results in $\mathsf{E}\mathsf{D}\mathsf{B}$ revealing—at query time—the sequence of labels (tokens) needed for the recursive look-up and the sequence of (encrypted) vertices that is eventually returned to the client.

Ghosh et al. ¹⁰ provide a security proof of the GKT scheme in a simulation-based security model that assumes an honest-but-curious (semi-honest) server. The approach identifies a leakage profile for the GKT scheme and formally proves that the scheme leaks nothing more than this. The leakage profile comes in two parts: setup leakage (available to the server upon receipt of the encrypted data structure) and query leakage (that becomes available to the server as it processes each query). Specifically, the query leakage leaks when two queries are equal, that is, the query pattern, the length of the queried path, and how two paths with the same destination intersect.

This work exploits the query leakage of the GKT scheme to mount a query recovery (QR) attack against the scheme. This attack can be mounted by the honest-but-curious server and requires knowledge of the graph $G$ . This may appear to be a strong requirement, but it is, in fact, weaker than is permitted in the security model of Ghosh et al., ¹⁰ where the adversary can even choose $G$ . Assuming that the graph $G$ is public is a standard assumption for many schemes that support private graph queries.^10,13,14 There are many settings in which the graph may be known but the edge weights are private, or in which one only wishes to protect the privacy of the client’s queries. This model is ideal for routing and navigation systems in which the road network may easily be obtained online via Google Maps or Waze, but the client may wish to keep its queries private. In such a scenario, the map and traffic information are widely available, but the routing information of individual users is sensitive.

The attack has two phases. First, it has an offline, preprocessing phase that is carried out on the graph $G$ . In this phase, a plaintext description of all the shortest path trees in $G$ is extracted. These trees are then processed, and the candidate queries for each issued query are computed using each tree’s canonical name. A canonical name is an encoding of a graph that can be used to decide if two graphs are isomorphic; a canonical name of a rooted tree can be computed efficiently using the Aho, Hopcraft, and Ullman (AHU) algorithm. ¹⁵ This concludes the offline phase of the attack. Its time complexity is $O(n^3)$ , where $n$ is the number of vertices in $G$ , and matches the run time of our overall attack and the run time of the GKT scheme’s setup. Both the attack and the setup run-time are lower bounded by the time to compute the all-pairs shortest paths (APSP), which takes $O(n^3)$ time for general graphs. ¹⁶

The second phase of the attack is online: as queries are issued, the adversary constructs a second set of trees that correspond to the sequence of labels computed by the server when processing each query, that is, the per-query leakage of the scheme. That leakage is uniquely determined by the search token that initiates the look-up. This description uses the labels of $\mathsf{E}\mathsf{D}\mathsf{B}$ (which are search tokens) as vertices; two labels are connected if the first points to the second in $\mathsf{E}\mathsf{D}\mathsf{B}$ . When an entire tree has been constructed, the adversary can then run the AHU algorithm again to compute the canonical names associated with this query tree. An entire query tree $Q$ can be built when all queries to a particular destination have been issued. In practice, this is a realistic routing scenario where many trips may share a common popular destination (e.g. an airport, school, or distribution center).

By correctness of the scheme, there exists a collection of isomorphisms mapping $Q$ to at least one tree computed in the offline phase. Such isomorphisms also map shortest paths to shortest paths. A matching between paths in the trees from the online phase to the trees in the offline phase is thus performed. This can be done efficiently using a novel extension of the AHU algorithm, ¹⁵ which decides when one path can be mapped to another by an isomorphism of trees. This yields two look-up tables which, when composed, map each path in the first set of trees to a set of candidate paths in the second set. The search token of the queries associated with $Q$ is then used to look-up the possible candidate queries in the tables computed in the online phase. These candidate queries are then returned. The run time of this phase is $O(n^{\prime }\cdot n^2),$ where $n^{\prime }\le n$ is the number of complete query trees computed in the online phase. The output is guaranteed to contain the correct query.

In general, the leakage from a query can be consistent with many candidates, and the correct candidate cannot be uniquely determined. Graph theoretically, this is because there can be many isomorphisms between pairs of trees in the two sets. In the chosen graph setting, it is easy to construct a graph $G$ where, given any query tree $Q$ of $G$ , its isomorphism is uniquely determined and there is a unique candidate for each query of $Q$ , that is, one can achieve what is called full QR (FQR). For such graphs, the GKT scheme offers almost no protection to queries. In other cases, the query leakage may result in one or only a few possible query candidates, which may be damaging in practice. In order to explore the effectiveness of the attack, the theoretical results are supported with experiments on eight real-world graphs (six of which were used in Ghosh et al. ¹⁰ ) and on random graphs with varying graph sizes and edge probabilities. The results show that for the real-world graphs, as many as 21.9% of all queries can be uniquely recovered, and as many as half of all queries can be mapped to at most three candidate queries. The experimental results show that QR tends to result in smaller sets of candidate queries when the graphs are less dense, and that dense graphs tend to have more symmetries and hence result in larger sets of candidate queries. Note also that the attack is the best possible: it always outputs a minimal set of candidates consistent with the query leakage, and the correct query is always included in the set.

This work extends that of Falzon and Paterson ¹² along numerous dimensions, including formal proofs of their claims (Section 4), supporting examples (Section 4), additional experiments on random graphs that better demonstrate the relationship between attack success and graph density (Section 5), and a new variation of the attack from the perspective of a network adversary (Appendix A).

The contributions can be summarized as follows:

(1)

This work better formalizes the attack in Falzon and Paterson ¹² against a GES that supports shortest path queries. This attack works in a passive-persistent server-side adversarial setting. A novel extension of the attack in a network-adversarial setting is also presented.

(2)

This work leverages the GKT scheme’s leakage to mount an efficient QR attack against the scheme. In particular, for the real-world datasets used, the set of all query trees can be recovered with as few as 68.1% of the queries.

(3)

This work makes use of the classical AHU algorithm for the graph isomorphism problem for rooted trees. A new algorithm for deciding when a path in one tree can be mapped onto a path in another tree under an isomorphism is presented.

(4)

This work also reports on an implementation of the attack in Python and a thorough evaluation against real-world datasets and random graphs.

Looking ahead toward building new schemes, it is important to better understand how leakage can be exploited. This attack demonstrates that leaking the topology of subtrees of the encrypted graph is detrimental, and that a noninteractive scheme that relies on chaining search tokens may leak too much information to the server. This is true in part because many problems that are not known to be polynomial-time solvable on general graphs can be solved in polynomial time on trees (i.e. the graph isomorphism problem vs. the tree isomorphism problem). The characterization of the GKT scheme’s leakage may thus help inform the construction of more secure GESs.

1.1. Prior and related work

This section describes prior and related work concerning GESs and leakage-abuse attacks on structured encryption.

1.1.1. Graph encryption

Chase and Kamara ⁸ present the first GES that supports both adjacency queries and focused subgraph queries. Poh et al. ¹⁷ give a scheme for encrypting conceptual graphs. Meng et al. ⁹ present three schemes that support approximate shortest path queries on encrypted graphs, each with a slightly different leakage profile. To reduce storage overhead, their solution leverages sketch-based oracles that select seed vertices and store the exact shortest distance from all vertices to the seeds; these distances are then used to estimate shortest paths between any two vertices in the graph. Ghosh et al. ¹⁰ and Wang et al. ¹¹ present schemes that support exact shortest path queries on encrypted graphs.

Other solutions for privacy-preserving graph structures use other techniques such as secure multiparty computation and private information retrieval (e.g. Wu et al. ¹⁸ and Lai et al. ¹⁹ ) and differential privacy (e.g. Sala et al. ²⁰ ). These approaches have different security goals from EDB schemes that are built on symmetric encryption.

1.1.2. Attacks

While many schemes fitting the EDB paradigm have been developed, the security that these schemes offer is not yet fully understood. Security analysis is often done by developing attacks that reconstruct either queries or the database from the leakage functions. Leakage analysis of searchable symmetric encryption (SSE) schemes has been studied in a number of settings including both active^21–23 and passive^{21,22,24–26} adversarial settings. Recently, a number of works analyze the leakage stemming from schemes that support more complex query types such as range queries on one attribute^27–34 and multiattribute^35,36 data, and $k$ -nearest neighbor queries. ³⁷ The leakage of GESs was first analyzed by Goetschmann. ³⁸ The author considers schemes that support approximate shortest path queries that use sketch-based distance oracles (e.g. Meng et al. ⁹ ), present two methods for estimating distances between nodes, and give a QR attack that aims to recover the vertices in an encrypted query; the experimental evaluation demonstrates that with auxiliary knowledge on some queries, the adversary can distinguish among candidate vertices which vertex was queried. This work also presents a QR attack, but uses knowledge of the graph $G$ rather than partial knowledge of some queries.

2. Preliminaries

2.1. Notation

For an integer $n$ , let $[n]=\{1,2,\dots ,n\}$ . The concatenation of two strings $a$ and $b$ is denoted as $a||b$ .

A dictionary $\mathsf{D}$ is a map from some label space $\mathbb{L}$ to a value space $\mathbb{V}$ ; $\mathsf{D}[\mathsf{\text{lab}}]=\mathsf{\text{val}}$ indicates that $\mathsf{\text{lab}}\mapsto \mathsf{\text{val}}$ . A multimap $\mathsf{M}$ is a generalization of a dictionary that maps labels to sets of values.

2.2. Graphs

A graph is a pair $G=(V,E)$ consisting of a vertex set $V$ of size $n$ and an edge set $E$ of size $m$ . A graph is directed if the edges specify a direction from one vertex to another. Two vertices $u,v\in V$ are connected if there exists a path from $u$ to $v$ in $G$ . In this paper, it is assumed that all graphs $G$ are connected for simplicity. However, the attack and its constituent algorithms directly apply to multicomponent graphs.

A tree is a connected, acyclic graph. A rooted tree $T=(V,E,r)$ is a tree in which one vertex $r$ has been designated the root. For some rooted tree $T=(V,E,r)$ and vertex $v\in V$ , $T[v]$ denotes the subtree of $T$ induced by $v$ and all its descendants.

Given a graph $G=(V,E)$ and some vertex $v\in V$ , a single-destination shortest path (SDSP) tree for $v$ is a directed spanning tree $T$ such that $T$ is a subgraph of $G$ , $v$ is the only sink in $T$ , and each path from $u\in V\setminus \{v\}$ to $v$ in $T$ is a shortest path from $u$ to $v$ in $G$ . An example of an SDSP tree can be found in Figure 1(c).

Figure 1.

(a) Original graph $G$ , (b) its corresponding single-destination shortest path (SDSP) tree for vertex $1$ in $G$ with the canonical names labeling all the vertices of the tree, and (c) the matching query tree that is leaked during setup (without any vertex labels). (a) Original graph $G$ ; (b) SDSP tree for vertex $1$ ; and (c) the inferred leakage.

This work makes use of two binary options on graphs. Given two graphs $G=(V,E)$ and $H=(V^{\prime },E^{\prime })$ , the union of $G$ and $H$ is defined as $G\cup H=(V\cup V^{\prime },E\cup E^{\prime })$ . Given a graph $G=(V,E)$ and a subgraph $H=(V^{\prime },E^{\prime })$ such that $V^{\prime }\subseteq V,E^{\prime }\subseteq E$ , the graph subtraction of $H$ from $G$ is defined as $G\setminus H=(V\setminus V^{\prime },E\setminus E^{\prime })$ .

2.3. Hash functions

A set $H$ of functions $U\to [M]$ is a universal hash function family if, for every distinct $x,y\in U$ , the hash function family $H$ satisfies the following constraint:

$$\underset{h\leftarrow H}{Pr}[h(x)=h(y)]\le 1/M.$$

In Section 5, the universal hash function is instantiated using a cryptographic hash function.

2.4. Graph isomorphisms

The attack will make heavy use of graph isomorphisms and automorphisms. In particular, because the leakage profile of the GKT leaks the network topology of spanning subtrees of the original graph $G$ , recovery is information theoretically possible up to graphs with the same topology.

Definition 2.1

An isomorphism of graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ is a bijection between vertex sets $\phi :V_1\to V_2$ such that for all $u,v\in V_1,(u,v)\in E_1$ if and only if $(\phi (u),\phi (v))\in E_2.$ This can be succinctly denoted as $G_1\cong G_2$ .

Definition 2.2

An isomorphism of rooted trees $T_1=(V_1,E_1,r_1)$ and $T_2=(V_2,E_2,r_2)$ is an isomorphism $\phi$ from $T_1$ to $T_2$ (as graphs) such that $\phi (r_1)=r_2$ .

2.5. Canonical names

A canonical name $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}(\cdot )$ is an encoding mapping graphs to bit-strings such that, for any two graphs $H$ and $G$ , $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}(G)=\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}(H)$ if and only if $G\cong H$ . For rooted trees, AHU ¹⁵ describe an algorithm for computing a specific canonical name in $O(n)$ time. We refer to this as the canonical name and describe it next.

This work makes use of a modified AHU algorithm, denoted as $\mathrm{ComputeNames}$ , to compute the canonical names of rooted trees (and their subtrees) and determine if they are isomorphic. $\mathrm{ComputeNames}$ takes as input a rooted tree $T=(V,E,r)$ , a vertex $v\in V$ , and an empty dictionary $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}$ . It outputs the canonical name of the subtree $T[v]$ (which is also referred to as the canonical name of $v$ ) and a dictionary $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}$ that maps each descendant $u$ of $v$ to the canonical name of $T[u]$ . The algorithm proceeds from the leaves to the root. It assigns the name “ $10$ ” to all leaves of the tree. It then recursively visits each descendent $u$ of $v$ and assigns $u$ a name by sorting the names of its children in increasing lexicographic order, concatenating them into an intermediate name $children\mathrm{\_}names$ and assigning the name “ $1||children\mathrm{\_}names||0$ ” to $u$ (see Figure 1(b) for an example). The canonical name of $T$ , $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}(T)$ , is the name assigned to the root $r$ by this algorithm.

$\mathrm{ComputeNames}$ takes time and space $O(n^2)$ where $|V|=n$ . Note that the original AHU algorithm can be modified to run in $O(n)$ time by only considering one level at a time and reassigning integers to the vertices at that level. ¹⁵ In contrast, the attack must assign names to each vertex in the tree in order to later compute the path names, so we are forced to make use of the $O(n^2)$ version.

The pseudocode of $\mathrm{ComputeNames}$ can be found in Algorithm 1.

3. The GKT GES

This section gives an overview of the GES of Ghosh et al. ¹⁰ and its leakage.

3.1. GKT scheme overview

The GKT scheme supports single pair shortest path (SPSP) queries. The graphs may be directed or undirected, and the edges may be weighted or unweighted. An SPSP query on a graph $G=(V,E)$ takes as input a pair of vertices $(u,v)\in V\times V$ , and outputs a path $p_{u,v}=(u,w_1,\dots ,w_{\ell },v)$ such that $(u,w_1),(w_1,w_2),\dots ,(w_{t-1},v)\in E$ . This path must be of minimal length in $G$ , that is, there does not exist a sequence of edges $(u,w_1^{\prime }),(w_1^{\prime },w_2^{\prime }),\dots ,(w_{{t-1}^{\prime }}^{\prime },v)\in E$ such that $t^{\prime }<t$ .

SPSP queries may be answered using a number of different data structures. The GKT scheme makes use of the SP-matrix. ³⁹ For a graph $G=(V,E)$ , the SP-matrix $M$ is a $|V|\times |V|$ matrix defined as follows. Entry $M[i,j]$ stores the second vertex along the shortest path from vertex $v_i$ to $v_j$ ; if no such path exists, then it stores $\perp$ . An SPSP query $(v_i,v_j)$ is answered by computing $M[i,j]=v_k$ to obtain the next vertex along the path and then recursing on $(v_k,v_j)$ until $\perp$ is returned.

At a high level, the GKT scheme proceeds by computing an SP-matrix for the query graph and then using this matrix to compute a dictionary ${\mathsf{\text{SPDX}}}^{\prime }$ . This dictionary is then encrypted using a dictionary encryption scheme (DES) such as Cash et al. ⁴⁰ and Chase and Kamara. ⁸ To ensure that the GKT scheme is noninteractive, the underlying DES must be response-revealing. Since it is germane to this work, the syntax of a DES is described next.

Definition 3.1

A DES is a tuple of four algorithms $\mathsf{D}\mathsf{E}\mathsf{S}=$ $(\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{G}\mathsf{e}\mathsf{n}$ , $\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{E}\mathsf{n}\mathsf{c}\mathsf{r}\mathsf{y}\mathsf{p}\mathsf{t},\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n},$ $\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{G}\mathsf{e}\mathsf{t})$ with the following syntax:

$\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{G}\mathsf{e}\mathsf{n}$ is probabilistic and takes as input a security parameter $\lambda$ , and outputs a secret key $\mathsf{s}\mathsf{k}$ .

$\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{E}\mathsf{n}\mathsf{c}\mathsf{r}\mathsf{y}\mathsf{p}\mathsf{t}$ takes as input a secret key $\mathsf{s}\mathsf{k}$ and dictionary $\mathsf{D}$ , and outputs an encrypted dictionary ( $\mathsf{E}\mathsf{D}$ ).

$\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$ takes as input a secret key $\mathsf{s}\mathsf{k}$ and a label $\mathsf{\text{lab}}$ , and outputs a search token $\mathsf{\text{tk}}$ .

$\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{G}\mathsf{e}\mathsf{t}$ takes as input a search token $\mathsf{\text{tk}}$ and an $\mathsf{E}\mathsf{D}$ , and returns a plaintext value $\mathsf{\text{val}}$ .

Correctness for a $\mathsf{D}\mathsf{E}\mathsf{S}$ states that for all dictionaries $\mathsf{D}$ , for all keys $\mathsf{s}\mathsf{k}$ output by $\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{G}\mathsf{e}\mathsf{n}$ and for pairs $(\mathsf{\text{lab}},\mathsf{\text{val}})$ in $\mathsf{D}$ , executing $\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{G}\mathsf{e}\mathsf{t}$ on input $\mathsf{\text{tk}}=\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}(\mathsf{s}\mathsf{k},\mathsf{\text{lab}})$ and dictionary $\mathsf{E}\mathsf{D}=\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{E}\mathsf{n}\mathsf{c}\mathsf{r}\mathsf{y}\mathsf{p}\mathsf{t}(\mathsf{s}\mathsf{k},\mathsf{D})$ results in output $\mathsf{\text{val}}$ .

Note that while the GKT scheme itself is response-hiding (i.e. the shortest path is not returned in plaintext to the client), the underlying DES used in the scheme is response-revealing, that is, the values in its $\mathsf{E}\mathsf{D}$ are revealed at query time. The response-revealing property of the DES is necessary to enable the GKT scheme to operate in a noninteractive manner.

A more detailed description of the GKT scheme will now be provided. At setup, the client generates two secret keys: one for a symmetric encryption scheme $\mathsf{S}\mathsf{K}\mathsf{E}$ , and one for a $\mathsf{D}\mathsf{E}\mathsf{S}$ . It takes the input graph $G$ and computes the SP-matrix $M[i,j]$ . It then computes a dictionary $\mathsf{\text{SPDX}}$ such that for each pair of vertices $(v_i,v_j)\in V\times V$ , it sets $\mathsf{\text{SPDX}}[(v_i,v_j)]=(w,v_j)$ if $i\ne j$ and if in the SP-matrix $M[i,j]=w$ for some vertex $w$ .

The client then computes a second dictionary ${\mathsf{\text{SPDX}}}^{\prime }$ as follows. For each label-value pair $(\mathsf{\text{lab}},\mathsf{\text{val}})$ in $\mathsf{\text{SPDX}}$ , the following steps are carried out. A search token $\mathsf{\text{tk}}$ is computed from $\mathsf{\text{val}}$ using algorithm $\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$ and a ciphertext $c$ is computed by encrypting $\mathsf{\text{val}}$ using $\mathsf{S}\mathsf{K}\mathsf{E}.\mathsf{E}\mathsf{n}\mathsf{c}\mathsf{r}\mathsf{y}\mathsf{p}\mathsf{t}$ . Then ${\mathsf{\text{SPDX}}}^{\prime }[\mathsf{\text{lab}}]$ is set to $(\mathsf{\text{tk}},c)$ .

The resulting dictionary ${\mathsf{\text{SPDX}}}^{\prime }$ is then encrypted using $\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{E}\mathsf{n}\mathsf{c}\mathsf{r}\mathsf{y}\mathsf{p}\mathsf{t}$ to produce an output $\mathsf{E}\mathsf{D}\mathsf{B}$ , which is given to the server.

Now the client can issue an SPSP query for a vertex pair $(u,v)$ by generating a search token $\mathsf{\text{tk}}$ for $(u,v)$ and sending it to the server. The server initializes an empty string $\mathsf{r}\mathsf{e}\mathsf{s}\mathsf{p}$ and uses $\mathsf{\text{tk}}$ to search $\mathsf{E}\mathsf{D}\mathsf{B}$ and obtain a response $a$ . If $a=\perp$ , then it returns $\mathsf{r}\mathsf{e}\mathsf{s}\mathsf{p}$ . Otherwise, it parses $a$ as $({\mathsf{\text{tk}}}^{\prime },c)$ , updates $\mathsf{r}\mathsf{e}\mathsf{s}\mathsf{p}=\mathsf{r}\mathsf{e}\mathsf{s}\mathsf{p}||c$ and recurses on ${\mathsf{\text{tk}}}^{\prime }$ until $\perp$ is reached on look-up. The server returns $\mathsf{r}\mathsf{e}\mathsf{s}\mathsf{p}$ , a concatenation of ciphertexts (or $\perp$ ) to the client. The client then uses its secret key to decrypt $\mathsf{r}\mathsf{e}\mathsf{s}\mathsf{p}$ , obtaining a sequence of pairs $\mathsf{\text{val}}=(w_k,v)$ from which the shortest path from $u$ to $v$ can be constructed.

Complexity. The GKT scheme’s setup takes time $O(n^3)$ and is dominated by the cost of computing the SP-matrix. Token generation takes time $O(1)$ (assuming use of an efficient DES) and querying $\mathsf{E}\mathsf{D}\mathsf{B}$ takes time $O(t)$ where $t$ is the maximum length of a shortest path in $G$ . The server storage is $O(n^2)$ .

3.2. Leakage of the GKT scheme

Ghosh et al. ¹⁰ provide a formal specification of their scheme’s leakage. Informally, the setup leakage of their scheme is the number of vertex pairs in $G$ that are connected by a path, while the query leakage consists of the query pattern (which pairs of queries are equal), the path intersection pattern (the overlap between pairs of shortest paths seen in queries), and the lengths of the shortest paths arising in queries. See Section 4.1 in Ghosh et al. ¹⁰ for more details.

In the GKT scheme, the server obtains $\mathsf{E}\mathsf{D}\mathsf{B}$ by encrypting the underlying dictionary ${\mathsf{\text{SPDX}}}^{\prime }$ , in which labels are of the form $\mathsf{\text{lab}}=(v_i,v_j)$ and values are of the form $\mathsf{\text{val}}=(\mathsf{\text{tk}},c)$ , using a DES. Here $\mathsf{\text{tk}}$ is a search token obtained by running $\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$ on a pair $(w,v_j)$ and $c$ is obtained by running $\mathsf{S}\mathsf{K}\mathsf{E}.\mathsf{E}\mathsf{n}\mathsf{c}\mathsf{r}\mathsf{y}\mathsf{p}\mathsf{t}$ also on $(w,v_j)$ . Since $\mathsf{E}\mathsf{D}\mathsf{B}$ is obtained by running $\mathsf{D}\mathsf{E}\mathsf{S}$ on ${\mathsf{\text{SPDX}}}^{\prime }$ , this means that the labels in $\mathsf{E}\mathsf{D}\mathsf{B}$ are derived from tokens obtained by running $\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$ on inputs $\mathsf{\text{lab}}=(v_i,v_j)$ . Moreover, these tokens also appear in the values in $\mathsf{E}\mathsf{D}\mathsf{B}$ that are revealed to the server at query time, that is, in the entries $(\mathsf{\text{tk}},c)$ .

In turn, the query leakage reveals to the server the token used to initiate a search, as well as all the subsequent pairs $(\mathsf{\text{tk}},c)$ that are obtained by recursively processing such a query. Let us denote the sequence of search tokens associated with the processing of some (unknown) query $q$ for a shortest path of length $t$ as $s={\mathsf{\text{tk}}}_1\Vert {\mathsf{\text{tk}}}_2\Vert \dots \Vert {\mathsf{\text{tk}}}_{t+1}\in \{0,1{\}}^{*}$ . This string is referred to as the token sequence of $q$ . Since the search tokens correspond to the sequence of vertices in the queried path, there are as many tokens in the sequence as there are vertices in the shortest path. By correctness of $\mathsf{D}\mathsf{E}\mathsf{S}$ used in the construction of $\mathsf{E}\mathsf{D}\mathsf{B}$ , no two distinct queries can result in the same token sequence (in fact no two distinct queries can produce the same first token ${\mathsf{\text{tk}}}_1$ , since each such first token must be used to derive a unique label in $\mathsf{E}\mathsf{D}\mathsf{B}$ identifying the beginning of a specific shortest path).

Notice also that token sequences for different queries can be overlapping; indeed since the tokens are computed by running $\mathsf{D}\mathsf{E}\mathsf{S}.\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$ on inputs $\mathsf{\text{lab}}=(v_i,v),$ where $v$ is the final vertex of a shortest path, two token sequences are overlapping if and only if they correspond to queries (and shortest paths) having the same end vertex. Hence, given the query leakage of a set of queries, the adversary can compute all the token sequences and construct from them $n^{\prime }\le n$ directed trees, $\{Q_i{\}}_{i\in [n^{\prime }]}$ , each tree having at most $n$ vertices and a single root vertex. The vertices across all $n^{\prime }$ trees are labeled with the search tokens in $\mathsf{E}\mathsf{D}\mathsf{B}$ and there is a directed edge from $\mathsf{\text{tk}}$ to ${\mathsf{\text{tk}}}^{\mathrm{\prime }}$ if and only if $\mathsf{\text{tk}}$ and ${\mathsf{\text{tk}}}^{\mathrm{\prime }}$ are adjacent in some token sequence. (Each tree has at most $n$ vertices because of our assumption about $G$ being connected.)

This set of trees is called the query trees . Each query tree corresponds to the set of queries having the same end vertex. Each tree has a single sink (root) that corresponds to a unique vertex $v\in V$ . The tree paths correspond to the shortest paths from vertices $w\in V\setminus \{v\}$ to $v$ , such that $w$ and $v$ are connected in $G$ . Note that Ghosh et al. ¹⁰ also discuss these trees, but they do not analyze the theoretical limits of what can be inferred from them.

The leakage of the GKT scheme on a graph $G$ after issuing a set of SPSP queries $\mathcal{Q}$ is denoted as $\mathcal{L}(G,\mathcal{Q})$ . For a formal proof of security that establishes the leakage profile of the GKT scheme, please refer to Ghosh et al. ¹⁰ The attacks in this work are based only on the leakage of the scheme, as established above, and not on breaking the underlying cryptographic primitives of the scheme.

3.3. Implications of leakage

Suppose that all queries have been issued and that we have constructed all $n$ query trees $\{Q_i{\}}_{i\in [n]}$ , each tree having $n$ vertices. Observe that there exists a one-to-one matching between the query trees $\{Q_i{\}}_{i\in [n]}$ and the SDSP trees $\{T_v{\}}_{v\in V}$ of $G$ such that each matched pair of trees is isomorphic. The reason is that the query trees are just differently labeled versions of the SDSP trees; in turn, this stems from the fact that paths in the query trees are in 1–1 correspondence with the shortest paths in $G$ .

This now reveals the core of the QR attack, developed in detail in Section 4 below. The server with access to $G$ first computes all the SDSP trees offline. As queries are issued, it then constructs the query trees one path at a time. Once a complete query tree $Q$ is computed (recall that each query tree must have $n$ vertices since $G$ is connected), the server finds all possible isomorphisms between $Q$ and the SDSP trees. Then, for each token sequence in $Q$ , it computes the set of paths in the SDSP trees to which that token sequence can be mapped under the possible isomorphisms. This set of paths yields the set of possible queries to which the token sequence can correspond. This information is stored in a pair of dictionaries, which can be used to look-up the candidate queries.

To illustrate the core attack idea, Figure 1 depicts (Figure 1a) a graph $G$ , (Figure 1b) its SDSP tree for vertex $1$ (with vertex labels and canonical names), and (Figure 1c) the matching query tree (without vertex labels). It is then clear that the leakage from the unique shortest path of length 2 in Figure 1(c) can only be mapped to the corresponding path with edges $(4,5)$ , $(5,1)$ in Figure 1(b) under isomorphisms, and similarly the shortest path of length 1 that is a subpath of that path of length 2 can only be mapped to path $(5,1)$ . On the other hand, the three remaining paths of length 1 can be mapped under isomorphisms to any of the length 1 paths $(2,1)$ , $(3,1)$ , or $(6,1)$ and so cannot be uniquely recovered.

Since the adversary only learns the query trees and token sequences from the leakage, the degree of QR that can be achieved based on that leakage is limited. In particular, without auxiliary information, the adversary can only recover the candidate queries up to symmetries arising from the isomorphisms between the query trees and the SDSP trees. In practice, this is often not an issue since many queries result in only a very small number of candidate queries (see Section 5 for more details).

4. Query recovery (QR)

4.1. Threat model and assumptions

This work considers a passive, persistent, honest-but-curious adversary that has compromised the server and can observe the initial search token issued, all subsequent search tokens revealed during the query processing, and the response. In particular, the adversary could be the server itself. Appendix A outlines a modified version of the attack in which the adversary is assumed to have only compromised the communication channels between the client and server; this adversary can thus only see the search tokens used to initiate the recursive look-up and the server responses.

The adversary is assumed to know the graph $G$ that has been encrypted to create $\mathsf{E}\mathsf{D}\mathsf{B}$ . As noted previously, this is a strong assumption, but it fits within the security model used in Ghosh et al. ¹⁰ (where $G$ can even be chosen) and is realistic in many routing/navigation scenarios. It is further assumed that the adversary sees enough queries to construct a subset of the $n$ query trees. Computing all $n$ trees does not require observing all possible queries; in the real-world datasets tested, it was possible to construct all query trees with as few as $68.1\mathrm{\%}$ of the possible queries. This is because constructing a query tree that corresponds to $T_v$ only requires observing the queries that start at the leaf nodes of $T_v$ and end at $v$ . In SDSP trees with few leaves, only a small fraction of queries is needed.

It is assumed that the APSP algorithm used in constructing the SP-matrix from $G$ during setup is deterministic. Moreover, it is assumed that this algorithm is known to the adversary. Such an assumption is reasonable as the adversary knows $G$ and many shortest path algorithms are deterministic, including Floyd-Warshall ¹⁶ and many of its adaptations.

4.2. Formalizing QR attacks

QR in general is the goal of determining the plaintext value of queries that have been issued by the client. The notion of QR was introduced by Islam et al. ²⁴ in the context of leakage-abuse attacks on SSE schemes and has been extensively studied in the context of SSE and related schemes since.

This work studies the problem of QR in the context of GESs, specifically, the GKT scheme: given $G$ , the setup leakage of the GKT scheme and the query leakage from a set of SPSP queries, the adversary’s goal is to match the leakage for each SPSP query with the corresponding start and end vertices $(u,v)$ of a path in $G$ . As noted above, there may be a number of candidate queries that can be assigned to the leakage from each query. The adversary’s goals are formally described below.

Definition 4.1

(Consistency) Let $G=(V,E)$ be a graph, $\mathcal{Q}=\{q_1,\dots ,q_k\}$ be the set of SPSP queries that are issued, and $S=\{s_1,s_2,\dots ,s_k\}$ be the set of token sequences of the queries issued. An assignment $\pi :S\to V\times V$ is a mapping from token sequences to SPSP queries. An assignment $\pi$ is said to be consistent with the leakage $\mathcal{L}(G,\mathcal{Q})$ if it satisfies $\mathcal{L}(G,\mathcal{Q})=\mathcal{L}(G,\pi (S))$ .

Informally, consistency requires that, for each $s_i\in S$ , the query $\pi (s_i)$ specified by assignment $\pi$ could feasibly result in the observed leakage $\mathcal{L}(G,\mathcal{Q})$ .

Definition 4.2

(QR) Let $G=(V,E)$ be a graph, $\mathcal{Q}=\{q_1,\dots ,q_k\}$ be a set of SPSP queries, and $S$ the corresponding set of token sequences. Let $\mathrm{\Pi }$ be the set of all assignments consistent with $\mathcal{L}(G,\mathcal{Q})$ . The adversary achieves QR when it computes and outputs a mapping: $s\mapsto \{\pi (s):\pi \in \mathrm{\Pi }\}$ for all $s\in S$ .

The adversary achieves QR if, for each $s\in S$ (a set of token sequences resulting from queries in $\mathcal{Q}$ ), it outputs a set of query candidates $\{\pi (s):\pi \in \mathrm{\Pi }\}$ containing every query that is consistent with the leakage. Note that this implies that the output always contains the correct query (and possibly more). This is the best the adversary can do, given the available leakage.

There is some information not conveyed in this mapping. In particular, by fixing an assignment for a given token sequence, it may be possible to fix or reduce the possible assignments for other query responses. Such an example is given below.

Example 4.3

Suppose one observes the set of token sequences $\{s_i:i\in [5]\}$ such that $s_1,s_2,s_3,s_4$ correspond to paths of length 1 and $s_5$ corresponds to a path of length 2, with $s_4$ a subsequence of $s_5$ , and which allows one to construct the query tree in Figure 1(c). Further, suppose that the resulting query tree is not isomorphic to any other query tree. Thus, it is possible to infer that all queries in $S$ are rooted at 1. An adversary achieving QR must output the following mappings:

$$\begin{array}{rl}\{& s_1:\{(6,1),(3,1),(2,1)\},s_2:\{(6,1),(3,1),(2,1)\},\\ & s_3:\{(6,1),(3,1),(2,1)\},s_4:\{(5,1)\},s_5:\{(4,1)\}\}.\end{array}$$

However, if the adversary could fix the assignment $s_1$ to $(1,6)$ (e.g. by using auxiliary information), then $s_2$ could only be mapped to either $(1,3)$ or $(1,2)$ .

A special type of QR when there exists only one assignment consistent with the query leakage is now defined, that is, the case when all queries can be uniquely recovered.

Definition 4.4

(FQR) Let $G=(V,E)$ be a graph, $\mathcal{Q}=\{q_1,\dots ,q_k\}$ be a set of SPSP queries, and $S$ the corresponding set of token sequences. Let $\mathrm{\Pi }$ be the set of assignments consistent with $\mathcal{L}(G,\mathcal{Q})$ . An adversary is said to achieve FQR when it (a) achieves QR and (b) $|\mathrm{\Pi }|=1$ .

That is, there is a unique assignment of token sequences to queries consistent with the leakage. Whether FQR is always possible (i.e. for every possible set of queries $\mathcal{Q}$ ) depends on the graph $G$ . Specifically, FQR is always possible if and only if each SDSP tree arising in $G$ is nonisomorphic and every path in each SDSP tree is fixed by all automorphisms of the tree. It is easy to construct graphs for which these conditions hold (see Section 4.10). For such graphs, the QR attack always achieves FQR.

4.3. Technical results

This section develops some technical results concerning isomorphisms of trees and the behavior of paths under those isomorphisms that will be needed in the remainder of the paper.

For any rooted tree $T=(V,E,r)$ and any $u\in V$ , let $T[u]\subseteq T$ denote the subtree induced by $u$ and all its descendants in $T$ .

Lemma 4.5

Let $T=(V,E,r)$ and $T^{\prime }=(V^{\prime },E^{\prime },r^{\prime })$ be rooted trees. Let $p_{u,r}=(u,w_1,\dots ,w_t,r)$ and $p_{v,r^{\prime }}=(v,w_1^{\prime },\dots ,w_{\ell }^{\prime },r^{\prime })$ be paths in $T$ and $T^{\prime }$ , respectively. If there exists an isomorphism $\phi :T\to T^{\prime }$ such that $\phi (u)=v$ , then $t=\ell$ and $\phi (w_i)=w_i^{\prime }$ for all $i\in [t]$ .

Proof.

By assumption $\phi (u)=v$ and by definition of isomorphism of rooted trees $\phi (r)=r^{\prime }$ . Since $T$ is a tree, there exists a unique path between $u$ and $r$ , and between $v$ and $r^{\prime }$ . Isomorphisms of graphs must be edge preserving, and so $\phi$ must map the subgraph $p_{u,r}$ to $p_{v,r^{\prime }}$ . These two paths can only be isomorphic if they are the same length and thus $t=\ell$ . Putting together these two facts implies that

$$(\phi (u),\phi (w_1))=(v,w_1^{\prime }),(\phi (w_1),\phi (w_2))=(w_1^{\prime },w_2^{\prime }),\dots ,(\phi (w_t),\phi (r))=(w_t,r^{\prime })$$

which concludes the proof.

Given a rooted tree $T=(V,E,r)$ and any $u\in V$ , let ${\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}}_T(u)$ denote the concatenation of the canonical names of vertices along the path from $u$ to $r$ in $T$ , separated by semicolons:

$$\begin{array}{rl}{\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}}_T(u)=\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}(T[u])\Vert \text{``};\text{''}\Vert \mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}(& T[w_1])\Vert \text{``};\text{''}\Vert \dots \Vert \text{``};\text{''}\Vert \mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}(T[w_t])\Vert \text{``};\text{''}\Vert \mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}(T[r]).\end{array}$$

Computing path names will form the core of the QR attack. A sequence of results about the relationship between path names and isomorphisms will now be proven. Section 4.5 explains how to apply a universal hash function to the path names to compress their length from $O(n^2)$ to $O(\log n)$ bits, thereby reducing storage and run time complexity.

Proposition 4.6

Let $T=(V,E,r)$ and $T^{\prime }=(V^{\prime },E^{\prime },r^{\prime })$ be isomorphic rooted trees and let $C$ and $C^{\prime }$ denote the set of children of $r$ and $r^{\prime }$ , respectively. There is an isomorphism from $T$ to $T^{\prime }$ if and only if there is a perfect matching from $C$ to $C^{\prime }$ such that for each matched pair $c_i\in C,c_i^{\prime }\in C^{\prime }$ , there exists an isomorphism ${\phi }_i:T[c_i]\to T[c_i^{\prime }]$ .

Proof.

To see the forwards direction, let $\phi$ denote an isomorphism from $T$ to $T^{\prime }$ and note that if $\phi (c)=c^{\prime }$ for $c\in C$ , then by the edge-preservation property of isomorphisms, $\phi$ must map the vertices of $T[c]$ to the vertices of $T[c^{\prime }]$ , and thus $T[c]\cong T[c^{\prime }]$ . For the backwards direction, construct an isomorphism $\phi$ from $T$ to $T^{\prime }$ as follows. Let ${\phi }_r$ be the trivial isomorphism that takes $r$ to $r^{\prime }$ and let

$$\phi ={\phi }_1\cup {\phi }_2\cup \cdots \cup {\phi }_k\cup {\phi }_r.$$

Let $(a,b)\in E$ . If $(a,b)$ is an edge in $T[c_i]$ for some $c_i\in C$ then it is easy to see that by restricting $\phi$ to the vertices in $T[c_i]$ , we have that $(\phi (a),\phi (b))$ is an edge in $T^{\prime }[c_i^{\prime }]\subseteq T^{\prime }$ . If $(a,b)=(c_i,r)$ for some $c_i\in C$ , then $(\phi (c_i),\phi (r))=(c_i^{\prime },r^{\prime })$ . Since $c_i^{\prime }$ is a child of $r^{\prime }$ then $(\phi (a),\phi (b))\in E^{\prime }$ . A similar argument holds for showing that if $(a,b)\in E^{\prime }$ , then $({\phi }^{-1}(a),{\phi }^{-1}(b))\in E$ .

Lemma 4.7

Let $T=(V,E,r)$ and $T^{\prime }=(V^{\prime },E^{\prime },r^{\prime })$ be isomorphic rooted trees. Let $u$ and $v$ be children of $r$ and $r^{\prime }$ , respectively. Suppose that $\sigma$ is an isomorphism from $T[u]$ to $T^{\prime }[v]$ . Then there exists an isomorphism $\phi$ from $T$ to $T^{\prime }$ such that $\phi {|}_{T[u]}=\sigma$ and $\phi (u)=v$ .

Proof.

Let $C$ and $C^{\prime }$ denote the set of children of $r$ and $r^{\prime }$ , respectively. Since $\phi$ is an isomorphism and is edge preserving, then it must map $C$ to $C^{\prime }$ , and we necessarily have that $k=|C|=|C^{\prime }|$ .

Proposition 4.6 can now be used to prove the lemma. Let $\hat{\phi }$ be any isomorphism from $T$ to $T^{\prime }$ . If $\hat{\phi }$ maps $u$ to $v$ then the lemma holds. Otherwise, $\hat{\phi }(u)=c^{\prime }\ne v$ and ${\hat{\phi }}^{-1}(v)=c\ne u$ for some $c^{\prime }\in C^{\prime }$ and $c\in C$ . By Proposition 4.6, $T[u]\cong T^{\prime }[c^{\prime }]$ and $T[c]\cong T^{\prime }[v]$ , and by assumption $T[u]\cong T^{\prime }[v]$ . Thus, by transitivity, it follows that $T[c]\cong T^{\prime }[c^{\prime }]$ . Let $W$ be the vertices in $T\setminus (T[u]\cup T[c])$ and let $\pi$ be an isomorphism from $T[c]$ to $T^{\prime }[c^{\prime }]$ . Then $\phi =\hat{\phi }{|}_W\cup \sigma \cup \pi$ is a collection of isomorphisms on all the trees rooted at the children of the roots. Thus, $\phi$ is an isomorphism from $T$ to $T^{\prime }$ that maps $u$ to $v$ .

The main technical result can now be introduced:

Theorem 4.8

Let $T=(V,E,r)$ and $T^{\prime }=(V^{\prime },E^{\prime },r^{\prime })$ be rooted trees and let $u\in V$ and $v\in V^{\prime }$ . There exists an isomorphism $\phi :T\to T^{\prime }$ mapping $u$ to $v$ if and only if ${\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}}_T(u)={\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}}_{T^{\prime }}(v)$ .

Proof.

The forward direction follows from Lemma 4.5.

For the backward direction, suppose that ${\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}}_T(u)={\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}}_{T^{\prime }}(v)$ . Since a path name includes the canonical name of the entire tree, we deduce that $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}(T[r])=\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}(T^{\prime }[r^{\prime }])$ ; it follows that $T\cong T^{\prime }$ . Similarly, one can deduce that $T[u]\cong T^{\prime }[v]$ . More generally, let $p_{u,r}=(u,w_1,\dots ,w_{t-1},r)$ and $p_{v,r^{\prime }}=(v,w_1^{\prime },\dots ,w_{t-1}^{\prime },r^{\prime })$ be paths in $T$ and $T^{\prime }$ , respectively. Then for all $i\in [t-1]$ it must be that $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}(T[w_i])=\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}(T^{\prime }[w_i^{\prime }])$ .

The result will now be proven inductively on the vertices along the path from $u$ to $r$ . For the base case, take any isomorphism ${\phi }_0$ from $T[u]$ to $T^{\prime }[v]$ and note that this must necessarily map $u$ to $v$ .

This reasoning can be extended level-by-level upwards, at each stage using the equalities of components of the two path names to extend the isomorphism. Suppose that for $k\le t-1$ there exists an isomorphism ${\phi }_k$ from $T[w_k]$ to $T^{\prime }[w_k^{\prime }]$ such that ${\phi }_k(u)=v$ . By equality of path names, we have that $T[w_{k+1}]\cong T^{\prime }[w_{k+1}^{\prime }]$ . Note also that $w_k$ and $w_k^{\prime }$ are children of $w_{k+1}$ and $w_{k+1}^{\prime }$ , respectively. Applying Lemma 4.7, there exists an isomorphism ${\phi }_{k+1}$ from $T[w_{k+1}]$ to $T^{\prime }[w_{k+1}^{\prime }]$ such that ${\phi }_{k+1}{|}_{T[w_k]}={\phi }_k$ . Since $u$ is a vertex in $T[w_k]$ , it follows that ${\phi }_{k+1}(u)={\phi }_k(u)=v$ . This completes the induction and with it the proof.

Theorem 4.8 also gives a method for identifying when there exists only a single isomorphism between two rooted trees. Suppose that $T=(V,E,r)$ and $T^{\prime }=(V^{\prime },E^{\prime },r^{\prime })$ are isomorphic rooted trees and that every vertex $v\in V$ has a distinct path name; then there exists exactly one isomorphism from $T$ to $T^{\prime }$ . Intuitively, a vertex in $T$ can only be mapped to a vertex in $T^{\prime }$ with the same path name. So if path names are unique, then each vertex in $T$ can only be mapped to a single vertex in $T^{\prime }$ , meaning there is only a single isomorphism available. The converse also holds: if there exists exactly one isomorphism from $T$ to $T^{\prime }$ , then every vertex $v\in V$ necessarily has a distinct path name. This observation will be useful in characterizing when query reconstruction results in FQR. We summarize with:

Corollary 4.9

Let $T=(V,E,r)$ and $T=(V^{\prime },E^{\prime },r^{\prime })$ be isomorphic rooted trees. Every vertex $v\in V$ has a unique path name in $T$ if and only if there exists a single isomorphism from $T$ to $T^{\prime }$ .

4.4. Overview of the QR attack

Our QR attack takes as input the graph $G$ , a set of token sequences corresponding to the set of issued queries, and comprises the following steps:

(1)

Preprocess the graph offline (Algorithm 3). Compute the SDSP trees $\{T_v{\}}_{v\in V}$ of graph $G$ . Then construct a multimap $\mathsf{M}$ such that $\mathsf{M}$ maps each path name arising in the $T_v$ to the set of SPSP queries whose start vertices have the same path name.

(2)

Compute the query trees online. Construct the query trees from the token sequences as the queries are issued.

(3)

Process the query trees (Algorithm 4). Compute a dictionary $\mathsf{D}$ that maps each token sequence to the path name of the start vertex of the path.

Note that steps 4.4. and 4.4. are trivially parallelizable. In the case that the APSP algorithm is randomized, the adversary can simply run the attack multiple times to account for different shortest path trees.

In practice, the attack can output a single large table $T$ matching token sequences $s$ to sets of queries. However, storing this large table will be more expensive than storing $\mathsf{D}$ and $\mathsf{M}$ when $G$ has high symmetry. Moreover, $\mathsf{D}$ can be indexed by the first token $\mathsf{\text{tk}}$ in each token sequence $s$ (since $\mathsf{\text{tk}}$ uniquely determines the sequence).

The following subsections expand upon the steps in the above overview.

4.5. Computing the path names

Before diving into the attack, the algorithm for computing path names, which is used as a subroutine of the attack, is described. Algorithm 2 ( $\mathrm{ComputePathNames}$ ) takes as input a rooted tree $T=(V,E,r)$ and outputs a dictionary mapping each vertex $v\in V$ to its path name. First, Algorithm 1 ( $\mathrm{ComputeNames}$ ) is called on tree $T$ , its root $r$ , and an empty dictionary $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}$ , to obtain a dictionary $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}$ that maps each vertex $v\in V$ to the canonical name of subtree $T[v]$ .

A function $h$ drawn from a universal hash function family $H$ is used to compress the path names from $O(n^2)$ to $O(\log n)$ . An empty dictionary $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}$ is initialized and updated to include $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[r]=h(\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[r])$ . $T$ is then traversed in a depth-first search manner; when a new vertex $v$ is discovered during traversal, $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[v]$ is set to the hash of the concatenation of the name of $v$ and the path name of its parent $u$ , that is,

$$\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[v]=h(\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[v]\Vert \mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[u]).$$

(1)When all vertices have been explored, $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}$ is returned. The pseudocode for $\mathrm{ComputePathNames}$ can be found in Algorithm 2.

Theorem 4.10

Let $T=(V,E,r)$ be a rooted tree and $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}$ be the output of running Algorithm 2 on $T$ . Let $H$ be a universal hash function family mapping $\{0,1{\}}^{*}\to \{0,1{\}}^{6\log n}$ . Then, for randomly sampled $h\leftarrow H$ , the expected number of collisions in $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}$ is at most $O(1/n^3)$ .

Proof.

Let $u,v\in V$ be distinct and let $(u,w_1,\dots ,w_k,r=w_{k+1})$ and $(v,w_1^{\prime },\dots ,w_{k^{\prime }}^{\prime },r=w_{k^{\prime }+1})$ be paths in $T$ . Thus

$$\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[u]=h(\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[u]\Vert h(\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[w_1]\Vert h(\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[w_2]\Vert \cdots )))$$

and similarly for $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[v]$ . For there to be a collision between their path names then either: (1) $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[u]\Vert \mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[w_1]$ and $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[v]\Vert \mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[w_1^{\prime }]$ collide or (2) for some $i\in [min\{k,k^{\prime }\}]$ and $k,k^{\prime }\le n-2$ , it must be that $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[w_i]\Vert \mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[w_{i+1}]$ and $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[w_i^{\prime }]\Vert \mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[w_{i+1}^{\prime }]$ collide. Recall that a canonical name is unique up to isomorphism of the rooted tree.

Let $C_{uv}$ denote the event that the path names of $u$ and $v$ collide, and let $C_{uv}^j$ denote the event that the $j$ th nested hash of $u$ ’s and $v$ ’s path names collide. A collision on the path names occurs when any of the at most $n$ pairs of nested hash values (used to compute the path names of $u$ and $v$ ) collide. By definition of universal hash function, $\mathbb{E}[C_{uv}^j]<1/n^6$ and thus by linearity of expectation,

$$\mathbb{E}[C_{uv}]=\sum _{j=1}^{min\{k+1,k^{\prime }+1\}}\mathbb{E}[C_{uv}^j]<\frac{n}{n^6}=\frac{1}{n^5}.$$

Let $C$ denote the event of any collision of path names in $T$ . Then, by linearity of expectation, the expected number of collisions is

$$\mathbb{E}[C]=\sum _u\sum _v\mathbb{E}[C_{uv}]<\frac{n^2}{n^5}=\frac{1}{n^3}.$$

Corollary 4.11

Let $G=(V,E)$ be a graph and let $\{T_r{\}}_{r\in V}$ be the set of SDSP trees of $G$ . Let $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}$ be the union of the outputs of running Algorithm 2 on each tree in $\{T_r{\}}_{r\in V}$ . Let $H$ be a universal hash function family mapping $\{0,1{\}}^{*}\to \{0,1{\}}^{6\log n}$ . Then for randomly sampled $h\leftarrow H$ , the expected number of collisions in $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}$ is at most $O(1/n)$ .

To achieve a smaller probability of collision, one can choose a hash function family $H$ whose output length is $c\log n$ , where $c>6$ . For simplicity, the universal hash function is invoked using SHA-256 truncated to 128 bits.

Lemma 4.12

Let $T=(V,E,r)$ be a rooted tree on $n$ vertices and $H$ be a universal hash function family mapping $\{0,1{\}}^{*}\to \{0,1{\}}^{6\log n}$ . Upon input of $T$ , Algorithm 2 returns a dictionary of size $O(n\log n)$ mapping each $v\in V$ to a hash of its path name in time $O(n^2)$ .

Proof.

Correctness follows easily from Theorem 4.10 and by a recursive argument.

Calling $\mathrm{ComputeNames}$ (Algorithm 1) takes $O(n^2)$ time. Reading the name of the root $r$ and assigning the hash of its name takes at most time $O(n)$ . Every node is pushed onto the stack once, and thus the $\mathbf{w}\mathbf{h}\mathbf{i}\mathbf{l}\mathbf{e}$ loop on line 12 iterates $n$ times. Assigning a new path name on line 16 takes time $O(n)$ since $\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[v]$ is $O(n)$ bits, $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[u]$ is $O(\log n)$ bits, and computing the hash takes constant time. Pushing the children of a given vertex onto the stack takes time $O(n)$ for a total run time of $O(n^2)$ . $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}$ maps the vertices to the hash of their path names. Each vertex and its hashed path name can be encoded with $O(\log n)$ bits, yielding a dictionary of size $O(n\log n)$ .

4.6. Preprocess the graph

The original graph $G=(V,E)$ is first preprocessed into the $n$ SDSP trees. Since the adversary is assumed to have knowledge of $G$ , this step can be done offline. The same APSP algorithm used at setup is also used on $G$ to compute the $n$ SDSP trees $\{T_v{\}}_{v\in V}$ , where tree $T_v$ is rooted at vertex $v$ . For unweighted, undirected graphs, one can use breadth-first search for a total run time of $O(n^2+nm),$ where $m=|E|$ . For general weighted graphs, this step has a run time of $O(n^3)$ . ¹⁶

Next, the path names of each vertex in $\{T_r{\}}_{r\in V}$ are computed and a multimap $\mathsf{M}$ is constructed. $\mathsf{M}$ maps the (hashed) path name of each vertex in $\{T_r{\}}_{r\in V}$ to the set of SPSP queries whose start vertices have the same path name. Theorem 4.8 is leveraged to construct this map as described below.

An empty multimap $\mathsf{M}$ is initialized. For each $r\in V$ , $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}$ is computed by running Algorithm 2 ( $\mathrm{ComputePathNames}$ ) on tree $T_r$ . For each vertex $v$ in $T_r$ , $path\mathrm{\_}name\leftarrow \mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}[v]$ is computed and the label $path\mathrm{\_}name$ is looked up in $\mathsf{M}$ . If the label exists, then $\mathsf{M}[path\mathrm{\_}name]\leftarrow \mathsf{M}[path\mathrm{\_}name]\cup \{(v,r)\}$ . Otherwise $\mathsf{M}[path\mathrm{\_}name]\leftarrow \{(v,r)\}$ . The pseudocode for computing $\mathsf{M}$ can be found in Algorithm 3.

Lemma 4.13

Let $G=(V,E)$ be a graph on $n$ vertices. Upon input of $G$ , Algorithm 3 returns a multimap of size $O(n^2\log n)$ mapping each $v\in V$ to its corresponding path name in time $O(n^3)$ .

Proof.

For each vertex $r\in V$ , a dictionary mapping each vertex in $T_r$ to its respective path names is computed. The correctness of path names follows from Lemma 4.12.

The run time is now analyzed. Computing the all-pairs shortest path takes time $O(n^3)$ . The $\mathbf{f}\mathbf{o}\mathbf{r}$ loop on line 5 iterates through $n$ vertices. For each vertex in $V$ , running Algorithm 2 ( $\mathrm{ComputePathNames}$ ) takes $O(n^2)$ time and the inner $\mathbf{f}\mathbf{o}\mathbf{r}$ loop on line 9 takes $O(n)$ time. Thus, the $\mathbf{f}\mathbf{o}\mathbf{r}$ loop on line 5 takes a total time of $O(n^3)$ .

The multimap maps hashes of the path names to a list of candidate queries. The hashed path names have size $O(\log n)$ and there are at most $n^2$ distinct path names; each query corresponds to only one path name and is $O(\log n)$ bits long. The multimap thus has a total size $O(n^2\log n)$ .

4.7. Process the search tokens

The tokens revealed at query time must now be processed. Recall that the tokens are revealed such that the response to any shortest path query can be computed noninteractively. When a search token $\mathsf{\text{tk}}$ is sent to the server, the server recursively looks up each of the encrypted vertices along the path. The adversary can thus compute the query trees using the search tokens revealed at query time. First, it initializes an empty graph $F$ .

As label–value pairs $(\mathsf{\text{lab}},\mathsf{\text{val}})$ are revealed in $\mathsf{E}\mathsf{D}\mathsf{B}$ , the adversary parses ${\mathsf{\text{tk}}}_{\mathsf{\text{curr}}}\leftarrow \mathsf{\text{lab}}$ and $({\mathsf{\text{tk}}}_{\mathsf{\text{next}}},c)\leftarrow \mathsf{\text{val}}$ , and adds $({\mathsf{\text{tk}}}_{\mathsf{\text{curr}}},{\mathsf{\text{tk}}}_{\mathsf{\text{next}}})$ as a directed edge to $F$ . At any given time, $F$ will be a forest comprised of $n^{\prime }\le n$ trees, $\{Q_i{\}}_{i\in [n^{\prime }]}$ , such that each $Q_i$ has at most $n$ nodes. Identifying the individual trees in the forest can be done in time $O(n^2)$ . The adversary can compute the query trees online, and the final step of the attack can be run on any set of complete query trees. A complete query tree corresponds to the set of all queries to some fixed destination vertex. For ease of explanation, Algorithm 4 ( $\mathrm{QueryMapping}$ ) takes as input the set of all complete query trees that have been constructed from the leakage.

4.8. Map the token sequences to SPSP queries

In the last step, the set of complete query trees $\{Q_i{\}}_{i\in [n^{\prime }]}$ is used as input. The path names of each vertex in the $\{Q_i{\}}_{i\in [n^{\prime }]}$ are used to construct a dictionary $\mathsf{D}$ that maps each token sequence $s$ to the path name of the starting vertex of the corresponding path in its respective query tree. An empty dictionary $\mathsf{D}$ is initialized. For each complete query tree $Q_i$ , $\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{s}\leftarrow \mathrm{ComputePathNames}(Q_i)$ is computed and added to $\mathsf{D}$ . The pseudocode for computing $\mathsf{D}$ can be found in Algorithm 4.

Theorem 4.14

Let $G=(V,E)$ be a graph and $\mathsf{E}\mathsf{D}\mathsf{B}$ be an encryption of $G$ using the GKT scheme. Let $\{Q_i{\}}_{i\in [n^{\prime }]}$ be the query trees constructed from the leakage of queries issued to $\mathsf{E}\mathsf{D}\mathsf{B}$ . Upon input of $G$ , Algorithm 3 returns a dictionary $\mathsf{M}$ mapping each path name to a set of SPSP queries in time $O(n^3)$ . Upon input of $G$ and $\{Q_i{\}}_{i\in [n^{\prime }]}$ , Algorithm 4 returns a dictionary $\mathsf{D}$ mapping token sequences to path names in time $O(n^3)$ . Moreover, the outputs $\mathsf{D}$ and $\mathsf{M}$ have the property that, for any token sequence $s$ corresponding to a path $(v,r)$ in a query tree and for every query $(v^{\prime },r^{\prime })\in \mathsf{M}[\mathsf{D}[s]]$ , there exists an isomorphism $\phi$ from $Q$ to $T_{r^{\prime }}$ such that $\phi (v)=v^{\prime }$ and $\phi (r)=r^{\prime }$ .

Proof.

The correctness of $\{Q_i{\}}_{i\in [n]}$ follows from the correctness of the GKT scheme. Dictionary $\mathsf{D}$ contains a map of each vertex in ${\cup }_{i\in [n]}{Q}_i$ to its path name. The correctness of $\mathsf{M}$ and $\mathsf{D}$ follows from Lemmas 4.13 and 4.12, respectively.

Let $(v,r)$ be a pair comprised of a nonroot vertex $v$ and a root vertex $r$ in a complete query tree $Q$ , and let $s$ be the token sequence corresponding to $(v,r)$ . Let $(v^{\prime },r^{\prime })\in \mathsf{M}[\mathsf{D}[s]]$ . By composition of $\mathsf{D}$ and $\mathsf{M}$ , it must be that ${\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}}_Q(v)={\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}}_{T_{r^{\prime }}}(v^{\prime })$ . Applying Theorem 4.8, there is thus an isomorphism from $Q$ to $T_{r^{\prime }}$ that maps $v$ to $v^{\prime }$ and $r$ to $r^{\prime }$ .

With regard to run time, preprocessing $G$ (Algorithm 3) takes time $O(n^3)$ . Computing the path names (Algorithm 2) of $n^{\prime }\le n$ trees takes $O(n^3)$ time, which is an upper bound on the run time of the whole attack.

4.9. Recover the queries

Once the map between each node (token) in a query tree and its corresponding path name has been computed, the attacker can use $\mathsf{M}$ and $\mathsf{D}$ to compute the candidate queries of all queries in the complete query trees. Given $\mathsf{M}$ and $\mathsf{D}$ (outputs of Algorithms 3 and 4, respectively) and an observed token $s$ matching a query in the query trees for some unknown query, the adversary can find the set of queries consistent with $s$ by simply computing $\mathsf{M}[\mathsf{D}[s]]$ .

4.10. Full query recovery (FQR)

This section is concluded with a discussion of when FQR is possible. By the correctness of the attack, this is the case for a graph $G$ , a set of complete query trees $\{Q_i{\}}_{i\in [n^{\prime }]}$ , and associated token sequences $S$ when for $\mathsf{M}\leftarrow \mathrm{PreprocessGraph}(G)$ , $\mathsf{D}\leftarrow \mathrm{QueryMapping}(G,\{Q_i{\}}_{i\in n^{\prime }})$ , and all $s\in S$ , $|\mathsf{M}[\mathsf{D}[s]]|=1$ .

A condition for FQR feasibility can also be described in graph-theoretic terms. Recall Corollary 4.9, which states that given two isomorphic rooted trees $T$ and $T^{\prime }$ , if each vertex in $T$ has a unique path name, then there exists only one isomorphism from $T$ to $T^{\prime }$ . FQR is thus always achievable for any set of complete query trees, when all $n^2$ vertices in the SDSP trees have unique path names. More formally:

Corollary 4.15

Let $G=(V,E)$ be a graph and let $\{T_v{\}}_{v\in V}$ be the set of SDSP trees of $G$ . Suppose every vertex in $\bigcup _{v\in V}{T}_v$ has a unique path name (and in particular, each $T\in \{T_v{\}}_{v\in V}$ has a unique canonical name). Then, FQR can always be achieved on any complete query tree(s). The converse is also true.

By correctness, the attack achieves FQR whenever it is possible. Figure 2 depicts a graph for which FQR is always possible. Indeed, each tree $\{T_v{\}}_{v\in [7]}$ has a unique canonical name, and for all $v\in [7]$ , each vertex $u$ in $T_v$ has a unique path name. More generally, let $\mathcal{G}$ be the family of graphs having one central vertex $c$ and any number of paths all of distinct lengths appended to $c$ . It is easy to see that the attack achieves FQR for all graphs $G\in \mathcal{G}$ .

Figure 2.

An example graph for which FQR is always possible, no matter which set of SPSP queries is issued. FQR: full query recovery; SPSP: single pair shortest path.

5. Experiments

The theoretical results are supported by experiments on both real-world datasets and random graphs.

5.1. Implementation details

The attack was implemented in Python 3.7.6 and ran on a computing cluster with a $2\times 28$ Core Intel Xeon Gold 6258R 2.7 GHz Processor (Turbo up to 4 GHz/AVX512 Support), and 384 GB DDR4 2933 MHz error correcting code memory. To generate the leakage, the GES from Ghosh et al. ¹⁰ was implemented, and the same machine for both the client and server was used. The cryptographic primitives were implemented using the PyCryptodome library version 3.10.1 ⁴¹ ; AES-CBC with a 16B key was used for symmetric encryption, and SHA-256 was used for collision-resistant hash functions SHA-256. For the DES, ${\mathrm{\Pi }}_{bas}$ from Cash et al. ⁴⁰ was implemented, and the tokens were generated using hash-based message authentication code with SHA-256 truncated to 128 bits. The shortest paths of the graphs were computed using the single_source_shortest_path algorithm from the NetworkX library version 2.6.2. ⁴²

The QR attack was implemented using the same shortest path algorithm from NetworkX as in the scheme implementation. An implementation of the AHU algorithm (Algorithm 1) was used to compute canonical names. As mentioned previously, the attack is highly parallelizable, and this property was exploited when implementing the attack.

5.2. Graph datasets

The attack was evaluated on six of the same datasets as Ghosh et al. ¹⁰ ; in addition, the InternetRouting dataset from the University of Oregon Route Views Project (collected on 2 January 2000) and the facebook-combined dataset were also used. All eight of these datasets were obtained from Leskovec and Krevl. ⁴³ The InternetRouting and CA-GrQc datasets were extracted from the original datasets using the dense subset extraction algorithm by Charikar ⁴⁴ as implemented by Ambavi et al. ⁴⁵ Details about these datasets can be found in Table 1, and a summary of the attack results can be found in Table 2.

Table 1.

A description of the real-world datasets used in the experimental evaluation; $n$ denotes the number of vertices; $m$ denotes the number of edges of the graph dataset; $d=2m/(n\cdot (n-1))$ denotes the density of the graph.

Dataset	$\mathit{n}$	$\mathit{m}$	$\mathit{d}$	# Comp
InternetRouting	35	323	0.543	1
CA-GrQc	46	1030	0.995	1
Email-Eu-core	1005	16,706	0.0331	20
Facebook-combined	4039	88,234	0.011	1
p2p-Gnutella08	6301	20,777	0.001	2
p2p-Gnutella04	10,876	39,994	0.0006	1
p2p-Gnutella25	22,687	54,705	0.0002	13
p2p-Gnutella30	36,682	88,328	0.0001	12

Table 2.

A comparison of the attack results for the real-world datasets.

					Percentile
Dataset	$\frac{\text{\# Unique}}{\text{Total}}$	% Unique	$\frac{\text{\# Leaves in SDSP trees}}{\text{\# Nodes in SDSP trees}}$	% Min	50	90	99
InternetRouting	$\frac{28}{1190}$	2.353	$\frac{1120}{1190}$	94.1	40	84	90
CA-GrQc	$\frac{3}{2070}$	0.145	$\frac{2065}{2070}$	99.8	1845	1845	1845
Email-EU-core	$\frac{65,659}{1,009,020}$	6.507	$\frac{787,486}{1,009,020}$	78.0	16	69	190
Facebook-combined	$\frac{33,634}{16,309,482}$	0.206	$\frac{16,194,084}{16,309,482}$	99.3	1826	11,424	20,480
p2p-Gnutella08	$\frac{8,519,868}{39,696,300}$	21.463	$\frac{27,663,800}{39,696,300}$	69.7	4	12	64
p2p-Gnutella04	$\frac{25,915,785}{118,276,500}$	21.911	$\frac{80,580,827}{118,276,500}$	68.1	3	9	32
p2p-Gnutella25	$\frac{82,736,533}{514,677,282}$	16.075	$\frac{379,383,168}{514,677,282}$	73.7 %	5	18	54
p2p-Gnutella30	$\frac{197,413,906}{1,345,532,442}$	14.671	$\frac{1,003,317,663}{1,345,532,442}$	74.6	5	24	60

SDSP: single-destination shortest path; QR: query recovery.

The third column denotes the fraction of queries that are recoverable up to one candidate. The fourth column denotes the smallest fraction of queries needed to reconstruct all query trees. The last three columns show the 50th, 90th, and 99th percentiles obtained for QR on the eight real-world datasets.

In addition to the real-world datasets, the attack was also deployed on random graphs for $n=100,250,500,1000$ and edge probabilities $p=0.2,0.4,0.6,0.8$ . The graphs were generated using the fast_gnp_random_graph function from NetworkX. ⁴²

5.3. Query reconstruction results

Real-world datasets. The attack was carried out on the Internet Routing, CA-GrQc, email-EU-Core, facebook-combined, and p2p-Gnutella08 datasets; the online portion of the attack (Algorithm 4) given all queries ran in 0.087 s, 0.093 s, 5.807 s, 102.670 s, and 339.957 s for each dataset, respectively. For the first four datasets, attacks given 75% and 90% were also run. The results were averaged over 10 runs, and the vertices were sampled as follows: the start vertex was chosen uniformly at random, and the end vertex was chosen with probability linearly proportional to its out degree in the original graph. This simulates a more realistic setting in which certain “highly connected” destinations are chosen with higher frequency. The results of these experiments can be found in Table 3. Queries can be reconstructed with just 75% of the queries. In fact, for the Facebook-combined dataset, complete query trees can be observed with high probability after only observing 20% of the queries.

For the remaining datasets, simulations were run to demonstrate the success that an adversary could achieve given 100% of the queries. The simulations were carried out as follows. Given $G$ , the SDSP trees and the path names for each vertex in these trees were computed, and then a dictionary mapping each query in $G$ to the set of candidate queries was constructed by identifying queries whose starting vertices have the same path name. The simulations only used the plaintext graph, and the results show the success that an adversary would achieve in an end-to-end attack. Simulations were used for the larger graphs since storing all responses is memory-intensive; in practice, the attack can be run on larger datasets by writing the map out to a back-end key-value store. These results can be found in the bottom row of Table 3.

Table 3.

CDFs for QR of the real-world data sets after observing (row 1) 75%, (row 2) 90%, and (rows 3 and 4) 100% of the queries.

Table 1 reports the percentage of uniquely recoverable queries when the attack is run on the set of all query trees. Uniquely recoverable queries are queries whose responses result in only one candidate. CA-GrQc had the smallest percentage of uniquely recoverable queries (0.145%) and the p2p-Gnutella04 had the largest percentage (21.911%). The small percentage for CA-GrQc can be attributed to its high density ( $d=0.995$ ), where density is defined as $d=2m/(n\cdot (n-1))$ . The CA-GrQc graph is nearly complete, and its SDSP trees display a high degree of symmetry. In fact, many of the query trees are isomorphic to the majority of SDSP trees, and the majority of SDSP trees have a star shape (i.e. $n-1$ of the vertices in the tree are adjacent to the root). Each nonroot vertex in a star tree has the same path name, resulting in a large number of possible candidates per token sequence.

Table 3 depicts the cumulative distribution functions (CDFs) resulting from the experiments. The four Gnutella datasets exhibit a high recovery rate that can be explained by asymmetry and low density. Fifty percent of all queries for the p2p-Gnutella08, p2p-Gnutella04, p2p-Gnutella25, and p2p-Gnutella30 datasets result in at most 4, 3, 5, and 5 candidate query values, respectively. Details of the 50th, 90th, and 99th percentiles can be found in Table 1. The histograms of the results for QR on the real-world datasets (assuming 100% of the queries have been observed) are depicted in Table 4.

Random graphs. The attack was also deployed on random graphs, varying the number of nodes ( $n=100,250,500,1000$ ) and the edge probability ( $p=0.2,0.4,0.6,0.8$ ). QR was carried out after all queries had been issued. For each $(n,p)$ pair, 50 random graphs were generated and encrypted using the GKT scheme. The leakage for all possible SPSP queries was then generated, and the server-side QR attack was deployed on the responses. For each recovered multimap, the average number of candidate queries across all 50 graphs was computed. The CDFs of these results can be found in Table 5. The attack executed very quickly, with runtimes ranging from 0.471 s on graphs with $n=100$ to $46.2$  s on graphs with $n=1000$ .

Table 4.

Histograms for quick recovery (QR) of the real-world datasets after observing 100% of the queries.

The number of candidate queries output by QR is plotted on the $x$ axis, and the number of queries is plotted on the $y$ -axis. The red dotted lines indicate the 50th, 90th, and 99th percentiles. An asterisk next to the dataset indicates that results were obtained via simulation; see the discussion for details.

Table 5.

CDFs for QR of random graphs for $n=100,250,500,1000$ and $p=0.2,0.4,0.6,0.8$ after observing 100% of the queries.

CDF: cumulative distribution function; QR: query recovery.

The number of candidate queries output by the QR attack was plotted on the $x$ -axis, and the percentage of total queries was plotted on the $y$ axis. For each $(n,p)$ , 50 graphs were generated, and an average of the number of vertices with each given set size of candidate queries was taken. As the edge probability increases, the number of symmetries, and hence the number of candidate queries output, tends to increase.

Table 6.

PDFs for QR of random graphs after observing 100% of the queries.

PDF: probability density function; QR: query recovery.

The number of candidate queries output by the QR attack is plotted on the $x$ -axis, and the percentage of total queries is plotted on the $y$ -axis.

In general, an increase in $p$ and $n$ both result in an increase in the size of the maximum query candidate sets. For example, for $n=100,p=0.2$ , $6.3\mathrm{\%}$ of all queries are uniquely recoverable and $50\mathrm{\%}$ of all queries are recoverable to at most 10 candidate queries (representing $0.101\mathrm{\%}$ of all queries). For $n=1000,p=0.2$ , $1.5\mathrm{\%}$ of all queries are uniquely recoverable and $50\mathrm{\%}$ of all queries are recoverable to at most 107 candidate queries (representing $0.0107\mathrm{\%}$ of all queries).

As $p$ increases from $0.2$ to $0.8$ , the graphs become more dense, and a similar trend as seen in the real-world datasets can be observed. Denser graphs are closer to complete, and result in more symmetries and larger candidate query sets. As $p$ increases, more “waves” in the CDFs can also be observed; in the graphs showing the probability density functions (Table 6), these correspond to large clusters of candidate queries, all of which have the same path name and hence cannot be distinguished.

6. Discussion

This work describes a QR attack against the GKT GES from Ghosh et al. ¹⁰ The attack model considered is strong, but fits within the model used in Ghosh et al. ¹⁰ The attack begins with an offline preprocessing phase of the graph. In the online phase, the attack waits until it has observed all queries to at least one destination vertex and then outputs a list of candidates for each of these queries. The attack has the property that the output contains everything consistent with the leakage (and nothing more), and always contains the correct query. The attack was supported with a precise characterization of when FQR is possible, and evaluated against real-world and random graphs.

An alternative setting is to consider query reconstruction when arbitrary subsets of queries have been issued: then the adversary can construct partial query trees and attempt to identify isomorphic embeddings of them into the SDSP trees. It is an interesting open problem to develop an efficient attack for this setting. Yet another variant of the attack, for a network adversary, is described in Appendix A.

This paper highlights the need for detailed cryptanalysis of GESs. The value of such analysis was recognized in Ghosh et al., ¹⁰ but omitted on the grounds that the impact of the leakage is application-specific and can only be assessed in the context of particular use cases at the time of deployment. Such analysis, however, should be done in tandem with security proofs (establishing leakage profiles) at the same time as schemes are developed. Of course, attacks should be assessed with respect to real-world datasets whenever possible, as done here.

This work leaves open the question of whether other GESs can be similarly attacked. On the constructive side, the question of whether more secure schemes can be built that utilize chaining in a noninteractive manner and which support shortest path queries remains open. Another interesting line of research includes constructing practical interactive graph database schemes that minimize the communication overhead and number of rounds between the client and the server. Moreover, there is still much work to be done regarding the design of encrypted graph database schemes that can support a variety of queries—an important property for schemes in practical settings.