Efficient shortest distance approximate query on large scale encrypted graph data

Abstract The problem of querying shortest distance on a graph has attracted significant research attention due to the widespread applicability of graphs and the ability of graph shortest path queries to address numerous application problems. Given the limited capabilities of clients and the ongoing advancements in cloud computing, people would like to outsource their graph data. Outsourcing data, however, poses the problem of privacy breaches. We should enable clients to encrypt their data before outsource it to cloud servers while retaining the capability of querying the data. The major challenge lies in designing a scheme computing the shortest distance on encrypted graph is how to strike a balance between security, efficiency and accuracy. Moreover, this challenge becomes even more pronounced as the scale of the graph increases. In this article, we propose an efficient scheme called Encrypted Shortest Distance Approximate Query (ESDAQ). We design a new algorithm k-level BFS and make use of cryptographic primitive AES to fulfill the scheme where k is an optional parameter selected by user. The total time cost can be O(N) at best to finish setup and query, which is super