Private Matrix Multiplication From MDS-Coded Storage With Colluding Servers

Jinbao Zhu, Jie Li, Songze LiarXiv 2022 · OpenReview

Abstract

This paper presents efficient strategies for private matrix multiplication in distributed systems where data is stored using Maximum-Distance-Separable (MDS) codes. By employing polynomial-based secret sharing and interference alignment, the proposed methods provide information-theoretic privacy for both data and computation indices against colluding servers. The strategies significantly reduce communication and computation overhead compared to existing state-of-the-art methods, particularly by making upload costs nearly independent of library size.

Introduction

In the era of big data, large-scale matrix multiplication is a fundamental operation for various machine learning and data analysis tasks. To handle the sheer volume of data, distributed computing systems often store datasets across multiple servers. Reliability is typically ensured through Maximum-Distance-Separable (MDS) codes, such as Reed-Solomon codes, which offer optimal storage efficiency. However, performing computations on sensitive data in these distributed environments introduces significant privacy risks. If servers are curious or collude to share information, they could potentially reconstruct private matrices or infer which specific data points a user is accessing.

Problem Formulation

The authors address two primary scenarios involving private matrix multiplication:

1. Private and Secure Matrix Multiplication (PSMM)

In this setting, a user (the master node) possesses a private matrix $A$ and wishes to compute the product $AB^{(\theta)}$, where $B^{(\theta)}$ is a matrix selected from a public library $\mathcal{L}^B = \{B^{(1)}, \dots, B^{(V)}\}$ stored on $N$ servers using an $(N, K)$ MDS code. The privacy requirement is two-fold: the servers must not learn anything about the private matrix $A$, and they must not learn the index $\theta$ of the selected library matrix.

System model for Private and Secure Matrix Multiplication (PSMM).

2. Fully Private Matrix Multiplication (FPMM)

Here, both matrices are selected from public libraries $\mathcal{L}^A$ and $\mathcal{L}^B$ stored on the servers. The user wants to compute $A^{(\theta_A)}B^{(\theta_B)}$ without revealing the indices $\theta_A$ or $\theta_B$ to any group of up to $T$ colluding servers.

System model for Fully Private Matrix Multiplication (FPMM).

Proposed Methodology

The core innovation lies in the use of Polynomial Secret Sharing combined with Interference Alignment.

Encoding and Querying

The master node encodes its private inputs (either the matrix $A$ or the indices $\theta_A, \theta_B$) into polynomials. For PSMM, a polynomial $f(x)$ is constructed such that its coefficients include the private matrix $A$ and several random noise matrices to ensure $S$-privacy against colluding servers. Similarly, query polynomials $h(x)$ are designed to be MDS-compatible, meaning they account for the specific $(N, K)$ MDS structure used for storage.

Interference Alignment

When servers perform local multiplications, the resulting response is an evaluation of a product polynomial $g(x) = f(x) \cdot h(x)$. A critical challenge in MDS-coded storage is that each server only holds a coded piece of every library matrix. Multiplying the query by these coded pieces generates "interference" from all other matrices in the library. The authors use interference alignment to ensure that the desired product terms are mapped to specific coefficients of the result polynomial $g(x)$, while all unwanted interference terms are aligned to a separate, disjoint set of coefficients.

Recovery

The master node collects responses from a subset of servers. The number of required responses is defined as the "recovery threshold." Because the responses are evaluations of the polynomial $g(x)$, the master can use polynomial interpolation to recover the coefficients and, consequently, the desired matrix product.

Key Results and Performance

The proposed strategies offer several advantages over existing methods, such as the state-of-the-art strategy by Li & Hollanti:

  • Efficiency and Scalability: In the PSMM scenario, the upload cost is made almost independent of the library size $V$. This is a major improvement over previous techniques where communication costs scaled linearly with $V$, making the new approach highly suitable for "big data" applications.
  • Lower Recovery Thresholds: For FPMM, the proposed strategy achieves a lower recovery threshold than standard Private Information Retrieval (PIR) baselines. This means the system can complete the computation faster by waiting for fewer servers.
  • Robustness: The framework is naturally resilient to "stragglers" (slow servers). Since the responses form an MDS codeword, the master node only needs a subset of responses to reconstruct the result. The authors also note that the scheme can be extended to handle malicious servers that might return incorrect data.

Conclusion

This work provides a robust theoretical framework for private distributed matrix multiplication. By cleverly aligning interference within a polynomial structure, the authors achieve high levels of privacy with significantly reduced overhead. While the current model assumes "honest-but-curious" servers and a fixed MDS storage structure, it sets a strong foundation for future research into Byzantine-resilient systems and dynamic storage environments.

Summary updated

BibTeX
@misc{zhu2022private,
  author = {Jinbao Zhu and Jie Li and Songze Li},
  title = {{Private Matrix Multiplication From MDS-Coded Storage With Colluding Servers}},
  year = {2022},
  url = {https://openreview.net/forum?id=PwZKC98P-Ys},
}
Figure