Achieving security, robust cheating resistance, and high-efficiency for outsourcing large matrix multiplication computation to a malicious cloud

Computation outsourcing to the cloud has become a popular application in the age of cloud computing. This computing paradigm brings in some new security concerns and challenges, such as input/output privacy and result verifiability. Given that matrix multiplication computation (MMC) is a ubiquitous scientific and engineering computational task, we are motivated to design a protocol to enable secure, robust cheating resistant, and efficient outsourcing of MMC to a malicious cloud in this paper. The main idea to protect the privacy is employing some transformations on the original MMC problem to get an encrypted MMC problem which is sent to the cloud; and then transforming the result returned from the cloud to get the correct result to the original MMC problem. Next, a randomized Monte Carlo verification algorithm with one-sided error is introduced to successfully handle result verification. We analytically show that the proposed protocol is correct, secure, and robust cheating resistant. Extensive theoretical analysis and experimental evaluation also show its high-efficiency and immediate practicability. Finally, comparisons between the proposed protocol and the previous protocols are given to demonstrate the improvements of the proposed protocol.