Efficient Graph Encryption Scheme for Shortest Path Queries

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. Our scheme is the first structured encryption scheme that supports a recursive algorithm, where the number of recursion steps is not known at setup time (unlike the chaining technique from [Chase and Kamara, 2010]). Recursion is an important algorithmic design paradigm. Hence, our technique may help develop other practical encrypted structures for recursive algorithms.