Options
2020
Conference Paper
Titel
cipherPath: Efficient traversals over homomorphically encrypted paths
Abstract
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.