Harnessing the Cloud for Securely Solving Large-Scale Systems of Linear Equations

摘要: Cloud computing economically enables customers with limited computational resources to outsource large-scale computations the cloud. However, how protect customers' confidential data involved in then becomes a major security concern. In this paper, we present secure outsourcing mechanism for solving systems of linear equations (LE) Because applying traditional approaches like Gaussian elimination or LU decomposition (aka. direct method) such LE problems would be prohibitively expensive, build via completely different approach -- iterative method, which is much easier implement practice and only demands relatively simpler matrix-vector operations. Specifically, our customer securely harness cloud iteratively finding successive approximations solution, while keeping both sensitive input output computation private. For robust cheating detection, further explore algebraic property operations propose an efficient result verification mechanism, allows verify all answers received from previous one batch high probability. Thorough analysis prototype experiments on Amazon EC2 demonstrate validity practicality proposed design.