Secure Distributed Outsourcing of Large-scale LU Decomposition
Da Feng, Fucai Zhou, Qiyu Wu, Bao Li, Mengna Guo · 2023
Lower-Upper (LU) decomposition is one of the most important algorithms in linear algebra and numerical analysis. For very large scale matrices, the calculation amount of LU decomposition is enough to overwhelm the computing power of ordinary computing devices. Simply offloading tasks to large computing servers can pose serious data security concerns. In this work, we propose a secure distributed outsourcing protocol for LU decomposition in malicious adversarial model, for the first time. Specifically, we propose a new task allocation method, and design a new fast distributed LU decomposition algorithm accordingly, which is more efficient than previous algorithms because of its higher resource utilization. Then we propose a structure-preserving matrix masking scheme, and realize securely outsourcing LU decomposition to a distributed network of agents. Finally, we give both theoretical and experimental results to show the practical value of the proposed protocol.