Secure Computation Outsourcing Schemes For Low-Rank System Of Linear Equations And Univariate Polynomials

Cloud computing providers with huge computing and storage resources can provide for the users on-demand computing and storage services. So cloud users benefit much from the computing and storage services provided by the cloud providers. Howerver, the users are also confronted with some security challenges. Especially, in the cloud computation outsourcing paradigm, the cloud users need to consider the computational input/output privacy, the verifiability of the computational results, the computational correctness, and the computational efficiency problems. The dissertation includes the following contributions dedicated to solving sytstem of linear equations and evaluating univariate polynomials.1. Secure cloud computation outsourcing protocol for solving low-rank linear equations. This protocol is the generalization and improvement on the previous protocol for matrix inversion computation(MIC). Similar to the MIC protocol, the protocol uses the features of easy multiplication and inversion of the permutation matrices to blind the coefficient matrix and the constant vector of the linear equations. Analysis shows that the protocol guarantees the input and output privacy. Computational complexity and efficiency analysis demonstrate that the larger the dimension of the matrix, the larger the advantage of our outsourcing protocol: After the dimension of hundreds, efficiency of outsourcing protocol is better than the local scheme; After the dimension of thousands, the protocol can save the computational overhead for the users with a factor about 50%.2. Secure cloud computation outsourcing protocol for the evaluation of univariate polynomials. Based on the modular subset sum problem, we construct a secure cloud computation outsourcing protocol for the evaluation of univariate polynomials(EUP). The protocol blinds the polynomial by encrypting each coefficient of the polynomial. The input/output privacy is proved under the computational intracability assumption of the modular subset sum problem. The computational results can be verified by comparing the decrypted results. Simulation results illustrate that in general cases, the protocol can save the computational overhead for the users with a factor about 50%.