Distributed Matrix Multiplication: Download Rate, Randomness and Privacy Trade-Offs
Amirhosein Morteza, Rémi A. Chou
Abstract
We study the trade-off between communication rate and privacy for distributed batch matrix multiplication of two independent sequences of matrices A and B with uniformly distributed entries. In our setting, B is publicly accessible by all the servers while A must remain private. A user is interested in evaluating the product AB with the responses from the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> fastest servers. For a given parameter <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\alpha\in [0,1]$</tex>, our privacy constraint must ensure that any set of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell$</tex> colluding servers cannot learn more than a fraction <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\alpha$</tex> of A. Additionally, we study the trade-off between the amount of local randomness needed at the encoder and privacy, which to the best of our knowledge no previous work has characterized. Finally, we establish the optimal trade-offs when the matrices are square and identify a linear relationship between information leakage and communication rate.