Privacy Preserving Shortest Path Queries on Directed Graph

Abstract

Trust relation in this work refers to permission that is given to a user at source-host to access another user at target-host through an authentication key with a unique fingerprint. We form a directed graph out of these trust relations, such that user-host pairs are considered as nodes and fingerprints as arrows. We present a novel protocol to query the shortest path from node A to node B, in a privacy preserving manner. We would like to use a cloud to perform such queries, but we do not allow the cloud to learn any information about the graph, nor the query. Also the database owner is prevented from learning any information about the query, except that it happened.

Keywords

• Cryptography
• Privacy-enhancing technology
• Cloud computing
• Private information retrieval
• Directed graph
• Shortest path queries