Cost-Based Modeling and Optimization of Secure Matrix Multiplication in the Cloud

Machine Learning (ML) applications are prominent in many fields due to their ability to derive insights and automate processes. Many services utilize data from smart devices to offer personalized services to users. However, privacy concerns arise when sensitive data is collected by such devices for ML operations and outsourced to the cloud, along with the high liability costs associated with a security breach. Multiparty computation (MPC) is a promising method for privacy-preserving ML. Nonetheless, it has a significant computational overhead, mainly due to the large number of associated Matrix Multiplications (MM) in ML training and inference. This paper improves the arithmetic complexity of secure MM over MPC using the Strassen algorithm. We formulated a Multi-Objective Optimization Problem (MOOP) to optimize the trade-off among resource costs, execution time of secure MM, and the potential security loss due to a cyberattack. We implemented and analyzed the performance of several classical solutions to the MOOP, including Brute Force and the Non-Dominated Sorting Genetic Algorithm (NSGA). Using insights from these evaluations, we developed a solution, DepthSwift, which judiciously, efficiently, and quickly solves the MOOP for all required MMs in ML training or inference. Our implementation over SPDZ shows that we can significantly reduce resource costs and minimize potential security loss with respect to the naive MM over MPC.