Paper 2024/845

PathGES: An Efficient and Secure Graph Encryption Scheme for Shortest Path Queries

Francesca Falzon, ETH Zurich
Esha Ghosh, Microsoft Research (USA)
Kenneth G. Paterson, ETH Zurich
Roberto Tamassia, Brown University
Abstract

The increasing importance of graph databases and cloud storage services prompts the study of private queries on graphs. We propose PathGES, a graph encryption scheme (GES) for single-pair shortest path queries. PathGES is efficient and mitigates the state-of-the-art attack by Falzon and Paterson (2022) on the GES by Ghosh, Kamara, and Tamassia (2021), while only incurring an additional logarithmic factor in storage overhead. PathGES leverages a novel data structure that minimizes leakage and server computation. We generalize what it means for one leakage function to leak less than another by defining a relation with respect to a family of query sequences and show that our scheme provably leaks less than the GKT scheme when all queries have been issued. We complement our security proof with a cryptanalysis that demonstrates an information-theoretic gap in the size of the query reconstruction space of our scheme as compared to the GKT scheme and provide concrete examples of the gap for several graph families. Our prototype implementation of PathGES is efficient in practice for real-world social network and geographic data sets. In comparison with the GKT scheme, PathGES has on average the same response size and up to 1.5$\times$ faster round-trip query time.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. ACM CCS 2024
Keywords
Encrypted DatabasesSearchable EncryptionGraph Encryption
Contact author(s)
ffalzon @ ethz ch
esha ghosh @ microsoft com
kenny paterson @ inf ethz ch
roberto @ tamassia net
History
2024-07-19: last of 2 revisions
2024-05-29: received
See all versions
Short URL
https://ia.cr/2024/845
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/845,
      author = {Francesca Falzon and Esha Ghosh and Kenneth G. Paterson and Roberto Tamassia},
      title = {{PathGES}: An Efficient and Secure Graph Encryption Scheme for Shortest Path Queries},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/845},
      year = {2024},
      url = {https://eprint.iacr.org/2024/845}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.