PathGES: An Efficient and Secure Graph Encryption Scheme for Shortest Path Queries
Open access
Date
2024Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
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 the same response size on average and up to 1.5x faster round-trip query time. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000682991Publication status
acceptedExternal links
Publisher
Association for Computing MachineryEvent
Subject
cryptography; Graph Database; Encrypted Database; Searchable EncryptionOrganisational unit
02660 - Institut für Informationssicherheit / Institute of Information Security09653 - Paterson, Kenneth / Paterson, Kenneth
More
Show all metadata
ETH Bibliography
yes
Altmetrics