## 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 |