Paper 2022/838

An Efficient Query Recovery Attack Against a Graph Encryption Scheme

Francesca Falzon, Brown University, University of Chicago
Kenneth G. Paterson, ETH Zurich

Ghosh, Kamara and Tamassia (ASIA CCS 2021) presented a Graph Encryption Scheme supporting shortest path queries. We show how to perform a query recovery attack against this GKT scheme when the adversary is given the original graph together with the leakage of certain subsets of queries. Our attack falls within the security model used by Ghosh et al., and is the first targeting schemes supporting shortest path queries. Our 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 pre-compute the set of candidate queries that match each response. Then, 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, our attack runs in time $O(n^3)$ and matches the time complexity of the GKT scheme's setup. We evaluate the attack's performance using the real world datasets used in the original paper and on random graphs, and show that for the real-world datasets as many as 21.9% of the queries can be uniquely recovered and as many as 50% of the queries result in sets of only three candidates.

Available format(s)
Attacks and cryptanalysis
Publication info
encrypted databases leakage-abuse attacks cryptanalysis
Contact author(s)
francesca_falzon @ brown edu
kenny paterson @ inf ethz ch
2022-06-27: approved
2022-06-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Francesca Falzon and Kenneth G. Paterson},
      title = {An Efficient Query Recovery Attack Against a Graph Encryption Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2022/838},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.