Efficient Graph Encryption Scheme for Shortest Path Queries
Esha Ghosh, Seny Kamara, Roberto Tamassia
Abstract
Graph encryption schemes (introduced by [Chase and Kamara, 2010]) have been receiving growing interest across various disciplines due to their attractive tradeoff between functionality, efficiency and privacy. In this paper, we advance the state of the art on encrypted graph search by providing an efficient graph encryption scheme for shortest path queries. The preprocessing time and space and the query time are proportional to those for building and querying the search structure for the unencrypted graph. Hence, the overhead of providing structured encryption is asymptotically optimal. We implement our scheme and experimentally validate its performance on real world networks. Furthermore, we extend our scheme to support verifiability.