cipherPath: Efficient traversals over homomorphically encrypted paths

We propose cipherPath, a novel graph encryption scheme that enables exact shortest distance queries on encrypted graphs. Shortest distance queries are very useful in a vast number of applications, including medical, social or geospatial. Our approach using somewhat homomorphic encryption in combination with structured encryption enables exact shortest distance queries on outsourced and encrypted graph data. Our approach upholds provable security against a semi-honest provider. We demonstrate our framework by means of two different shortest path algorithms on encrypted graphs: Dijkstra and Floyd. Finally, we evaluate the leakage profile of cipherPath.