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

Wei Ting Chang, Ravi Tandon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations

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θ, 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.

Original languageEnglish (US)
Title of host publication2019 IEEE Information Theory Workshop, ITW 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538669006
DOIs
StatePublished - Aug 2019
Event2019 IEEE Information Theory Workshop, ITW 2019 - Visby, Sweden
Duration: Aug 25 2019Aug 28 2019

Publication series

Name2019 IEEE Information Theory Workshop, ITW 2019

Conference

Conference2019 IEEE Information Theory Workshop, ITW 2019
Country/TerritorySweden
CityVisby
Period8/25/198/28/19

Keywords

  • Distributed Matrix Multiplication
  • Private Information Retrieval
  • Secure Matrix Multiplication

ASJC Scopus subject areas

  • Software
  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Information Systems

Fingerprint

Dive into the research topics of 'On the Upload versus Download Cost for Secure and Private Matrix Multiplication'. Together they form a unique fingerprint.

Cite this