Abstract
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.
Original language | English |
---|---|
Title of host publication | Proceedings - 2022 IEEE 21st International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2022 |
Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
Pages | 89-96 |
Number of pages | 8 |
ISBN (Electronic) | 9781665494250 |
DOIs | |
Publication status | Published - 2022 |
Event | 21st IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2022 - Virtual, Online, China Duration: 9 Dec 2022 → 11 Dec 2022 |
Publication series
Name | Proceedings - 2022 IEEE 21st International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2022 |
---|
Conference
Conference | 21st IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2022 |
---|---|
Country/Territory | China |
City | Virtual, Online |
Period | 9/12/22 → 11/12/22 |
Bibliographical note
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-careOtherwise 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.
Keywords
- Graph encryption
- Security
- Shortest distance query
- Unsorted nodes