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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

20 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Article number8735830
Pages (from-to)315-328
Journal / PublicationIEEE Transactions on Information Forensics and Security
Online published12 Jun 2019
Publication statusPublished - 2020


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.

Research Area(s)

  • Cloud computing, secure outsourcing, min-cut algorithm, graph privacy, sensitive information