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 language | English |
---|---|
Title of host publication | 2020 IEEE Conference on Communications and Network Security, CNS 2020 |
Publisher | IEEE |
Number of pages | 6 |
ISBN (Electronic) | 9781728147604 |
DOIs | |
Publication status | Published - Jun 2020 |
MoE publication type | A4 Article in a conference publication |
Event | IEEE Conference on Communications and Network Security - Virtual, Online, France Duration: 29 Jun 2020 → 1 Jul 2020 |
Conference
Conference | IEEE Conference on Communications and Network Security |
---|---|
Abbreviated title | CNC |
Country/Territory | France |
City | Virtual, Online |
Period | 29/06/2020 → 01/07/2020 |