Secure Outsourcing for Normalized Cuts of Large-Scale Dense Graph in Internet of Things

With popularity and growth of cloud computing, outsourcing computation, as an important cloud service, has been applied in the field of academic and industry. It allows the resource-constrained IoT devices to outsource the computationally intensive problems to the cloud server. The smallest normalized cuts of the large-scale graph is a fundamental issue in graph theory, which is often used in various fields, such as community discovery, image segmentation, and network partition. Minimizing the normalized cuts of graph, as an NP-hard problem, can be approximately solved by the spectral decomposition. However, carrying out the spectral decomposition is very time-consuming and complicated for some IoT devices. In this article, we design a secure and efficient algorithm for outsourcing the spectral decomposition to an untrusted cloud server. We utilize a series of elementary matrices to protect both the input's privacy and the output's privacy from being disclosed to the cloud server. In order to ensure the correctness of the returned results, we design an efficient verification algorithm, which allows the client to detect the invalid results with a probability approximately 1. Our proposed algorithm not only reduces computational overhead on the client side, but also does not bring extra computational overhead on the cloud server side. Then, we give a theoretical analysis about correctness and privacy. Finally, we also provide some experimental results to show the feasibility of our proposed algorithm.

Automated summary

With the rise of cloud computing, outsourcing computation has become a popular service in academic and industry sectors. In this article, a secure and efficient algorithm is proposed to outsource spectral decomposition to an untrusted cloud server, protecting both input and output privacy while ensuring correctness through efficient verification. The results not only reduce computational overhead for clients, but also do not add extra workload on the cloud server, with theoretical analysis and experimental results provided.