TY - GEN

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

AU - Chang, Wei Ting

AU - Tandon, Ravi

N1 - Funding Information:
This work was supported by NSF Grants CAREER 1651492, and CNS 1715947.
Publisher Copyright:
© 2019 IEEE.

PY - 2019/8

Y1 - 2019/8

N2 - 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θ, where θ 1,..., M. The set of candidate matrices B1,..., BM are public, and available at all the N servers. The goal of the user is to distributedly compute ABθ, 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)M-1)) 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.

AB - 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θ, where θ 1,..., M. The set of candidate matrices B1,..., BM are public, and available at all the N servers. The goal of the user is to distributedly compute ABθ, 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)M-1)) 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.

KW - Distributed Matrix Multiplication

KW - Private Information Retrieval

KW - Secure Matrix Multiplication

UR - http://www.scopus.com/inward/record.url?scp=85081053857&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85081053857&partnerID=8YFLogxK

U2 - 10.1109/ITW44776.2019.8989342

DO - 10.1109/ITW44776.2019.8989342

M3 - Conference contribution

AN - SCOPUS:85081053857

T3 - 2019 IEEE Information Theory Workshop, ITW 2019

BT - 2019 IEEE Information Theory Workshop, ITW 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE Information Theory Workshop, ITW 2019

Y2 - 25 August 2019 through 28 August 2019

ER -