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

摘要

AbstractIn 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.Highlights•We analyze the security vulnerabilities of existing linear regression (LR) outsourcing scheme.•We present a new encryption scheme to securely outsource large-scale LR to an untrusted cloud, in which the input dataset is perturbed by dense matrices with high efficiency.•We observe an equivalent condition of LR answer verification, based on which we develop a novel verification algorithm for LR outsourcing.•We provide detailed theoretical analysis and extensive simulation experiments to evaluate the new scheme.