On the Upload versus Download Cost for Secure and Private Matrix Multiplication

Abstract

In this paper, we study the problem of secure and private distributed matrix multiplication. Specifically, we focus on a scenario where a user wants to compute the product of a confidential matrix A, with a matrix B <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">θ</sub> , where θ ∈ {1,..., M}. The set of candidate matrices {B <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> ,..., B <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</sub> } are public, and available at all the N servers. The goal of the user is to distributedly compute AB <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">θ</sub> , such that (a) no information is leaked about the matrix A to any server; and (b) the index θ is kept private from each server. Our goal is to understand the fundamental tradeoff between the upload vs download cost for this problem. Our main contribution is to show that the lower convex hull of following (upload, download) pairs: (U,D) = (N/(K - 1), (K/(K - 1)) (1 + (K/N) + ··· + (K/N) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M-1</sup> )) for K = 2, ..., N is achievable. The scheme improves upon state-of-the-art existing schemes for this problem, and leverages ideas from secret sharing and coded private information retrieval.