Data confidentiality and integrity preserving outsourcing algorithm for matrix chain multiplication over malicious cloud server

摘要

Cloud computing offers an economical, convenient and elastic pool of computing resources over the internet. It enables computationally weak client to execute large computations by outsourcing their computation load to the cloud servers. However, outsourcing of data and computation to the third-party cloud servers bring multifarious security and privacy challenges that needed to be understood and address before the development of outsourcing algorithm. In this paper, the authors propose solutions for matrix-chain multiplication (MCM) problem. Our goal is to minimize the execution burden on the client without sacrificing the confidentiality and integrity of the input/output. Conventionally, the complexity of matrix-chain multiplication is O(n(3)). After leveraging the facility of outsourcing, the client-side complexity reduces to O(n(2)). In the proposed algorithm, the client employs some efficient linear transformation schemes, which preserve the data confidentiality. It also developed a novel result verification scheme, which verifies the result with modest burden and high probability and maintain the integrity of computed result. The analytical analysis of algorithm depicted that the algorithm is simultaneously meeting the design goals of correctness, security, efficiency and verifiability. We conduct many experiments to validate the algorithm and demonstrate its practical usability. The algorithm is implemented on public cloud "Amazon EC2", and found that the proposed outsource algorithm performs 11.655 times faster computation of matrix-chain multiplication than the direct implementation.