A Minimum Path Calculation Algorithm for Protecting the Edge Weight Privacy in Cloud Circumstance

Xin LIU, Huan LI


Based on the encryption algorithm, this paper presents an algorithm to calculate a minimum path between nodes, which protects the privacy and security of edge weights. This algorithm carries on the encryption to the edge weight information, and then the encrypted data is outsourced to the cloud platform. Using breadth first theory, cloud server can directly achieve the graph like data encryption from the initial node outward, and calculate the minimum path from the initial node to the other nodes. This aims to calculate the minimum path between any two nodes. The minimum path calculated by the client and cloud server interaction in collaboration. The main calculation can be from the server, the client only decrypt and judges the operation simple. This algorithm can make the low computational capability of the client and also use cloud computing task to calculate the minimum path computation intensive, and to ensure that the intermediate results of calculation of edge weights. The final result of privacy information will not be leaked. Theoretical analysis and simulation experiments show the safety and correctness of the algorithm.


Cloud Computing, Shortest Distance Computing, Encrypted Graph Data, Privacy-preserving, Homomorphic Encryption


Full Text:



  • There are currently no refbacks.