Research On The Shortest Path Outsourcing Privacy Computing Model And Application Of Graph Dat

As graph data is widely used and contains massive private information,it is trend to outsource the storage and computation tasks of graph data to cloud servers due to the increasing development of cloud computing and its own characteristics,it can minimize the investment of material resources and the cost of daily maintenance and management.Shortest path query,as the most basic structural query for graph data,is broadly used in many query services.However,the topological structure and node association relationship of graph data are complexity,and the privacy data lose physical control with outsourcing,it is easy to leak the privacy data.Firstly,in order to protect sensitive data,it is necessary to have encryption of data before outsourcing to cloud servers,thus protect data security to prevent leakage of private information,but using traditional encryption schemes will impact the utilization of data,and the availability of original data is destroyed during computation and storage operations.Secondly,cloud services are not completely trustworthy or even malicious,and they may violate data security and privacy by presuming and deciphering the original data based on encrypted graph data and query requests,or deliberately not performing query calculations according to the real calculation process because of economic interests（e.g.,deliberately reduce computing resources）,or cause partial data loss or errors by third-party attacks,their own failures,etc.,leading to the requested shortest distance query calculation results are not correct or accurate.In response to the above problems respectively design schemes,the main work of this paper on the shortest path outsourced privacy calculation of graph data includes the following aspects:（1）Design the exact shortest distance computation on ciphertext graph data,and propose an exact shortest distance query of outsourced graph data based on 2-hop cover labeling and additive homomorphic encryption.First,a breadth-first search pruning strategy is proposed to reduce the number of preprocessed labels and improve the query efficiency by preprocessing the original set of labels generated by 2-hop cover labeling;second,the set of labels is encrypted and a secure index structure is constructed based on additive homomorphic encryption and pseudo-random function to protect the node and distance information of graph data for exact shortest distance query on encrypted graph data;third,the security model of the scheme is defined formally,it is proved that the exact shortest distance computation scheme for encrypted graph data satisfies IND-CPA security and （L₁,L₂）security under the random oracle model by theoretical analysis and simulating the adversary attack mode in the query process;finally,experimental comparison with related schemes is conducted.（2）Design correctness verifiable shortest path outsourcing computation scheme for encrypted graph data.Firstly,it analyzes the way of instantiating graph data in the adjacency table,establishes the array index based on the node in/out degree,and constructs the breadth-first shortest path computation algorithm on encrypted graph data using additive homomorphic encryption to support the exact shortest distance query outsourcing computation of encrypted graph data;secondly,it structures the probabilistic correctness verification mechanism of the shortest path outsourcing computation results based on the bilinear mapping accumulator to guarantee the correctness and incorruptibility of the results.Thirdly,it constructs the adversary attack process under the random oracle model through formal definition of security model of scheme,and proves the adaptive semantic security and correctness verification of the scheme under the collision-free security with random prediction model;finally,it is compared and analyzed with the existing verifiable scheme.