Notes on Communication and Computation in Secure Distributed Matrix Multiplication

Rafael G.L. D'Oliveira, Salim El Rouayheb, Daniel Heinlein, David Karpuk

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

3 Citations (Scopus)

Abstract

We consider the problem of secure distributed matrix multiplication in which a user wishes to compute the product of two matrices with the assistance of honest but curious servers. In this paper, we answer the following question: Is it beneficial to offload the computations if security is a concern? We answer this question in the affirmative by showing that by adjusting the parameters in a polynomial code we can obtain a trade-off between the user's and the servers' computational time. Indeed, we show that if the computational time complexity of an operation in F q is at most Z q and the computational time complexity of multiplying two n× n matrices is O(nω Z q) then, by optimizing the trade-off, the user together with the servers can compute the multiplication in O (n4-/6ω+1 Z q) time. We also show that if the user is only concerned in optimizing the download rate, a common assumption in the literature, then the problem can be converted into a simple private information retrieval problem by means of a scheme we call Private Oracle Querying. However, this comes at large upload and computational costs for both the user and the servers.

Original languageEnglish
Title of host publication2020 IEEE Conference on Communications and Network Security, CNS 2020
PublisherIEEE
Number of pages6
ISBN (Electronic)9781728147604
DOIs
Publication statusPublished - Jun 2020
MoE publication typeA4 Article in a conference publication
EventIEEE Conference on Communications and Network Security - Virtual, Online, France
Duration: 29 Jun 20201 Jul 2020

Conference

ConferenceIEEE Conference on Communications and Network Security
Abbreviated titleCNC
CountryFrance
CityVirtual, Online
Period29/06/202001/07/2020

Fingerprint Dive into the research topics of 'Notes on Communication and Computation in Secure Distributed Matrix Multiplication'. Together they form a unique fingerprint.

Cite this