Secure and Efficient Matrix Multiplication with MapReduce

International audienceMapReduce is one of the most popular distributed programming paradigms that allows processing big data sets in parallel on a cluster. MapReduce users often outsource data and computations to a public cloud, which yields inherent security concerns. In this paper, we consider the problem of matrix multiplication and one of the most efficient matrix multiplication algorithms: the Strassen-Winograd (SW) algorithm. Our first contribution is a distributed MapReduce algorithm based on SW. Then, we tackle the security concerns that occur when outsourcing matrix multiplication computation to a honest-but-curious cloud i.e., that executes tasks dutifully, but tries to learn as much information as possible. Our main contribution is a secure distributed MapReduce algorithm called S2M3 (Secure Strassen-Winograd Matrix Multiplication with MapReduce) that enjoys security guarantees such as: none of the cloud nodes can learn the input or the output data. We formally prove the security properties of S2M3 and we present an empirical evaluation devoted to show its efficiency