An efficient query recovery attack against a graph encryption scheme
Francesca Falzon, Kenneth G. Paterson · Journal of Computer Security · 2025
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.