pith. sign in

arxiv: 1906.10684 · v1 · pith:TRDVDHLVnew · submitted 2019-06-25 · 💻 cs.IT · cs.CR· cs.DC· math.IT

On the Upload versus Download Cost for Secure and Private Matrix Multiplication

Wei-Ting Chang , Ravi Tandon This is my paper

Pith reviewed 2026-05-25 15:49 UTC · model grok-4.3

classification 💻 cs.IT cs.CRcs.DCmath.IT
keywords secure matrix multiplicationprivate information retrievalupload download tradeoffsecret sharingcoded PIRdistributed computationinformation theoretic privacy
0
0 comments X

The pith

The lower convex hull of (N/(K-1), (K/(K-1)) times the geometric sum up to M terms with ratio K/N) pairs for K=2 to N is achievable.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies upload versus download costs when a user computes the product of a secret matrix A with one matrix B_theta chosen from a public list of M candidates, using N servers, while ensuring no server learns anything about A and each server learns nothing about the index theta. It establishes that the lower convex hull of the listed (U, D) pairs is achievable by a scheme that combines secret sharing with coded private information retrieval. A reader would care because these pairs quantify the communication overhead required to enforce both matrix privacy and query privacy in distributed linear algebra. The construction improves on earlier schemes by attaining the entire convex hull rather than isolated operating points.

Core claim

The lower convex hull of the (upload, download) pairs (U, D) = (N/(K-1), (K/(K-1))(1 + (K/N) + … + (K/N)^{M-1})) for K = 2, …, N is achievable.

What carries the argument

A construction that uses secret sharing to protect matrix A together with coded private information retrieval to hide the index theta, realizing each listed cost pair.

If this is right

  • Each integer K from 2 to N yields an achievable operating point on the tradeoff curve.
  • The scheme improves the upload-download pairs attainable by all prior constructions for the same problem.
  • Convex combination of the listed points yields every point on the lower convex hull.
  • The same machinery applies for any number of servers N and any number of candidate matrices M.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same hull may serve as a benchmark when extending the setting to other linear functions such as matrix-vector multiplication.
  • Small explicit values of N, M and K could be used to verify the geometric-sum formula by direct construction.
  • The separation between upload and download phases suggests possible gains if the two phases could be interleaved.

Load-bearing premise

The model assumes honest-but-curious servers, information-theoretic privacy, and the exact definitions of upload and download cost given in the problem statement.

What would settle it

A concrete scheme achieving a cost pair strictly inside or below the claimed convex hull, or a proof that any of the boundary pairs for a given K cannot be attained, would falsify the result.

Figures

Figures reproduced from arXiv: 1906.10684 by Ravi Tandon, Wei-Ting Chang.

Figure 1
Figure 1. Figure 1: System model for secure and private matrix multiplication: multiply a confidential matrix [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison between our proposed scheme and the scheme in [12], with [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Downloading strategy for (N = 4, M = 2, K = 3). Repetition 1, the user ends up downloading all the blocks of W(1) once (12 from Round 1, and 4 from Round 2). In order to decode W(1), the user needs to download all 16 blocks two more times with different linear combinations. Thus, the user can follow the same downloading pattern with a right shift of indices in Repetition 2 and one more shift in Repetition … view at source ↗
read the original abstract

In this paper, we study the problem of secure and private distributed matrix multiplication. Specifically, we focus on a scenario where a user wants to compute the product of a confidential matrix $A$, with a matrix $B_\theta$, where $\theta\in\{1,\dots,M\}$. The set of candidate matrices $\{B_1,\dots,B_M\}$ are public, and available at all the $N$ servers. The goal of the user is to distributedly compute $AB_{\theta}$, such that $(a)$ no information is leaked about the matrix $A$ to any server; and $(b)$ the index $\theta$ is kept private from each server. Our goal is to understand the fundamental tradeoff between the upload vs download cost for this problem. Our main contribution is to show that the lower convex hull of following (upload, download) pairs: $(U,D)=(N/(K-1),(K/(K-1))(1+(K/N)+\dots+(K/N)^{M-1}))$ for $K=2,\dots,N$ is achievable. The scheme improves upon state-of-the-art existing schemes for this problem, and leverages ideas from secret sharing and coded private information retrieval.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies secure and private distributed matrix multiplication in which a user computes the product A B_θ (A private, θ private) from one of M public matrices stored at N honest-but-curious servers. The central claim is an achievability result: the lower convex hull of the normalized cost pairs (U, D) = (N/(K-1), (K/(K-1)) ∑_{i=0}^{M-1} (K/N)^i) for K = 2, …, N is attainable by combining additive/polynomial secret sharing (for A) with coded PIR (for θ).

Significance. If the constructions are correct, the paper supplies new achievable points on the upload-download tradeoff that improve on prior schemes by directly importing the standard normalized rates of secret sharing and geometric-series coded PIR. The result is a clean, parameter-free derivation from existing primitives and therefore strengthens the literature on information-theoretically private coded computation.

minor comments (2)
  1. Abstract, download-cost expression: the finite geometric sum is written with ellipsis; replacing it with explicit summation notation would improve readability without changing meaning.
  2. Problem statement: the precise normalization of upload and download costs (bits per matrix entry, relative to the size of A or B) should be restated once in the main text even if it follows the cited PIR literature.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the recognition that the result strengthens the literature by cleanly importing existing primitives, and the recommendation to accept.

Circularity Check

0 steps flagged

No circularity: pure achievability via external primitives

full rationale

The central claim is an achievability result: specific (U,D) pairs obtained from additive/polynomial secret sharing across N servers (with K-redundancy) combined with geometric-series coded-PIR queries are attainable, hence their convex hull is attainable. These costs match the normalized rates that follow directly from the standard definitions of those primitives; no parameter is fitted to the target result, no equation reduces to itself by construction, and the cited building blocks (secret sharing, coded PIR) are independent of the present paper. The security model is the conventional honest-but-curious information-theoretic model and is not justified by self-citation. Consequently the derivation chain contains no load-bearing self-referential step.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only abstract available; no explicit free parameters, axioms, or invented entities are described.

axioms (1)
  • domain assumption Information-theoretic privacy against honest-but-curious servers
    Implicit in the problem setup of secure and private matrix multiplication.

pith-pipeline@v0.9.0 · 5746 in / 1042 out tokens · 25165 ms · 2026-05-25T15:49:52.764793+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · 6 internal anchors

  1. [1]

    Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding,

    Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding,” CoRR, vol. abs/1801.07487, 2018. [Online]. Available: http://arxiv.org/abs/1801.07487

    work page arXiv 2018

  2. [2]

    On the Optimal Recovery Threshold of Coded Matrix Multiplication

    S. Dutta, M. Fahim, F. Haddadpour, H. Jeong, V . R. Cadambe, and P. Grover, “On the optimal recovery threshold of coded matrix multiplication,” CoRR, vol. abs/1801.10292, 2018. [Online]. Available: http://arxiv.org/abs/1801.10292

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  3. [3]

    Minimizing latency for secure distributed computing,

    R. Bitar, P. Parag, and S. E. Rouayheb, “Minimizing latency for secure distributed computing,” in 2017 IEEE International Symposium on Information Theory (ISIT) , Jun. 2017, pp. 2900–2904

    work page 2017

  4. [4]

    Limited-sharing multi-party computation for massive matrix operations,

    H. A. Nodehi and M. A. Maddah-Ali, “Limited-sharing multi-party computation for massive matrix operations,” in 2018 IEEE International Symposium on Information Theory (ISIT) , Jun. 2018, pp. 1231–1235

    work page 2018

  5. [5]

    Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy

    Q. Yu, N. Raviv, J. So, and A. S. Avestimehr, “Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy,” CoRR, vol. abs/1806.00939, 2018. [Online]. Available: http://arxiv.org/abs/1806.00939

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  6. [6]

    On the capacity of secure distributed matrix multiplication,

    W. Chang and R. Tandon, “On the capacity of secure distributed matrix multiplication,” in 2018 IEEE Global Communications Conference (GLOBECOM), Dec. 2018, pp. 1–6

    work page 2018

  7. [7]

    Secure distributed computing with straggling servers using polynomial codes,

    H. Yang and J. Lee, “Secure distributed computing with straggling servers using polynomial codes,” IEEE Transactions on Information F orensics and Security, vol. 14, no. 1, pp. 141–150, Jan 2019

    work page 2019

  8. [8]

    Rate-Efficiency and Straggler-Robustness through Partition in Distributed Two-Sided Secure Matrix Computation

    J. Kakar, S. Ebadifar, and A. Sezgin, “Rate-efficiency and straggler-robustness through partition in distributed two-sided secure matrix computation,” CoRR, vol. abs/1810.13006, 2018. [Online]. Available: http://arxiv.org/abs/1810.13006

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  9. [9]

    GASP codes for secure distributed matrix multiplication,

    R. G. L. D’Oliveira, S. E. Rouayheb, and D. A. Karpuk, “GASP codes for secure distributed matrix multiplication,” CoRR, vol. abs/1812.09962, 2018. [Online]. Available: http://arxiv.org/abs/1812.09962

    work page arXiv 2018

  10. [10]

    Distributed and Private Coded Matrix Computation with Flexible Communication Load

    M. Aliasgari, O. Simeone, and J. Kliewer, “Distributed and private coded matrix computation with flexible communication load,” CoRR, vol. abs/1901.07705, 2019. [Online]. Available: http://arxiv.org/abs/1901.07705

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  11. [11]

    On the Capacity of Secure Distributed Fast Fourier Transform,

    W. Chang and R. Tandon, “On the Capacity of Secure Distributed Fast Fourier Transform,” in 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP) , Nov. 2018, pp. 653–657

    work page 2018

  12. [12]

    Private Secure Coded Computation

    M. Kim and J. Lee, “Private secure coded computation,” CoRR, vol. abs/1902.00167, 2019. [Online]. Available: http: //arxiv.org/abs/1902.00167

    work page internal anchor Pith review Pith/arXiv arXiv 1902

  13. [13]

    The capacity of private information retrieval,

    H. Sun and S. A. Jafar, “The capacity of private information retrieval,” IEEE Transactions on Information Theory , vol. 63, no. 7, pp. 4075–4088, Jul. 2017

    work page 2017

  14. [14]

    The capacity of private information retrieval from coded databases,

    K. Banawan and S. Ulukus, “The capacity of private information retrieval from coded databases,” IEEE Transactions on Information Theory, vol. 64, no. 3, pp. 1945–1956, March 2018

    work page 1945

  15. [15]

    The Capacity of Private Computation

    H. Sun and S. A. Jafar, “The capacity of private computation,” CoRR, vol. abs/1710.11098, 2017. [Online]. Available: http://arxiv.org/abs/1710.11098

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  16. [16]

    Private function retrieval,

    M. Mirmohseni and M. A. Maddah-Ali, “Private function retrieval,” in 2018 Iran Workshop on Communication and Information Theory (IWCIT), Apr. 2018, pp. 1–6

    work page 2018

  17. [17]

    Private computation of systematically encoded data with colluding servers,

    D. Karpuk, “Private computation of systematically encoded data with colluding servers,” in 2018 IEEE International Symposium on Information Theory (ISIT) , Jun. 2018, pp. 2112–2116

    work page 2018

  18. [18]

    Achievable rate of private function retrieval from MDS coded databases,

    S. A. Obead and J. Kliewer, “Achievable rate of private function retrieval from MDS coded databases,” in 2018 IEEE International Symposium on Information Theory (ISIT) , Jun. 2018, pp. 2117–2121

    work page 2018