Efficiently and securely harnessing cloud to solve linear regression and other matrix operations

In this paper, we study the problem of efficiently outsourcing large-scale linear regression of a customer to the public cloud while preserving the privacy of the customer's input and output results. To reduce the customer's computation costs, existing schemes generally use diagonal matrix multiplication to encrypt the input data. While such approaches are efficient, there are potential security limitations. For example, in this paper we reveal previously unknown limitations in the scheme of Chen et al. (2014). We then present a novel method to generate random dense matrices, and a new secure solution for outsourcing linear regression to cloud. In our proposed approach, we perturb the customer's input/output by adding random numbers and multiplying our constructed random dense matrices. A comparative summary demonstrates that the proposed approach has a stronger level of security, without incurring additional computation complexity. We also demonstrate that our constructed dense matrices can be utilized to efficiently enhance the security of outsourcing scheme for other large-scale matrix operations, including linear equation system and determinant computation.