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_{\theta }$, where $\theta \in \{1,\dots ,M\}$. The set of candidate matrices $\{B_1,\dots ,B_M\}$ are public, and available at all the $N$ servers. The goal of the user is to distributedly compute $A{B}_{\theta }$, such that $(a)$ no information is leaked about the matrix $A$ to any server; and $(b)$ the index $\theta$ 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)+\cdots +(K/N{)}^{M-1}))$ for $K=2,\dots ,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.

arXiv commentTo appear at IEEE Information Theory Workshop (ITW) 2019

References in corpus (4)

• Minimizing Latency for Secure Distributed Computing
• Rate-Efficiency and Straggler-Robustness through Partition in Distributed Two-Sided Secure Matrix Computation
• The Capacity of Private Computation
• Private Secure Coded Computation

Cited by in corpus (4)

• Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
• Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier
• Uplink-Downlink Tradeoff in Secure Distributed Matrix Multiplication
• $X$-secure $T$-private Information Retrieval from MDS Coded Storage with Byzantine and Unresponsive Servers