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 superior to SOTA solutions of O ( NlogN ). Theoretical security analysis shows that ESDAQ can reach CQA2 -security . Theoretical analysis on security, performance and accuracy are provided of our proposed scheme. Meanwhile, experiments on 12 representative real-world datasets and comprehensive comparison with top and latest schemes are provided. The experiments results demonstrates that our scheme is highly efficient and can be effectively applied to large-scale graphs which comprising over 3 million nodes and 1 billion edges.