{"id":"0e94cda5-4b23-4662-9180-aa87a945d528","arxiv_id":"1908.06957","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The capacity of secure distributed batch matrix multiplication is characterized in several parameter regimes, and the previously claimed general capacity formula is shown to be incorrect.","lead":"This paper finds how much data a user must download from secure servers to compute many matrix products at once, when no group of servers may learn the inputs. It settles the best possible download rate for several settings and shows a previously published general formula was wrong.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 1's dimension-independent capacity claim is not proven: the paper lacks any lower bound C(AB,φ) ≥ 1−2X/N for rank-deficient K < min(L,M), so the infimum may be lower than 1−2X/N.","rationale":"The reader's verdict accepts the paper with high confidence and identifies Lemma 6 as the weakest assumption. My review finds a different, load-bearing gap: the proof of Corollary 1. The paper's main converse and achievability theorems are internally consistent, and the connection to MM-XSTPIR in Theorem 1 appears valid under the stated security and query-storage independence assumptions. However, the dimension-independent capacity characterization is a headline result, and it is not a logical consequence of the cited cases. Cases (32),(34),(35) only provide upper bounds on the dimension-independent capacity in the sense of exhibiting dimensions with small capacity; they do not prove that every dimension has capacity at least 1−2X/N. The rank-deficient regime K < min(L,M) is exactly where the paper's lower bounds are weakest: neither the general scheme nor the CSA scheme achieves 1−2X/N in that regime, as shown by the concrete example L=M=4, K=3, N=5, X=1. The paper does not claim a universal lower bound, and in fact leaves square-matrix capacity open, so the corollary is premature. This does not undermine the other capacity results, which are stated for specific asymptotic regimes, but it means the claim that the dimension-independent capacity is fully characterized is not proven. The appropriate verdict is CONDITIONAL: accept subject to either proving the missing lower bound or qualifying Corollary 1 to reflect that the exact dimension-independent capacity remains open.","tokens_in":29256,"tokens_out":33023,"duration_ms":331822,"concrete_test":"Re-derive Corollary 1 by listing every lower bound on C(AB,φ) proved in Section 5 and checking whether any applies to K < min(L,M) with finite dimensions. For the concrete instance L=M=4, K=3, N=5, X=1, the CSA scheme achieves (3/5)(15/16)=9/16=0.5625 and the general scheme achieves (4/5)(15/24)=1/2=0.5, both below the claimed 3/5. Determine whether any scheme in the paper reaches ≥3/5 for this instance, or alternatively whether an upper bound ≤9/16 can be derived; either outcome settles whether the corollary's infimum claim is supported. If neither is found, the corollary must be revised to state only that the dimension-independent capacity is at most 1−2X/N and equals this value if the missing lower bound is conjectured.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Corollary 1 states that the dimension-independent capacity of SDBMM(AB,φ) is 1−2X/N for N>2X and 0 for N≤2X, and says it follows immediately from cases (32),(34),(35) of Theorem 2. Those cases supply sequences of dimensions (K/min(L,M)→∞) along which capacity tends to the stated values; they show the infimum over all dimensions is at most 1−2X/N (or at most 0), but they do not show the required matching lower bound C(AB,φ) ≥ 1−2X/N for every L,K,M. The only general lower bound in the paper is Remark 3.4, which assumes K ≥ min(L,M). For K < min(L,M), the two explicit achievability schemes are the general scheme of Section 5.1 and the CSA scheme of Section 5.2, with rates (1−X/N)·H/(K(L+M)) and (1−2X/N)·H/(LM), where H = LK+KM−K² < LM. For N=5, X=1, L=M=n, K=n−1, the CSA rate is (3/5)(n²−1)/n², strictly below 3/5 for every finite n, and the general-scheme rate is (4/5)(n²−1)/(2n(n−1)) ≈ 2/5, also below 3/5. The paper provides no scheme achieving ≥3/5 in this rank-deficient regime, and its own conclusion leaves L=K=M>1 open. Thus Corollary 1 is stronger than the proven results: the dimension-independent capacity is not established as 1−2X/N unless an additional universal lower bound for K<min(L,M) is supplied.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies secure distributed batch matrix multiplication (SDBMM), where sequences of matrix products A_s B_s are retrieved from N servers that store the matrices A and B in X-secure coded form. It defines rate as the ratio of the entropy of the desired products to the average download, and capacity as the supremum over schemes and batch sizes. The authors prove upper bounds by connecting SDBMM to a new multi-message X-secure T-private information retrieval (MM-XSTPIR) problem and proving an upper bound on the latter. They prove capacity results and asymptotic characterizations for several variants: SDBMM(AB,φ), SDBMM(B,A), SDBMM(B,B), SDBMM(B,φ), and SDBMM(AB,B). Achievability uses a general download-A-and-B scheme, a cross-subspace alignment scheme, and a monomorphic transformation turning scalar multiplication into scalar addition. The paper also claims that the previously reported two-sided secure SDMM capacity (1-2X/N)^+ is false in general, and it states dimension-independent capacities as corollaries.","tokens_in":29572,"tokens_out":29060,"duration_ms":296729,"significance":"If the main results hold, the paper makes a substantial contribution: it introduces the MM-XSTPIR connection, gives the first capacity characterizations for secure batch matrix multiplication in several parameter regimes, exactly settles the outer-product case K=1, asymptotically settles the long inner-product case, and provides a counterexample to a previously published converse. The achievable schemes are explicit and the converse proofs are largely self-contained. The main caveat is that one of the advertised corollaries, the dimension-independent capacity of SDBMM(AB,φ), is not established by the supplied arguments.","major_comments":[{"comment":"The lower-bound half of Corollary 1 is not proved. By the definition in Section 2.1, the dimension-independent capacity is the infimum of C(AB,φ) over all L,K,M. For N>2X, the claimed value 1-2X/N therefore requires C(AB,φ) ≥ 1-2X/N for every triple (L,K,M). Theorem 2 cases (34) and (35) are asymptotic statements: they give sequences of dimensions with K/min(L,M)→∞ along which capacity tends to 0 or to 1-2X/N. These sequences show only that the infimum is no larger than the stated values; they do not show that no finite dimension has smaller capacity. The only lower bounds proved for finite dimensions are the general scheme of Section 5.1 and the CSA scheme of Section 5.2. When K<min(L,M), Lemma 2 gives H_q(AB)=LK+KM-K^2, so the CSA scheme achieves (1-2X/N)(LK+KM-K^2)/(LM), which is strictly below 1-2X/N, and the general scheme achieves (1-X/N)(LK+KM-K^2)/(LK+KM), which is also below 1-2X/N for the family L=M=n, K=n-1 with n≥3 (e.g., N=5, X=1 gives rates 2(n+1)/(5n) and (3/5)(n^2-1)/n^2, both < 3/5 for every finite n). Remark 3.4 supplies a lower bound only for K≥min(L,M), and Section 6 explicitly leaves the square-matrix case open. Thus the lower-bound half of Corollary 1 is unsupported as written; the authors must either provide a universal lower bound for K<min(L,M) or revise the corollary to a weaker, asymptotic statement.","section":"Section 3.4, Corollary 1"}],"minor_comments":[{"comment":"The arrow notation 'C(AB,φ)→...' is used without explicitly stating the order of limits; the theorem should state that the limit is taken with q→∞ and then with the indicated dimension ratio tending to infinity (or jointly, as appropriate).","section":"Theorem 2"},{"comment":"The phrase 'presents a contradiction that calls into question the converse bound in [9]' would be more precise as 'provides a counterexample to the converse bound in [9]', since the issue is with a claimed theorem in the prior work, not with the logical framework of the present paper.","section":"Remark 4"},{"comment":"In the rate computation near Eq. (159), the term 2SN log_q(2) accounts for secret-sharing the zero-indicator bits; this is correct but could use one sentence explaining that each indicator is secret-shared across all N servers, so the total download of indicators is 2SN bits.","section":"Section 5.4.1"}],"recommendation":"major_revision","confidential_remarks":"The main gap is local but load-bearing: Corollary 1's lower-bound claim needs either a new proof or a weakened statement. I would not reject the paper, because the other theorems and the achievability schemes appear sound and valuable, and the issue is fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a genuine contribution, and the main asymptotic capacity results look right, but the stress-test note is correct about Corollary 1. The dimension-independent capacity is not established by the arguments given.\n\nWhat is genuinely new: the SDBMM formulation, the reduction to MM-XSTPIR, the new converse for MM-XSTPIR in Appendix A, and the CSA plus multiplication-to-addition construction. The paper also gives a concrete counterexample to the previously published claim that two-sided secure SDMM capacity is always (1-2X/N)^+, and the K=1 outer-product result, capacity 1-X/N, is a clean exact characterization that contradicts prior work. The converse chain through Lemma 6 and the Han's inequality steps is internally consistent as far as I checked. The field-size limits are handled carefully enough for this literature.\n\nNow the soft spot. Corollary 1 claims the infimum over all dimensions is 1-2X/N for N>2X. Cases (34) and (35) produce sequences of dimensions with K/min(L,M) -> infinity along which capacity tends to the claimed values. That shows the infimum is at most 1-2X/N (or at most 0), not that it is at least 1-2X/N for every L,K,M. There is no universal lower bound for K < min(L,M), the rank-deficient regime. Both explicit achievability schemes fall short there: with N=5, X=1, L=M=n, K=n-1, the CSA rate is (3/5)(n^2-1)/n^2 and the general-scheme rate is about 2/5, neither reaching 3/5. The paper itself leaves L=K=M>1 open, which is consistent with the gap. So the sentence that Corollary 1 follows immediately is not right. I suspect the same gap affects the other dimension-independent corollaries unless a separate universal lower bound exists; I do not see one in the manuscript.\n\nThis does not sink the paper. The exact and asymptotic capacity characterizations are the core contribution, and those arguments appear sound. But the dimension-independent results are advertised as settled, and the current proof does not support them.\n\nBottom line: send it to peer review. A serious referee should ask the authors to supply a genuine lower bound for K < min(L,M) or soften the dimension-independent statements. I would still cite the asymptotic and K=1 results, and I would bring it to a reading group.","headline":"Real correction of the prior SDMM capacity formula and a solid new PIR connection, but the dimension-independent capacity claims overreach: the proof supplies asymptotic sequences, not the required universal lower bound for rank-deficient matrices.","tokens_in":30131,"tokens_out":11359,"would_cite":true,"duration_ms":118845,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that the capacity of secure distributed batch matrix multiplication depends on matrix dimensions, and that for a batch of outer products it is exactly $1 - X/N$, contradicting the previously reported general bound $(1…","keywords":["secure distributed matrix multiplication","batch matrix multiplication","capacity","information-theoretic security","private information retrieval","cross-subspace alignment","outer products","dimension-independent capacity"],"falsifier":"For $N=3$, $X=1$, $K=1$, the paper's capacity formula gives $C(AB,\\phi)=1-X/N=2/3$. A concrete check is to search for any valid $X$-secure scheme in this smallest case whose rate exceeds $2/3$, or to prove a converse below $2/3$; either would refute Theorem 2. The same test applies to the general geometric bound in case (38): any explicit scheme with rate above that bound in an intermediate-dimension regime would falsify the converse.","tokens_in":29012,"feed_emoji":"🛡️","tokens_out":9787,"duration_ms":88492,"temperature":0.7,"pith_summary":"Secure distributed batch matrix multiplication (SDBMM) asks how many bits a user must download to compute a sequence of products $A_s B_s$ from $N$ servers that store $A$ and $B$ in $X$-secure coded form, so that any $X$ colluding servers learn nothing. The paper establishes that the capacity is not a single dimension-independent number: it depends on the matrix dimensions $L, K, M$ as well as on $N$ and $X$. In particular, when each $A_s$ and $B_s$ is a vector, so the products are outer products ($K=1$), the capacity is exactly $1 - X/N$, which exceeds the previously claimed general bound $(1 - 2X/N)^+$ for two-sided secure matrix multiplication. More generally, the paper gives matching upper and lower bounds in several parameter regimes and identifies the dimension-independent capacity as $0$ for $N \\le 2X$ and $1 - 2X/N$ for $N > 2X$. The result matters because it shows the communication cost of secure distributed matrix multiplication can be much lower than earlier analyses suggested, and it points to a previously unnoticed connection to multi-message $X$-secure $T$-private information retrieval.","feed_headline":"Outer-product batches break the old secure matrix multiplication bound","feed_subtitle":"The true capacity depends on matrix shape, and for K=1 it exceeds the previously claimed 1 − 2X/N.","key_machinery":"Two ingredients carry the argument. First, Lemma 1 converts any SDBMM scheme without $A$ as side information into a multi-message $X$-secure $T$-private information retrieval (MM-XSTPIR) scheme, thinking of $A$ as the stored messages and $B$ as the user's private query, so the new MM-XSTPIR upper bound in Theorem 1 bounds SDBMM rate from above. Second, the achievable schemes use cross-subspace alignment: the servers' stored shares are random linear combinations with poles at distinct constants $f_s + \\alpha_n$, so the downloads concentrate the desired products $A_s B_s$ in decodable subspaces while noise terms align in separately decodable subspaces. For the scalar and outer-product regimes, a transformation maps the multiplicative group of the finite field to the additive group modulo $q-1$, realized inside a larger prime field, turning scalar multiplication into scalar addition; this is retrieved with an $X$-secure MDS code. The matrix-invertibility lemma for the cross-subspace decoding matrix is the technical keystone, and the entropy calculations for products of random matrices fix the normalization $H_q(AB)$.","core_discovery":"The paper establishes that the capacity of SDBMM$(AB,\\phi)$, where both $A$ and $B$ are held in $X$-secure coded form and the user has no side information, is characterized by Theorem 2. For $N > X$ and $K = 1$ (each product is an outer product of vectors), the capacity is exactly $1 - X/N$. When $K/\\min(L,M) \\to \\infty$, the capacity tends to $0$ for $N \\le 2X$ and to $1 - 2X/N$ for $N > 2X$; when $K \\le \\min(L,M)$ and $\\max(L,M)/K \\to \\infty$, it tends to $1 - X/N$. For intermediate dimensions the paper proves upper bounds $(1 - X/N)\\min(L,M,K)/K$ in the regime $2X \\ge N > X$ and the geometric-series bound $(1 - X/N)\\left(1 + \\frac{X}{N-X} + \\cdots + \\left(\\frac{X}{N-X}\\right)^{\\lfloor K/\\min(L,M,K)\\rfloor -1}\\right)^{-1}$ for $N > 2X$. The dimension-independent capacity, minimized over all matrix dimensions, is $0$ for $N \\le 2X$ and $1 - 2X/N$ for $N > 2X$. The paper further argues that the previously reported general two-sided secure capacity $(1 - 2X/N)^+$ cannot be correct, because the $K=1$ case already achieves the larger rate $1 - X/N$, so the true capacity genuinely depends on $L, K, M$.","pith_inferences":["Beyond the paper: if the scalar-multiplication-to-addition transformation can be generalized from $K=1$ to square matrices, the capacity for $L=K=M>1$ may exceed the geometric-series upper bounds, since the $K=1$ case already breaks the previously accepted answer.","Beyond the paper: the SDBMM-to-MM-XSTPIR connection means that any future improvement to MM-XSTPIR capacity, or to the related private computation problem, will automatically give tighter converses for these matrix multiplication problems; conversely, better SDBMM schemes would provide new lower bounds for those PIR problems.","Beyond the paper: the dimension-dependence of capacity has a practical reading: a system designer can change the communication cost of security by reorganizing a computation into outer products, inner products, or square blocks, because these regimes have genuinely different capacities.","Beyond the paper: the scalar scheme's rate approaches $1 - X/N$ only as the field size $q \\to \\infty$, since the zero-indicator overhead and the prime-field embedding vanish only in that limit; for small $q$, the exact finite-field capacity is not addressed and could be strictly lower."],"forward_implications":["For batches of outer products of vectors ($K=1$), the capacity is exactly $1 - X/N$, so a user can compute all $S$ products by downloading only the $N/(N-X)$ overhead factor, independent of $L$ and $M$.","For batches of inner products of long vectors ($L=M=1$, $K \\to \\infty$), the capacity approaches $1 - 2X/N$ when $N > 2X$, and approaches $0$ when $N \\le 2X$; in this regime two-sided security costs twice the overhead.","The dimension-independent capacity of SDBMM$(AB,\\phi)$ is fully settled: it is $0$ for $N \\le 2X$ and $1 - 2X/N$ for $N > 2X$.","The previous claim that the general two-sided secure capacity is $(1 - 2X/N)^+$ is false, because the $K=1$ outer-product scheme already achieves $1 - X/N > (1 - 2X/N)^+$ whenever $X>0$ and $N>X$.","For the one-sided secure setting SDBMM$(B,A)$, the capacity is $1 - X/N$ independent of matrix dimensions, matching the prior result, and the paper supplies an achievable scheme that works for all $K < L$ cases."],"supporting_citations":[{"why":"Establishes the prior two-sided secure SDMM capacity claim $(1 - 2X/N)^+$ that this paper contradicts with the $K=1$ outer-product rate $1 - X/N$.","marker":"[9]"},{"why":"Defines the one-sided secure distributed matrix multiplication problem and gives the baseline that Theorem 3 for SDBMM$(B,A)$ matches and extends.","marker":"[8]"},{"why":"Introduces cross-subspace alignment and the $X$-secure $T$-private PIR structure that Theorem 1 and the CSA achievable schemes build on.","marker":"[15]"},{"why":"Provides multi-message PIR capacity results that motivate the MM-XSTPIR problem used in the SDBMM converses.","marker":"[13]"},{"why":"Supplies the entropy averaging inequality used in the converse proofs to reduce the bound over all colluding sets.","marker":"[19]"},{"why":"Gives the probability that a random square matrix over a finite field is singular, used in Lemma 2 to compute entropies of products of random matrices.","marker":"[33]"}],"fun_headline_variants":["Secure batch matrix multiplication capacity depends on shape","Outer-product case achieves rate 1−X/N, beating old bound","Old secure batch matrix bound broken: capacity is dimension-dependent","For K=1, secure batch matrix multiplication hits optimal rate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"All converse bounds rely on the MM-XSTPIR upper bound, which assumes perfect $X$-security of the stored data and independence between the user's queries and the server storage; if colluding servers were allowed to learn partial information about $A$ or $B$, the upper bounds would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Secure batch matrix multiplication capacity depends on shape","Outer-product case achieves rate 1−X/N, beating old bound","Old secure batch matrix bound broken: capacity is dimension-dependent","For K=1, secure batch matrix multiplication hits optimal rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001339,"raw_usage":{"total_tokens":5645,"prompt_tokens":1346,"completion_tokens":4299,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":962,"completion_tokens_details":{"reasoning_tokens":4230}},"tokens_in":962,"tokens_out":4299,"duration_ms":36138,"temperature":1.0,"reasoning_tokens":4230,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:33:15.866004+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $N=3$, $X=1$, $K=1$, the paper's capacity formula gives $C(AB,\\phi)=1-X/N=2/3$. A concrete check is to search for any valid $X$-secure scheme in this smallest case whose rate exceeds $2/3$, or to prove a converse below $2/3$; either would refute Theorem 2. The same test applies to the general geometric bound in case (38): any explicit scheme with rate above that bound in an intermediate-dimension regime would falsify the converse.","supporting_citations":[{"cited_title":"On the Capacity and Straggler-Robustness of Dis- tributed Secure Matrix Multiplication,","cited_arxiv_id":null,"evidence_quote":"Establishes the prior two-sided secure SDMM capacity claim $(1 - 2X/N)^+$ that this paper contradicts with the $K=1$ outer-product rate $1 - X/N$."},{"cited_title":"Cross subspace alignmen t and the asymptotic capacity of x -secure t -private information retrieval,","cited_arxiv_id":null,"evidence_quote":"Introduces cross-subspace alignment and the $X$-secure $T$-private PIR structure that Theorem 1 and the CSA achievable schemes build on."},{"cited_title":"Multi-message Private Infor mation Retrieval: Capacity Results and Near-optimal Schemes,","cited_arxiv_id":null,"evidence_quote":"Provides multi-message PIR capacity results that motivate the MM-XSTPIR problem used in the SDBMM converses."},{"cited_title":"How Often do Determinants Over Finite F ields Vanish?","cited_arxiv_id":null,"evidence_quote":"Gives the probability that a random square matrix over a finite field is singular, used in Lemma 2 to compute entropies of products of random matrices."}],"review_version":1}