Privacy-Preserving Outsourcing Algorithm for Solving Large Systems of Linear Equations

Abstract

In recent years, the secure offloading of resource-intensive computations to third-party servers has gained significant attention, thanks to the availability of computing services provided by major cloud service providers. In this paper, we propose a novel algorithm that addresses the secure outsourcing of computation for solving large-scale System of Linear Equations (SLEs). The proposed algorithm introduces a unique transformation technique to encrypt a given SLE, effectively tackling the security challenges that have been posed or raised by previous related algorithms. In contrast to prior algorithms, which focused on SLEs with a full-rank coefficient matrix, our algorithm is the first of its kind, compatible with all variations of large-scale SLEs, effectively finding a solution if one exists. Moreover, our suggested approach ensures a one-round client–cloud interaction, and allowing the client to verify the trustworthiness of the cloud server with a probability of 1. For the experimental analysis, we utilized a GPU server, specifically the Tesla V100-PCIE, as the cloud-side server. Furthermore, through a comprehensive theoretical analysis and experimental comparisons with the best-known algorithm [IEEE TIFS, 2014], we demonstrate the effectiveness of our approach. The results show that our algorithm outperforms the best-known algorithm in terms of efficiency, thereby solidifying its superiority in solving large-scale SLEs. © 2023, The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd.