Source-linked AI summary
On the Capacity of Secure Distributed Matrix Multiplication
Wei-Ting Chang, Ravi Tandon
TL;DR
The paper addresses the open problem of communication limits for information-theoretically secure distributed matrix multiplication with colluding servers. It presents a capacity-achieving scheme and converse for the one-sided model, and an achievable scheme for the fully private-input model.
Problem
The fundamental communication limits for information-theoretically secure matrix multiplication remain open, despite interest in outsourcing computation to untrusted servers.
Source: §I · p. 1Method
The paper develops a secure scheme and matching converse for the one-sided model, and proposes an achievable scheme for the fully secure model.
Source: §I · p. 2Results
The one-sided capacity is (N − ℓ)/N, while the fully secure model receives a novel achievable scheme.
Source: §I · p. 2Takeaways & Limitations
For the one-sided model, the stated price of security against ℓ colluding servers is ℓ/N.
Source: §I · p. 2
Abstract
from arXiv · showhide
Matrix multiplication is one of the key operations in various engineering applications. Outsourcing large-scale matrix multiplication tasks to multiple distributed servers or cloud is desirable to speed up computation. However, security becomes an issue when these servers are untrustworthy. In this paper, we study the problem of secure distributed matrix multiplication from distributed untrustworthy servers. This problem falls in the category of secure function computation and has received significant attention in the cryptography community. However, the fundamental limits of information-theoretically secure matrix multiplication remain an open problem. We focus on information-theoretically secure distributed matrix multiplication with the goal of characterizing the minimum communication overhead. The capacity of secure matrix multiplication is defined as the maximum possible ratio of the desired information and the total communication received from $N$ distributed servers. In particular, we study the following two models where we want to multiply two matrices $A\in\mathbb{F}^{m\times n}$ and $B\in\mathbb{F}^{n\times p}$: $(a)$ one-sided secure matrix multiplication with $\ell$ colluding servers, in which $B$ is a public matrix available at all servers and $A$ is a private matrix. $(b)$ fully secure matrix multiplication with $\ell$ colluding servers, in which both $A$ and $B$ are private matrices. The goal is to securely multiply $A$ and $B$ when any $\ell$ servers can collude. For model $(a)$, we characterize the capacity as $C_{\text{one-sided}}^{(\ell)}=(N-\ell)/N$ by providing a secure matrix multiplication scheme and a matching converse. For model $(b)$, we propose a novel scheme that lower bounds the capacity, i.e., $C_{\text{fully}}^{(\ell)}\geq (\lceil \sqrt{N}-\ell \rceil)^2/(\lceil \sqrt{N}-\ell \rceil+\ell)^2$.
I. INTRODUCTION
The paper seeks information-theoretically secure matrix multiplication with low communication overhead across one-sided and fully private-input models. It gives a capacity result for the one-sided model and proposes an achievable scheme for the fully secure model.
Motivation
- Outsourcing computation to distributed servers can improve efficiency, but untrustworthy servers raise concerns when inputs contain sensitive information.The motivation is to use powerful servers without revealing input data.Source: §I · p. 1
Related Work
- Prior information-theoretic distributed-multiplication work used codes to reduce communication and mitigate stragglers, while secure multiplication had mainly drawn cryptographic approaches.The introduction identifies limited information-theoretic work on secure matrix multiplication.Source: §I · p. 1
Main Contributions
- The paper aims to combine information-theoretic security with low communication overhead in distributed matrix multiplication.The stated goal is to devise schemes with both properties.Source: §I · p. 1
- For one-sided multiplication, the capacity is (N − ℓ)/N, so the stated security cost is ℓ/N.Here B is public and A is private, with security against any ℓ colluding servers.Source: §I · p. 2
- For fully secure multiplication, where both matrices are private, the paper proposes a novel achievable scheme for security against any ℓ colluding servers.The supplied contribution passage does not provide the complete rate expression.Source: §I · p. 2
II. SYSTEM MODEL AND PROBLEM FORMULATION
The model has one user distribute encoded matrix inputs to N honest-but-curious servers and decode their responses into AB. It distinguishes which inputs must remain hidden when any ℓ servers may collude.
System Model
- A user seeks AB from N servers over private links, sending securely encoded versions of A and B and decoding the returned server answers.The matrices have dimensions A ∈ F^(m×n) and B ∈ F^(n×p).Source: §II · p. 2
One-Sided Model
- In the one-sided model, B is public and A must remain hidden from any ℓ colluding servers, whose identities the user does not know.The security condition requires the colluding servers’ encoded views of A to reveal no information about A.Source: §II · pp. 2–3
Fully Secure Model
- In the fully secure model, both A and B are private and their jointly encoded views must reveal no information about either input to any ℓ colluding servers.The passage states the condition as I(A, B; eA_L, eB_L) = 0 for every ℓ-server set L.Source: §II · p. 3
Rate and Capacity
- A rate is achievable when a scheme satisfies the decodability and security constraints, and the fully secure capacity is the supremum of achievable rates.The one-sided rate is described as desired bits per download bit.Source: §II · p. 3
III. ONE-SIDED SECURE MATRIX MULTIPLICATION WITH ℓCOLLUDING SERVERS
The one-sided scheme lets servers multiply encoded pieces of A by public B, while a converse establishes its optimality. A four-server example illustrates recovery under two-server collusion.
One-Sided Secure Matrix Multiplication
- The proposed one-sided scheme is paired with a converse proof establishing information-theoretic optimality.The section presents the scheme and converse for the model where B is public and A must remain private.Source: §III · p. 3
Example
- The example’s encoding uses random matrices alongside partitions of A, and each server multiplies its encoded matrix by B and returns the result.Each encoded matrix has the same dimension as a partition of A.Source: §III · p. 3
- For N = 4 and ℓ = 2, the user recovers two desired products from four returned items, achieving rate 1/2.The coefficient matrix is Vandermonde and invertible, while any two servers see only two equations in four matrices.Source: §III · p. 4
Proof of Theorem 1
The proof section gives a generalized achievable scheme for one-sided secure multiplication and establishes its optimality with an information-theoretic converse.
Proof of Theorem 1
- A modified Shamir secret-sharing scheme provides the generalized achievable scheme for the one-sided problem.The proof section pairs the scheme with a converse argument.Source: Proof of Theorem 1 · p. 4
- The converse and matching scheme establish the capacity for one-sided secure matrix multiplication.The section identifies the converse as the optimality argument.Source: Proof of Theorem 1 · p. 4
- The proof treats the scheme as a generalization of the preceding achievable construction.It states that the capacity can be achieved by the modified secret-sharing scheme.Source: Proof of Theorem 1 · p. 4
A. Achievable Scheme
The scheme partitions A, masks its blocks with random matrices in a polynomial encoding, and recovers the desired products by interpolation while preserving information-theoretic security.
A. Achievable Scheme
- A is split vertically into N−ℓ blocks; ℓ independent uniform random matrices mask them in polynomial evaluations at distinct nonzero server points.Each encoded matrix has the same dimension as a block of A.Source: A. Achievable Scheme · p. 4
- At rate (N−ℓ)/N, interpolation of N server evaluations recovers the N−ℓ desired products A_iB.The responses are evaluations of a degree N−1 polynomial.Source: A. Achievable Scheme · p. 4
- The authors establish information-theoretic security by showing the colluding servers’ encoded shares reveal zero mutual information about A.The security proof uses the independence of the random masks from A.Source: A. Achievable Scheme · p. 4
B. Converse
An entropy-based converse upper-bounds the one-sided scheme’s rate, and the matching achievable scheme establishes its capacity.
B. Converse
- Decodability expresses H(AB) through the servers’ joint answers, while security makes each ℓ-server subset’s answers independent of AB.The argument uses data processing and Han’s inequality to bound answer entropy.Source: B. Converse · p. 5
- The converse and achievable scheme match, establishing one-sided matrix multiplication capacity as (N−ℓ)/N.The upper bound is compared with the matching scheme from Section III-A.Source: B. Converse · p. 5
IV. FULLY SECURE MATRIX MULTIPLICATION WITH ℓCOLLUDING SERVERS
For fully secure multiplication, the paper gives a capacity lower bound when both matrices must remain private from any ℓ colluding servers. Its proposed rate is below the one-sided capacity, and its behavior varies with the number of servers and colluders.
IV. FULLY SECURE MATRIX MULTIPLICATION WITH ℓCOLLUDING SERVERS
- The proposed fully secure scheme lower-bounds capacity while keeping both A and B secure from any ℓ colluding servers.The theorem states a lower bound on capacity.Source: §IV · p. 5
- With ℓ=1, the proposed fully secure rate is below the one-sided capacity, and both rates approach 1 as N grows, with Theorem 1 converging faster.Figure 2 compares the communication rates as N varies.Source: §IV · p. 5, Figure 2 · p. 6
- At fixed N=100, the proposed rate decreases faster as ℓ rises; the authors say the scheme cannot tolerate too many colluders because of the N term in (22).The rate comparison is against the one-sided capacity.Source: §IV · p. 6
A. Proof of Theorem 2
The fully secure scheme partitions both inputs and encodes them so polynomial interpolation recovers the desired submatrix products. Its rate counts the desired products among all server responses, and the authors prove information-theoretic security.
A. Proof of Theorem 2
- The user partitions A and B into r submatrices each, making AB consist of r² smaller matrix products.The scheme adds ℓ independent uniform random matrices for each private input before encoding.Source: A. Proof of Theorem 2 · p. 6
- Polynomial encoding gives each coefficient a distinct degree, so evaluations at distinct server points recover the products by interpolation; the entropy argument establishes information-theoretic security.The polynomial has degree (r+ℓ)²−1, and the security proof uses the independent random masks.Source: A. Proof of Theorem 2 · pp. 6–7
- The scheme recovers r² desired products from (r+ℓ)² server responses, yielding rate r²/(r+ℓ)².At least (r+ℓ)² responses are required for recovery.Source: A. Proof of Theorem 2 · p. 7
B. Improving Theorem 2 by Aligned Secret Sharing
Aligned secret sharing groups undesired terms into shared polynomial degrees while leaving desired products separately recoverable. In the (8, 1) example, this raises the rate from 4/9 to 1/2.
B. Improving Theorem 2 by Aligned Secret Sharing
- The general scheme gives each polynomial term a distinct degree, motivating alignment so desired AjBj′ products can remain individually recoverable.The section introduces aligned secret sharing as a way to improve the rate by grouping other, undesired terms.Source: B. Improving Theorem 2 by Aligned… · p. 8
- The encoding aligns undesired terms such as AjKB, KABj′, and KAKB while assigning desired products distinct degrees.The example splits each input into two submatrices and uses one random matrix for each input.Source: B. Improving Theorem 2 by Aligned… · p. 8
- A rate of 1/2 (4/8) exceeds the original scheme’s 4/9 rate in the (8, 1) example.The aligned polynomial has degree 7, so eight evaluations recover its coefficients, including four desired products.Source: B. Improving Theorem 2 by Aligned… · p. 8
V. CONCLUSIONS
The paper characterizes the one-sided model’s communication capacity and gives an achievable scheme for the fully secure model. It identifies a converse for the fully secure problem and extensions to other secure computation tasks as open problems.
V. CONCLUSIONS
- The one-sided model’s capacity is completely characterized as (N−ℓ)/N.Here B is public, A is private, and any ℓ servers may collude.Source: §V · p. 8
- For fully secure multiplication, the paper presents an achievable scheme and an improvement using aligned secret sharing.Both matrices are private, and any ℓ servers may collude.Source: §V · p. 8
- The authors leave a converse for fully secure multiplication and generalization to other secure distributed computation tasks as open problems.Source: §V · p. 8