Correctness Verifiable Outsourcing Computation Scheme of Shortest Path Querying over Encrypted Graph Data
Mass graph data such as geolocation and social networks are widely used and contain massive privacy,usually,it re-quires varied query services through secure outsourcing computation schemes.However,it is still an open challenge to design cor-rectness verifiable outsourcing computation protocols for graph data.To this end,a correctness-verifiable outsourcing computation scheme of accurate shortest path over encrypted graph data is proposed.In this scheme,a breadth-first shortest path algorithm for encrypted graph data is constructed by using additive homomorphic encryption to support the outsourcing computation of exact shortest distance queries over encrypted graph data.Secondly,a probabilistic correctness verification mechanism of shortest path outsourcing computation result is constructed by using the bilinear mapping accumulator.Analysis and proof show that this scheme implements the correctness-verifiable accurate shortest path outsourcing computation with probabilistic reliability,it has the security of IND-CCA2 under the random oracle model.Comparisons and experiments indicate that the proposed scheme has significant advantages compared with other related schemes in terms of security and functionality,compared with existing verifiable graph data outsourcing computation schemes,the overheads in the initialization and encryption phase,the query phase,and the verification and decryption phase reduces by 0.15％～23.19％,12.91％～30.89％and 1.13％～18.62％,respectively.
Graph data outsourcing computationVerifiableShortest path queryCryptographic accumulatorHomomorphic encryption
万方数据
维普
