How to Securely Outsource Finding the Min-Cut of Undirected Edge-Weighted Graphs

Finding min-cut is a fundamental operation in graph theory. It has been widely used in many applications such as image segmentation and network partition. However, solving min-cut problem is time-consuming for resource-constrained devices, especially when the graph is large and dense. In this paper, we explore how to securely solve the min-cut problem in cloud environment, and propose two secure outsourcing schemes for the min-cut of undirected edge-weighted graphs. The first scheme is based on two non-colluded untrusted cloud servers, and the second one is under the single untrusted cloud server model. In the designed schemes, we develop a new technique that contains merging vertices and edges, inserting fake vertices and edges, shuffling vertices and randomizing weights of edges to protect the privacy of graphs. In order to realize the checkability of result from a single untrusted cloud server, we design a novel verification mechanism by outsourcing the min-cut of two related graphs. Besides, we also provide the security analysis and the experimental evaluation. To the best of our knowledge, it is the first research on secure outsourcing of graph algorithm.