Francesca Falzon, University of Chicago
From 12.00 until 13.30
At CNB/F/110 (Lunch) + CAB H 52 (Seminar), ETH Zurich
CNB/F/110 (Lunch) + CAB H 52 (Seminar), ETH Zurich
Abstract:
Plaintext graph database systems have already received much attention in both industry and academia. With the rise of data storage outsourcing and, consequently, data breaches, there is an increased interest in Graph Encryption Schemes (GES). A GES enables a client to encrypt a graph, outsource the storage of the encrypted graph to an untrusted server, and to make certain types of graph queries to the server.
Ghosh, Kamara and Tamassia (ASIA CCS 2021) presented a GES that supports shortest path queries. That is, the client can query two nodes in the encrypted graph G and receive from the server an (encrypted) response containing the shortest path in G between the two given nodes. We show how a passive, persistent, server-side adversary can mount an attack against this GKT scheme and recover the plaintext query values after observing 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. 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.
Join us in CNB/F/110 (Lunch) + CAB H 52 (Seminar).