Graph Encryption for Shortest Path Queries with k Unsorted Nodes

Graph Encryption for Shortest Path Queries with k Unsorted Nodes

Li, Meng (Hefei University of Technology)
Gao, Jianbo (Hefei University of Technology)
Zhang, Zijian (Beijing Institute of Technology)
Fu, Chaoping (Huaqiao University)
Lal, C. (TU Delft Cyber Security)
Conti, M. (Università degli Studi di Padova)

2022

Shortest distance queries over large-scale graphs bring great benefits to various applications, i.e., save planning time and travelling expenses. To protect the sensitive nodes and edges in the graph, a user outsources an encrypted graph to an untrusted server without losing the query ability. However, no prior work has considered the user requirement of the shortest path with k unsorted nodes. In particular, we are concerned with how to securely find the shortest path by passing k nodes that do not have a fixed traverse order. To solve the problems, we propose Gespun (stands for Graph encryption for shortest path queries with k unordered nodes). It includes an oracle encryption scheme that is provably secure against the semi-honest server. Specifically, we compute the shortest paths and distances for all nodes locally to obtain path-distance oracles. We transform the shortest paths to a sequence of secure codes by using a pseudo-random permutation to protect the structure privacy. We encrypt the shortest distance by using additively homomorphic encryption. Second, we pack the oracles in link-list nodes and store them in an array-based dictionary after another permutation. Next, we construct a search graph to compute the shortest path while guaranteeing that the path passes the required k nodes. We formally prove that Gespun is adaptively semantically-secure in the random oracle. We implement a prototype of Gespun and evaluate its performance. Experiments results demonstrate that Gespun is efficient, e.g., a query over 6301 nodes, 20777 edges, and 5 unsorted nodes only needs 483 ms to get queried results. We believe that our research problem span new research that soon promotes a new line of graph encryption schemes.

Graph encryption
Security
Shortest distance query
Unsorted nodes

http://resolver.tudelft.nl/uuid:259442d8-cfc6-48e7-b548-8675e9695042

https://doi.org/10.1109/TrustCom56396.2022.00023

IEEE

2023-07-01

9781665494250

Proceedings - 2022 IEEE 21st International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2022

21st IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2022, 2022-12-09 → 2022-12-11, Virtual, Online, China

Proceedings - 2022 IEEE 21st International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2022

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Institutional Repository

conference paper

© 2022 Meng Li, Jianbo Gao, Zijian Zhang, Chaoping Fu, C. Lal, M. Conti