{"id":"6817a95a-a17c-4cca-9414-ae44316efcf8","arxiv_id":"1908.04255","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A secure multi-party computation scheme for matrix polynomials uses polynomial sharing and claims large worker savings, but its transpose procedure is wrong, breaking the arbitrary-polynomial result.","lead":"This paper proposes a sharing scheme, called polynomial sharing, for secure multi-party computation of matrix polynomials over storage-limited workers, claiming to cut the required number of workers dramatically. The multiplication scheme is plausible, but the transpose operation used to support arbitrary polynomials is mathematically incorrect for block matrices, so the main general claim fails.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Procedure 4 does not compute A^T: it rearranges row blocks without transposing each block, so Algorithm 6's general-polynomial claim rests on a false primitive.","rationale":"The reader's weakest-assumption identification is accurate and is the single most load-bearing concern: the transpose primitive is used both to prepare transposed inputs and to re-share results in Algorithm 6, so a wrong Procedure 4 invalidates the central claim that any polynomial function can be computed with the stated worker count. I checked the derivation and the bug is concrete: Eq. (36) recovers A_{ij} from row-block shares, but Eq. (40) assembles these into L_i = [A_{i1};...;A_{ik}], which is not the i-th column block of A^T. The per-block transposes are missing; even the block-index layout is wrong. The multiplication and addition procedures appear algebraically plausible, and the worker-count matching the prior secure matrix multiplication literature gives the scheme some independent support, but it does not rescue the general polynomial claim. I did not find a more fundamental concern that would change the verdict: the transpose error alone is sufficient to reject the main theorem as stated.","tokens_in":31266,"tokens_out":9075,"duration_ms":96538,"concrete_test":"Run a literal implementation of Algorithm 4 over a small finite field, e.g., GF(101), with k=2, t=2, m=4, b=1, and N=3 evaluation points, using Def. 2 with random mask matrices. Share an asymmetric A partitioned into 2x2 blocks, e.g., A11=0, A12=[[0,1],[0,0]], A21=[[0,0],[1,0]], A22=0. After executing Steps 1-3, reconstruct Q(0) from the aggregated output shares; the random terms vanish at x=0. If Q(0) equals A rather than A^T=[[A11^T,A21^T],[A12^T,A22^T]], the transpose primitive is confirmed wrong and Theorem 3's correctness claim fails.","verdict_should_be":"REJECT","load_bearing_attack":"Procedure 4 (Transposing, Section VII-D) is load-bearing: Algorithm 6 Steps 7 and 9 invoke it to convert between shares of A and A^T, and the paper's claim of arbitrary polynomial computation depends on it. The procedure is incorrect except in trivial cases. From Eq. (35), F_i(x) is the i-th row-block of F_A and contains coefficients A_{i1},...,A_{ik}. Interpolation (36) correctly gives A_{ij} = sum_n r_n^{(j)} F_i(alpha_n). Substituting into Eq. (40) yields the i-th output column block L_i = [A_{i1};...;A_{ik}], whereas the i-th column block of A^T is [A_{1i}^T;...;A_{ki}^T]. The per-block transposes are omitted and the index order is wrong; for k=2 the procedure simply returns A, and for k=1 it returns A rather than A^T unless A is symmetric. Hence correctness condition (3) is not shown for any nontrivial transpose, and the claimed bound N*_G(t,k) <= min{2k^2+2t-3, k^2+kt+t-2} in Theorem 1 is unsupported. This is an internal algebraic error, not a disagreement with an external consensus.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes 'polynomial sharing,' a matrix-valued generalization of Shamir secret sharing aimed at secure multi-party computation when each worker can store only a 1/k fraction of each private input. It defines procedures for addition, multiplication by a constant, matrix multiplication, and matrix transposition, and it claims that these procedures can be concatenated to compute any polynomial function G of the private matrices. The headline result, Theorem 1, asserts that N*_G(t,k) is at most min{2k^2+2t-3, k^2+kt+t-2} workers, with information-theoretic privacy against any t-1 semi-honest workers and against the master beyond the final result. The proof relies on a probabilistic interpolation argument and on repeatedly recasting intermediate results as polynomial shares.","tokens_in":31521,"tokens_out":15465,"duration_ms":160238,"significance":"If the claimed bounds were correct, this would be a valuable contribution to coded secure computation for massive matrices: the multiplication procedure alone reduces the worker count from O(k^2 t) to O(k^2+kt), and the framework unifies addition, multiplication, and transposition under one sharing scheme. The multiplication core is algebraically natural, and the finite-field interpolation and Schwartz-Zippel arguments are standard. However, the general-polynomial claim depends critically on the transpose procedure, and that procedure is incorrect as written. Until the transpose primitive is repaired and the main theorem is re-proved, the central claim of the paper is not established.","major_comments":[{"comment":"The transpose procedure does not compute A^T. With A partitioned into k x k blocks A_{ij} of size (m/k)x(m/k), the i-th column block of A^T is [A_{i1}^T; A_{i2}^T; ...; A_{ik}^T], whereas Eq. (40) defines L_i = [A_{i1}; A_{i2}; ...; A_{ik}], omitting the per-block transpose. For k=1 the procedure returns A rather than A^T for non-symmetric A, so the failure is not limited to a boundary case. The step marked (a) in Eq. (40) is therefore false.","section":"VII-D, Eq. (40)"},{"comment":"Because Algorithm 6 invokes the transpose procedure in Steps 7 and 9, the incorrectness of Procedure 4 is load-bearing: the correctness condition (3) is not established for arbitrary polynomial functions G, and the bound in Theorem 1 is unsupported for any nontrivial transpose. A revision must supply a correct block-transpose operation (transposing each recovered block A_{ij}^T before forming the column blocks of A^T) and then re-verify correctness and privacy for the modified protocol.","section":"VIII, Algorithm 6 and Theorem 3"}],"minor_comments":[{"comment":"The presentation would benefit from writing A^T in block form before describing the procedure; doing so would make the missing per-block transpose visible and would also clarify the required indexing.","section":"VII-D"},{"comment":"The displayed equality H(M_S^{(r)} | ...) = H(R_S^{(r)} | ...) is not generally an equality, since the same message can be produced by different random choices. The subsequent argument only requires an inequality, so the proof can be repaired by replacing the equality with 'greater than or equal to'.","section":"Appendix B, Eq. (62)"},{"comment":"The index of the random matrix is written R_n in the definition text and R_j in Eq. (19), and the condition 'k+t-1<N' should be stated as 'N >= k+t-1' to match the usage in the rest of the paper.","section":"VI, Definition 2 and Eq. (19)"},{"comment":"The operand naming in these steps is confusing: the multiplication procedure expects A in (1,t,k) form and B in (k,t,k) form, but the steps describe converting F_{B^T} to F_B and F_{A^T} to F_A. Rephrasing with explicit input operands would improve readability.","section":"VIII, Algorithm 6, Steps 7-10"},{"comment":"The privacy condition uses both the messages M_{n'->n} and the source shares X~_{gamma n}, but the notation for the colluding set S is not harmonized across the two terms; a cleaner statement would make the conditioning set uniform.","section":"II, Eq. (4)"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about this paper. The polynomial-sharing framework is a real idea, but the claimed generality is broken by a wrong transpose. The multiplication and addition primitives look sound and match the known worker counts, but Algorithm 6 leans on a transpose that does not compute A^T.\n\nWhat is actually new: sharing a matrix as a polynomial in column blocks, with a worker-to-worker re-sharing step that keeps intermediate results in the same polynomial-share format. That composition trick is the interesting part. The paper also positions itself fairly against Lagrange coded computing, GASP codes, and the earlier ISIT version. The bound for one multiplication, min{2k^2+2t-3, k^2+kt+t-2}, agrees with prior art, which is a good sanity check.\n\nThe soft spot is Procedure 4. The aggregation step derives L_i = [A_{i1};...;A_{ik}] and then asserts this is the i-th column block of A^T. It is not. The i-th column block of A^T is [A_{i1}^T;...;A_{ik}^T] (or the analogous stack with the per-block transpose); what the procedure produces omits the transpose of each block. For scalar blocks it happens to work, but for block size greater than one it fails, and for k=2 it returns something that is not A^T. Algorithm 6 invokes this procedure twice per multiplication gate, so the claim that any polynomial can be computed with the stated N is unsupported. This is load-bearing, not a typo. A correct transpose would require each worker to transpose its own block after exchanging row-block shares, and that is not in the protocol.\n\nA secondary issue: the privacy proof in Appendix B has an entropy step that is underjustified. It may be repairable, but it glosses over the conditioning when bounding H(M) by H(R).\n\nBottom line: this is a useful framework for secure distributed matrix multiplication for the A^T B primitive, and possibly for general polynomials if transpose is repaired. As it stands, Theorem 3 overclaims. I would still send it to peer review—the good parts deserve scrutiny and the transpose might be fixable—but I would not accept it as is.","headline":"The polynomial-sharing framework is promising and the multiplication bound is solid, but the transpose procedure is wrong and Algorithm 6's general-polynomial claim collapses with it.","tokens_in":32017,"tokens_out":10034,"would_cite":false,"duration_ms":91850,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A62","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A polynomial-sharing scheme computes any polynomial of private matrices with at most min{2k^2+2t-3, k^2+kt+t-2} storage-limited workers, preserving privacy against t-1 colluding workers.","keywords":["secure multi-party computation","polynomial sharing","coded computation","massive matrix operations","information-theoretic privacy","distributed matrix multiplication","colluding workers"],"falsifier":"Set k=2, choose an A whose second column block is not the transpose of its first row block, run the transposing procedure (Algorithm 4) with t=2 and at least the claimed number of workers, and compare the reconstructed matrix with A^T: the second column block of the output will be [A_{21}; A_{22}] instead of [A_{12}^T; A_{22}^T], so a single concrete matrix exposes the failure.","tokens_in":31028,"feed_emoji":"🔐","tokens_out":8191,"duration_ms":81489,"temperature":0.7,"pith_summary":"This paper aims to show that a cluster of storage-limited, semi-honest workers can securely compute any polynomial function of massive private matrices using far fewer workers than previously proposed schemes. The authors introduce polynomial sharing, in which each source encodes column blocks of its matrix as low-degree coefficients of a polynomial and uses random matrices in high-degree slots, and they provide procedures for addition, multiplication by a constant, matrix multiplication, transposing, and changing the sharing parameter. Concatenating these procedures yields Algorithm 6, which the paper claims satisfies correctness and both worker and master privacy for every polynomial G. The quantitative claim is an upper bound of min{$2k^{2}$+2t-3, $k^{2}$+kt+t-2} on the number of workers, compared with $k^{2}$(2t-1) workers for the job-splitting-plus-conventional-MPC baseline for a single multiplication. If true, the worker count no longer grows with the degree of the polynomial or the number of input matrices.","feed_headline":"Polynomial sharing cuts worker count for private matrix math","feed_subtitle":"Any polynomial of massive private matrices runs on O(k^2) storage-limited workers, beating job-splitting MPC.","key_machinery":"The load-bearing object is the polynomial share F_{A,b,t,k}(x) = sum_{j=1}^k A_j $x^{{b(j-1)}}$ + sum_{j=1}^{t-1} R_j $x^{{k^2+j-1}}$, where A is split into k column blocks A_j and the R_j are random matrices of matching size. Multiplication works because F_{A,1,t,k}(x) and F_{B,k,t,k}(x) place the products A_i^T B_j at the coefficients indexed by i-1+k(j-1), and the random high-degree terms hide the data from any t-1 evaluations. The number of nonzero coefficients of their product, computed in Lemma 4, determines the worker count; recovery uses generalized Vandermonde interpolation, with Schwartz-Zippel-style arguments guaranteeing that random evaluation points are usable with high probability.","core_discovery":"The central discovery is that Shamir secret sharing can be generalized from scalars to matrices by placing the k column blocks A_1,...,A_k at exponents 0, b, 2b, and so on, while filling a separate high-degree region with random matrices. When a worker multiplies a (1,t,k)-share of A with a (k,t,k)-share of B, the block products A_i^T B_j land on distinct coefficients of the product polynomial, so interpolating the product polynomial from worker evaluations recovers every block of A^T B. Lemma 4 counts the nonzero coefficients of this product polynomial as min{$2k^{2}$+2t-3, $k^{2}$+kt+t-2}, and Theorem 2 shows that for that many evaluation points the needed interpolations succeed with probability approaching one for random points over a large field. The paper's main theorem states that this sharing scheme, together with the basic-operation procedures, computes any polynomial function with that many workers while keeping the inputs private from any t-1 colluding workers and from the master.","pith_inferences":["If the transposing step were repaired by transposing each block before stacking, the worker count would likely stay the same, since the same interpolation coefficients would be reused; this is a natural test for an implementation.","The same polynomial-sharing construction suggests a direct extension to rectangular matrices and to block partitions, along the lines of the entangled polynomial sharing sketched in Section IX, where the exponent spacing is chosen to match the block layout rather than a fixed k.","A practical deployment would need to quantify the field size and the probability that random evaluation points fail; the paper's Theorem 2 guarantees high probability for large fields but does not give explicit finite-field bounds."],"forward_implications":["Any polynomial G of the private matrices is computed with the same worker count as a single matrix multiplication, since each gate's output is recast as a polynomial share and the count does not grow with the degree of G.","Secure matrix multiplication uses at most min{2k^2+2t-3, k^2+kt+t-2} workers, compared with k^2(2t-1) workers for splitting the job and running conventional MPC.","For linear functions of the inputs, the scheme needs only k+t-1 workers.","A transposed operand inside a polynomial does not force extra workers: the transposing and parameter-changing procedures keep the shares in the same form."],"supporting_citations":[{"why":"Supplies the Shamir-sharing-based MPC scheme that polynomial sharing generalizes and that the worker-count comparisons are measured against.","marker":"[4]"},{"why":"Provides Shamir secret sharing, which polynomial sharing reduces to for k=1 and b=1.","marker":"[8]"},{"why":"Introduces the polynomial coding idea for distributed matrix multiplication that motivates the structure of the sharing polynomial.","marker":"[13]"},{"why":"Provides the fast interpolation method used by the master in the reconstruction phase.","marker":"[35]"},{"why":"Gives the generalized Vandermonde determinant formula used in the proof that the needed coefficient recovery is possible.","marker":"[43]"},{"why":"Shows the existence of evaluation points for which the relevant determinant polynomial is nonzero over a large field.","marker":"[45]"},{"why":"Supplies the Schwartz-Zippel lemma used to argue that random evaluation points work with probability approaching one.","marker":"[46]"},{"why":"Supplies the sparse polynomial identity test used alongside Schwartz-Zippel in the probabilistic correctness argument.","marker":"[47]"}],"fun_headline_variants":["Matrix Shamir gets a polynomial boost, fewer workers needed","Private matrix math: new sharing cuts worker count","Polynomial sharing for matrices: privacy with less resources","Secure MPC for massive matrices with reduced worker count","Matrix secret sharing: lower worker overhead for private ops"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole algorithm depends on the transposing procedure correctly turning shares of A into shares of A^T; for block size larger than one entry, that procedure constructs the column blocks without transposing the individual blocks, so if it is wrong the general polynomial claim fails.","fun_headline_variants_meta":{"raw":{"variants":["Matrix Shamir gets a polynomial boost, fewer workers needed","Private matrix math: new sharing cuts worker count","Polynomial sharing for matrices: privacy with less resources","Secure MPC for massive matrices with reduced worker count","Matrix secret sharing: lower worker overhead for private ops"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000294,"raw_usage":{"total_tokens":1744,"prompt_tokens":1015,"completion_tokens":729,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":631,"completion_tokens_details":{"reasoning_tokens":654}},"tokens_in":631,"tokens_out":729,"duration_ms":7404,"temperature":1.0,"reasoning_tokens":654,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:49:34.677815+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set k=2, choose an A whose second column block is not the transpose of its first row block, run the transposing procedure (Algorithm 4) with t=2 and at least the claimed number of workers, and compare the reconstructed matrix with A^T: the second column block of the output will be [A_{21}; A_{22}] instead of [A_{12}^T; A_{22}^T], so a single concrete matrix exposes the failure.","supporting_citations":[{"cited_title":"Completeness theorems for non-cryptographic fault-tolerant distributed computation,","cited_arxiv_id":null,"evidence_quote":"Supplies the Shamir-sharing-based MPC scheme that polynomial sharing generalizes and that the worker-count comparisons are measured against."},{"cited_title":"Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,","cited_arxiv_id":null,"evidence_quote":"Introduces the polynomial coding idea for distributed matrix multiplication that motivates the structure of the sharing polynomial."},{"cited_title":"On the computation of the determinant of a generalized vandermonde matrix,","cited_arxiv_id":null,"evidence_quote":"Gives the generalized Vandermonde determinant formula used in the proof that the needed coefficient recovery is possible."},{"cited_title":"An algebraic approach to network coding,","cited_arxiv_id":null,"evidence_quote":"Shows the existence of evaluation points for which the relevant determinant polynomial is nonzero over a large field."},{"cited_title":"Fast probabilistic algorithms for verification of polynomial identities,","cited_arxiv_id":null,"evidence_quote":"Supplies the Schwartz-Zippel lemma used to argue that random evaluation points work with probability approaching one."},{"cited_title":"Probabilistic algorithms for sparse polynomials,","cited_arxiv_id":null,"evidence_quote":"Supplies the sparse polynomial identity test used alongside Schwartz-Zippel in the probabilistic correctness argument."}],"review_version":1}