Information-Theoretically Private Matrix Multiplication From MDS-Coded Storage

We study two problems of private matrix multiplication, over a distributed computing system consisting of a master node, and multiple servers who collectively store a family of public matrices using Maximum-Distance-Separable (MDS) codes. In the first problem of Private and Secure Matrix Multiplication from Colluding servers (MDS-C-PSMM), the master intends to compute the product of its confidential matrix $\mathbf{A}$ with a target matrix stored on the servers, without revealing any information about $\mathbf{A}$ and the index of target matrix to some colluding servers. In the second problem of Fully Private Matrix Multiplication from Colluding servers (MDS-C-FPMM), the matrix $\mathbf{A}$ is also selected from another family of public matrices stored at the servers in MDS form. In this case, the indices of the two target matrices should both be kept private from colluding servers. We develop novel strategies for MDS-C-PSMM and MDS-C-FPMM, which simultaneously guarantee information-theoretic data/index privacy and computation correctness. The key ingredient is a careful design of secret sharings of the matrix $\mathbf{A}$ and the private indices, which are tailored to matrix multiplication task and MDS storage structure, such that the computation results from the servers can be viewed as evaluations of a polynomial at distinct points, from which the intended result can be obtained through polynomial interpolation. We compare the proposed MDS-C-PSMM strategy with a previous MDS-PSMM strategy with a weaker privacy guarantee (non-colluding servers), and demonstrate substantial improvements over the previous strategy in terms of communication and computation performance.