Abstract
As one of the most important basic operations, matrix multiplication computation (MMC) has varieties of applications in the scientific and engineering community such as linear regression, k-nearest neighbor classification and biometric identification. However handling these tasks with large-scale datasets will lead to huge computation beyond resource-constrained client s computation power. With the rapid development of cloud computing, outsourcing intensive tasks to cloud server has become a promising method. While the cloud server is generally out of the control of clients, there are still many challenges concerned with the privacy security of clients sensitive data. Motivated by this, Lei et al. presented an efficient encryption scheme based on random permutation to protect the privacy of client s data in outsourcing MMC task. Nevertheless, there exists inherent security flaws in their scheme, revealing the statistic information of zero elements in the original data thus not satisfying the computational indistinguishability (IND-ZEA). Aiming to enhance the security of the outsourcing MMC task, we propose a new encryption scheme based on subtly designed invertible matrix where the additive perturbation is introduced besides the multiplicative perturbation. Furthermore, we show that the proposed encryption scheme can be applied to not only MMC task but also other kinds of outsourced tasks such as linear regression and principal component analysis. Theoretical analyses and experiments indicate that our methods are more secure in terms of data privacy, with comparable performance to the state-of-the-art scheme based on matrix transformation.
Introduction
Matrix multiplication computation (MMC) is a fundamental building block for numerous scientific and engineering applications, including linear regression, k-nearest neighbor classification, and biometric identification. As datasets scale, the $O(n^3)$ computational complexity of MMC often exceeds the capabilities of resource-constrained "thin" clients, such as mobile devices or local sensors.
Outsourcing these intensive tasks to cloud servers offers a viable solution. However, the "curious-and-lazy" nature of cloud providers introduces significant privacy and integrity risks. Previous lightweight encryption schemes, such as those based on random permutations, fail to hide the location and frequency of zero elements, making them vulnerable to "Zero Elements Attacks" (ZEA). Conversely, heavy-duty solutions like Fully Homomorphic Encryption (FHE) are computationally prohibitive for practical use. This paper proposes a novel encryption scheme that balances high security with computational efficiency.
Methodology
The proposed system architecture for secure outsourcing is illustrated in Figure 1. The client performs lightweight encryption and key generation locally, while the cloud server handles the bulk of the computation on the encrypted data.
Encryption Scheme
The core of the proposed method is a transformation using a subtly designed invertible matrix $M = P + H$.
- Multiplicative and Additive Perturbation: Unlike standard schemes that rely solely on a permutation matrix $P$ (multiplicative), this scheme adds a rank-1 matrix $H$ (additive). This "blending" ensures that zero elements in the original matrix are mapped to non-zero values in the ciphertext, satisfying Computational Indistinguishability (IND-ZEA).
- Sherman-Morrison Formula: To maintain efficiency, the client utilizes the Sherman-Morrison formula to compute the inverse of $M$ in $O(n^2)$ time, avoiding the $O(n^3)$ cost typically associated with general matrix inversion.
Verification and Applications
To ensure the integrity of the results returned by the cloud, the client employs a randomized verification method based on Freivalds' algorithm, which operates in $O(n^2)$ time. The authors further demonstrate that this $M = P + H$ transformation is versatile, extending to complex pipelines like Linear Regression (LR) and Principal Component Analysis (PCA).
Evaluation and Results
The scheme was evaluated using synthetic large-scale datasets with matrix dimensions ranging from $(400, 500, 600)$ to $(2400, 3000, 3600)$.
Performance Metrics
- Client Speedup: For the largest matrices ($2400 \times 3000 \times 3600$), the client achieved a speedup of approximately 76x compared to local execution.
- Cloud Efficiency: The overhead introduced by encryption was minimal, with cloud efficiency remaining near 1.0, indicating that the encrypted task's complexity is nearly identical to the plaintext version.
Security Analysis
Theoretical analysis confirms that the scheme is resistant to brute-force attacks, greatest common divisor attacks, and average absolute value attacks. By masking zero elements, it successfully addresses the security flaws identified in previous state-of-the-art methods.
Conclusion
This paper presents an efficient and secure encryption scheme for outsourcing MMC to the cloud. By integrating additive perturbation with multiplicative transformation, the method achieves IND-ZEA security without sacrificing the performance gains of outsourcing. While the scheme shows a slight efficiency drop in PCA due to the loss of matrix symmetry (cloud efficiency of ~0.91), it remains a robust solution for privacy-preserving cloud computing. Future work will explore methods to preserve matrix symmetry while maintaining high privacy standards.
Summary updated