{"id":"e2a845df-faaf-4936-a834-30da52db90f5","arxiv_id":"1909.00407","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Secure generalized PolyDot codes give a flexible recovery-threshold and communication-load trade-off for private and secure distributed matrix multiplication.","lead":"This paper designs codes that let a master server multiply two large matrices using cloud workers while keeping the matrices secret from colluding workers, and offers a tunable trade-off between how many workers must finish and how much data they must send. It also adds a variant that hides which public matrix is being multiplied, with an information-theoretic privacy guarantee.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"PSGPD privacy proof cites [38] only for query distribution; condition (9) is never established for the joint tuple (A_p^(κ), C_p^(κ)), so Theorem 3 is unproven as written.","rationale":"The reader's weakest assumption identifies the same load-bearing concern: Appendix A does not prove condition (9) for the full tuple seen by a worker. I agree that this is the point where Theorem 3 is least secure. The SGPD constructions in Theorems 1 and 2 have abbreviated security proofs, but those can be reconstructed from the stated entropy bounds and Vandermonde structure; the PSGPD privacy claim cannot be rescued by the one-line citation to [38]. The omitted joint-distribution argument is nontrivial because the returned product C_p^(κ) mixes the desired matrix, the random encoding of A, and the undesired library matrices. There is also a second, smaller gap in the same appendix: the constant term from undesired library matrices must be subtracted before interpolation, and the proof does not say so. Both gaps are repairable in principle, so the appropriate verdict remains CONDITIONAL rather than REJECT, matching the reader's verdict; no verdict change is needed.","tokens_in":18507,"tokens_out":26420,"duration_ms":255563,"concrete_test":"Use a small finite field, e.g., q=7, and instantiate the PSGPD construction of Theorem 3 with L=2, t=3, s=2, d=1, PC=1. Enumerate all random choices (fixed points, worker-specific points, random matrix R, and library matrices) and compute the exact joint distribution of (q_p^(κ), A_p^(κ), C_p^(κ)) for κ=1 and κ=2. If the two distributions differ, condition (9) fails as stated. Repeat with all random points restricted to F\\{0}; if equality holds, the scheme is repairable, but the written proof still omits the required joint-distribution argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing gap is in Appendix A's proof of Theorem 3. Condition (9) requires equality of the joint distribution (q_p^(κ), A_p^(κ), C_p^(κ), B) across indices κ. The appendix proves only that the query vectors q_p^(κ) are individually uniform, citing [38], and then asserts the privacy condition. It never derives the joint law. For s>1 this matters: A_p^(κ)=F_A(z_{κ,p}) and C_p^(κ)=A_p^(κ)·Σ_r F_{B(r)}(q_{p,r}); the joint law depends on κ through which coordinate of q_p is the worker-specific point. The cited result [38] cannot cover this. Moreover, as written the random points are drawn from F without excluding 0. If q_p has q_κ=0 and another coordinate nonzero, then under index κ the value A_p^(κ)=F_A(0) is constant, while under a different κ' with q_{κ'}≠0 the same A_p value is uniformly randomized by R; the joint distributions in (9) then differ. Restricting to nonzero points and supplying an independence argument for F_A(q_κ) may repair the claim, but that argument is absent from the paper. Separately, the recovery proof in Appendix A ignores the constant term Σ_{r≠κ} F_{B(r)}(z_r) in B_p^(κ); the master must subtract F_A(z)·const before interpolation, and the proof does not state this step.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributed matrix multiplication with security and privacy constraints. In the first setting, both matrices A and B must be kept secret from up to PC colluding workers; the authors propose secure generalized PolyDot (SGPD) codes and claim recovery-threshold formulas in Theorems 1 and 2 together with the communication load (16). In the second setting, one matrix is public and only its index must be kept private, with A still secret; the authors propose private and secure GPD (PSGPD) codes and claim the recovery threshold in Theorem 3 under PC=1. The paper also provides a latency analysis based on shifted-exponential computation times and the PR-th order statistic. The constructions build on the z-transform interpretation of generalized PolyDot codes and on PIR-style query generation.","tokens_in":18812,"tokens_out":25096,"duration_ms":268882,"significance":"If the proofs are completed, the SGPD codes would provide a genuinely flexible achievable trade-off between recovery threshold, communication load, and collusion threshold, generalizing the non-secure GPD codes. The PSGPD codes would similarly provide an achievable point for the joint secrecy-and-index-privacy problem. The explicit polynomial-degree derivations, the z-transform viewpoint, and the latency comparison are useful strengths, and the paper benchmarks against GPD codes and the PIR-based scheme [38]. However, the manuscript currently has load-bearing gaps in the statements and proofs of Theorems 2 and 3; the central claims are defensible but need substantial revision before they can be accepted.","major_comments":[{"comment":"The privacy proof does not establish condition (9). The appendix proves only that the query vectors q_p^{(κ)} have the same marginal distribution, citing [38], and then asserts that the privacy condition follows. Condition (9) requires equality of the full joint distribution (q_p^{(κ)}, A_p^{(κ)}, C_p^{(κ)}, B) across κ. Since A_p^{(κ)} = F_A(z_{κ,p}) and C_p^{(κ)} = A_p^{(κ)} Σ_{r=1}^L F_{B(r)}(q_r), the joint law depends on which coordinate of q_p is the worker-specific point z_{κ,p}; the proof never analyzes this joint law. Coordinate exchangeability of the i.i.d. query entries alone does not imply equality of the joint distribution for arbitrary library matrices B(r), because the functions F_{B(r)} need not be permutation polynomials. In addition, the query entries are drawn from F without excluding 0; if z_{κ,p}=0, then F_A(0) contains no random key term, so the security condition (8) fails and the distributions in (9) can differ. The authors need to specify nonzero evaluation points and provide a complete indistinguishability argument for the tuple (q_p, A_p, C_p, B), or else Theorem 3 is unproven as stated.","section":"Appendix A / Theorem 3, condition (9)"},{"comment":"The zero-block count in the s≥t case is inconsistent with the dimensions of the random parts. In (29) the random part R has t Δ'_PC block entries, and in (30) the random part R′ has d Δ'_PC block entries. The text says that the last s Δ'_PC − P_C block matrices are set to zero. For parameters such as t=3, s=6, d=3, P_C=1, this gives 6·1−1=5 zero blocks while A* has only 3 random blocks, so all random keys would be zeroed and the secrecy condition (3) would fail. The zero count should presumably be t Δ'_PC − P_C for A* and d Δ'_PC − P_C for B*, or an equivalent corrected condition. This must be repaired for Theorem 2 to define a valid construction.","section":"Section IV-B, Theorem 2 and equations (29)-(30)"},{"comment":"The recovery proof ignores the constant term in B_p^{(κ)}. Equation (44) gives B_p^{(κ)} = F_{B(κ)}(z_{κ,p}) + C_0 with C_0 = Σ_{r≠κ} F_{B(r)}(z_r), so each worker returns F_A(z_{κ,p})(F_{B(κ)}(z_{κ,p}) + C_0), not F_A(z) F_{B(κ)}(z). To interpolate F_A(z)F_{B(κ)}(z), the master must first subtract F_A(z_{κ,p}) C_0 from each received product; this is possible because the master knows F_A(z_{κ,p}) = A_p^{(κ)} and C_0 from the query, but the step is not stated. As written, the degree count in Appendix A proves the recovery threshold for the wrong polynomial.","section":"Appendix A, recovery step after equation (44)"},{"comment":"Step (b) of the entropy chain in (26) is not rigorous as written. It says that from 'PR polynomial evaluations' one can recover 2P_C unknowns 'given that we have P_R ≥ 2P_C', but A_P and B_P in (26) denote only the P_C colluding workers' encoded matrices, and P_R is not the number of colluding workers. The correct statement is that P_C evaluations of F_{a*}(z) suffice to recover the P_C random block matrices in A*, and P_C evaluations of F_{b*}(z) suffice to recover the P_C random block matrices in B*, because those blocks appear with distinct nonzero powers and the evaluation points are distinct and nonzero. This argument needs to be stated cleanly; the current wording with P_R is misleading.","section":"Section IV-A, proof of Theorem 1, equation (26)"}],"minor_comments":[{"comment":"There is a typo: 'he function H(·)' should read 'The function H(·)'.","section":"Section II-A"},{"comment":"The proof of Theorem 2 is only one sentence and does not spell out the security argument or the zero-block placement for the s≥t case. Given that the construction differs structurally from the s<t case, the proof should be expanded.","section":"Section IV-B, Theorem 2"},{"comment":"The notation 'dst∗' in the second line of (25) is easily misread; it should be written as 'd s t^*' or 'd·s·t^*'.","section":"Equation (25)"},{"comment":"In Example 2 the text writes 'T^comm_min = 1' but the model and equation (36) use the minimum computation time T^comp_min; this appears to be a typo.","section":"Example 2"},{"comment":"The complexity discussion counts only download communication and omits the upload cost of the query and encoded A_p. Since the paper compares with PIR-based schemes where upload cost is a known concern, a brief remark on this modeling choice would be helpful.","section":"Section V, Remark 3"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a timely and relevant problem, and the SGPD/PSGPD constructions are plausible. However, the current manuscript has two load-bearing gaps: the s≥t SGPD zero-block definition can eliminate the random keys, and the PSGPD privacy proof does not establish the required joint-distribution condition. Both are potentially repairable, but they require substantive additions rather than copy-editing. I would encourage the authors to supply a complete proof of condition (9) and to correct the zero-block counts in Theorem 2 before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper gives a genuinely useful trade-off curve: for secure distributed matrix multiplication, it achieves recovery threshold versus communication load under perfect secrecy, generalizing GPD codes. The SGPD code is a real extension—no one had addressed this trade-off with security before—and the recovery-threshold formulas in Theorems 1 and 2 check out against polynomial degree counts and reduce to known limits at PC=0. The z-transform interpretation is a nice way to see why the padding works. For the private version, the PSGPD idea of combining PIR query vectors with GPD encoding is sensible.\n\nThe soft spots are all in the proofs, not in the constructions. The security proof in Theorem 1 is sloppy: it uses PR where PC is meant, and step (b) asserts that the colluding workers' evaluations determine the random keys without giving the rank argument. That is almost certainly fixable—the evaluation points are distinct and the Vandermonde system is full rank—but it needs to be written down. The bigger problem is Theorem 3. Condition (9) requires the joint distribution of (q_p, A_p, C_p, B) to be independent of κ. The appendix proves only that the query vectors are uniform, cites [38], and then asserts the rest. It never gives the exchangeability argument over the random library matrices that would actually establish the equality. There is also a concrete bug: if the sampled point z_κ,p equals 0, then FA(0) is the unmasked block A_1,1, which leaks information. Excluding 0 fixes that, but it is not stated. The recovery proof also omits the step where the master subtracts the known constant term from the workers' products before interpolating.\n\nNone of these is a load-bearing flaw that sinks the paper. The constructions appear repairable, and the trade-off is new and worth knowing. But as written, Theorem 3 is not proven: the privacy condition is the central claim, and the appendix does not deliver it. I would send this to a serious referee. The right request would be: expand the privacy proof, tighten the security argument, and state the nonzero-point assumption. After that, it would be a solid contribution to the coded computation literature.","headline":"Useful achievable trade-off for secure coded matrix multiplication, but Theorem 3's privacy proof is under-powered; still deserves a serious referee.","tokens_in":19337,"tokens_out":14918,"would_cite":true,"duration_ms":131447,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A62","68P30","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A family of codes makes distributed matrix multiplication both private and flexible in cost.","keywords":["secure distributed matrix multiplication","generalized PolyDot codes","perfect secrecy","private information retrieval","recovery threshold","communication load","coded computation","straggler mitigation"],"falsifier":"Compute, for the PSGPD encoding with s>1, the mutual information or total variation between ($q_p^{{(κ)}}$, $A_p^{{(κ)}}$, $C_p^{{(κ)}}$) for two different indices κ; if any pair of distributions differs for a fixed worker p, condition (9) fails, and the recovery threshold of Theorem 3 becomes a secure-computation result rather than a private one. For SGPD, a direct check of the entropy chain in (26) on a small finite-field instance with s<t and P_C=2 would expose whether the claimed perfect secrecy holds.","tokens_in":18320,"feed_emoji":"🔐","tokens_out":4497,"duration_ms":39127,"temperature":0.7,"pith_summary":"This paper proposes coding schemes for distributed matrix multiplication where a master server wants the product C=AB from many workers without letting the workers learn the inputs. It claims two new code families achieve this: secure generalized PolyDot (SGPD) codes keep both matrices perfectly secret from up to P_C colluding workers, and private secure generalized PolyDot (PSGPD) codes keep one matrix secret while also hiding which public matrix from a library is being multiplied. Both families allow a flexible trade-off between recovery threshold, the number of workers that must finish, and communication load, the data downloaded, rather than optimizing one at the expense of the other. The paper also shows that the best code choice along this trade-off depends on whether the system bottleneck is communication rate or computation speed.","feed_headline":"Coded matrix multiplication gets private, tunable worker trade-offs","feed_subtitle":"New SGPD and PSGPD codes let system designers choose between fewer workers and less download while keeping data secret.","key_machinery":"The load-bearing object is the z-transform viewpoint of generalized PolyDot codes: matrices A and B are read as block sequences a and b, encoded by polynomial evaluation at worker-specific points, and the desired product blocks appear as the middle samples of the convolution a*b. The SGPD construction augments A and B with P_C random block matrices, arranged differently in the two cases s<t and s>=t so that the random terms in the product polynomial do not collide with the desired coefficient positions. The PSGPD construction attaches a private-information-retrieval query vector to each worker, so the desired public matrix is evaluated at a worker-specific random point while all undesired matrices are evaluated at common points, making the constant interference term that is later decoded away.","core_discovery":"The central discovery is that the generalized PolyDot z-transform construction can be extended with random padding blocks, chosen adaptively depending on whether s<t or s>=t, to satisfy information-theoretic secrecy without paying the full cost of a naive secure code. Theorem 1 states that for security level P_C<P, the SGPD code achieves the recovery threshold in (22) and communication load CL=P_R TD/(td) under the perfect secrecy condition I(A_P,B_P;A,B)=0. Theorem 2 covers s>=t with threshold (33). Theorem 3 states that by concatenating this idea with a private-information-retrieval query scheme, the PSGPD code achieves recovery threshold (40) with P_C=1 while satisfying both secrecy of A and index privacy of the selected public matrix. If correct, these are feasible operating points showing that security and privacy can be layered onto coded matrix multiplication at a tunable, not prohibitive, cost.","pith_inferences":["The same z-transform padding technique could plausibly extend to multilinear products or tensor contractions by stacking more sequences and placing random padding to avoid interference in coefficient positions; the paper does not explore this.","If the omitted joint-distribution argument for index privacy can be supplied, a natural next target is the colluding-worker case P_C>1 with low per-worker complexity, which the paper leaves open and notes can currently be handled only by a costly concatenation.","The latency formula suggests a concrete rate-aware code selection rule: measure the ratio of communication rate to computation speed and choose t,s,d accordingly, but the paper stops short of giving an explicit optimization policy."],"forward_implications":["For any fixed collusion threshold P_C, SGPD codes give a family of achievable (P_R, C_L) pairs parameterized by the block splitting (t,s,d), so system designers can choose the operating point that fits their network.","The recovery threshold expressions reduce to the known GPD thresholds when P_C=0, meaning the secure construction contains the non-secure state of the art as a special case.","The completion-time analysis shows the optimal code along the trade-off curve switches from low-communication-load codes at low communication rates to high-communication-load codes at high rates.","PSGPD codes achieve index privacy and secrecy of A with P_C=1, and their recovery threshold and communication load do not depend on the library size L.","The results imply that security and privacy constraints do not force a unique code choice; they enlarge the design space with explicitly quantified trade-offs."],"supporting_citations":[{"why":"Supplies the polynomial-code foundation for coded matrix multiplication that the GPD and secure constructions generalize.","marker":"[9]"},{"why":"Introduces PolyDot codes bridging polynomial and MatDot codes, the base trade-off that SGPD codes make secure.","marker":"[13]"},{"why":"Provides the generalized PolyDot (GPD) code whose recovery threshold and communication load are the non-secure baseline for this paper.","marker":"[14]"},{"why":"Introduces MatDot codes, a key endpoint of the communication-load versus recovery-threshold trade-off.","marker":"[15]"},{"why":"Gives a secure Lagrange-coding baseline with minimum recovery threshold for multilinear functions, which SGPD codes aim to generalize with flexible load.","marker":"[19]"},{"why":"Supplies the security proof style and capacity perspective for secure distributed matrix multiplication that the entropy argument in (26) follows.","marker":"[20]"},{"why":"Provides an entangled polynomial code with the same (P_R, C_L) properties as GPD codes, supporting the claimed optimality context.","marker":"[28]"},{"why":"Gives the private-information-retrieval query construction that PSGPD codes concatenate with the GPD encoding to hide the selected public matrix index.","marker":"[38]"},{"why":"Offers a related secure and private matrix multiplication scheme focused on download cost, against which PSGPD codes are positioned and compared.","marker":"[39]"}],"fun_headline_variants":["Secure matmul codes deliver perfect secrecy with flexible load","SGPD codes privately tune worker count and download cost","Tunable privacy for distributed matrix multiplication via SGPD","New codes make matrix products private with adjustable load"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The index-privacy guarantee of PSGPD codes depends on the whole tuple a worker sees, query, encoded A, and returned product, being identically distributed for every choice of public matrix, and the paper's proof verifies this only for the query vector while asserting the rest.","fun_headline_variants_meta":{"raw":{"variants":["Secure matmul codes deliver perfect secrecy with flexible load","SGPD codes privately tune worker count and download cost","Tunable privacy for distributed matrix multiplication via SGPD","New codes make matrix products private with adjustable load"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000705,"raw_usage":{"total_tokens":3222,"prompt_tokens":1034,"completion_tokens":2188,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":650,"completion_tokens_details":{"reasoning_tokens":2125}},"tokens_in":650,"tokens_out":2188,"duration_ms":17106,"temperature":1.0,"reasoning_tokens":2125,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:54:30.937591+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, for the PSGPD encoding with s>1, the mutual information or total variation between ($q_p^{{(κ)}}$, $A_p^{{(κ)}}$, $C_p^{{(κ)}}$) for two different indices κ; if any pair of distributions differs for a fixed worker p, condition (9) fails, and the recovery threshold of Theorem 3 becomes a secure-computation result rather than a private one. For SGPD, a direct check of the entropy chain in (26) on a small finite-field instance with s<t and P_C=2 would expose whether the claimed perfect secrecy holds.","supporting_citations":[{"cited_title":"Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,","cited_arxiv_id":null,"evidence_quote":"Supplies the polynomial-code foundation for coded matrix multiplication that the GPD and secure constructions generalize."},{"cited_title":"On the optimal recovery threshold of coded matrix mul- tiplication,","cited_arxiv_id":null,"evidence_quote":"Introduces MatDot codes, a key endpoint of the communication-load versus recovery-threshold trade-off."},{"cited_title":"On the Capacity of Secure Distributed Matrix Multiplication","cited_arxiv_id":"1806.00469","evidence_quote":"Supplies the security proof style and capacity perspective for secure distributed matrix multiplication that the entropy argument in (26) follows."},{"cited_title":"On the Upload versus Download Cost for Secure and Private Matrix Multiplication","cited_arxiv_id":"1906.10684","evidence_quote":"Offers a related secure and private matrix multiplication scheme focused on download cost, against which PSGPD codes are positioned and compared."}],"review_version":1}