Secure Coded Multi-Party Computation for Massive Matrix Operations

Hanzaleh Akbari Nodehi; Mohammad Ali Maddah-Ali

REVIEW 2 major objections 5 minor 1 cited by

Secure Coded Multi-Party Computation for Massive Matrix Operations

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 1908.04255 v2 pith:QJFDRG2J submitted 2019-08-12 cs.IT math.IT

Hanzaleh Akbari Nodehi , Mohammad Ali Maddah-Ali This is my paper · ORCID

classification cs.ITmath.IT MSC 94A6268W15

keywords securemulti-partycomputationpolynomialsharingcodedmassivematrixoperationsinformation-theoreticprivacydistributedmultiplicationcolludingworkers

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What 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.

The 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.

A 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).

Bottom 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.

Referee Report

2 major / 5 minor

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.

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 (2)

[VII-D, Eq. (40)] 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.
[VIII, Algorithm 6 and Theorem 3] 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.

minor comments (5)

[VII-D] 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.
[Appendix B, Eq. (62)] 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'.
[VI, Definition 2 and Eq. (19)] 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.
[VIII, Algorithm 6, Steps 7-10] 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.
[II, Eq. (4)] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the scheme is derived from first principles with interpolation and Schwartz-Zippel, and self-citations are not load-bearing.

full rationale

The paper's derivation is self-contained rather than circular. Polynomial sharing is defined explicitly in Definition 2, and each basic procedure (addition, multiplication by constant, matrix multiplication, transposing, and parameter change) is verified by direct polynomial manipulation: e.g., Eq. (24) shows the sum of two sharing polynomials is a sharing of the sum, Eq. (33) shows the aggregated messages form a sharing of A^T B via the interpolation relation (29), and Eq. (45) similarly justifies the parameter-change procedure. The key existence statement (Theorem 2) is proved in Appendix A using generalized Vandermonde matrices, Schur polynomials, and the Schwartz-Zippel lemma; it does not invoke the paper's own prior results as the proof of the existence of suitable evaluation points. The only self-citations, to the authors' conference papers [1] and [23], are used for historical comparison and as earlier statements of the same construction, not as load-bearing justification for the present claims. No fitted parameter is renamed as a prediction, and no quantity used as an input is also presented as an output. Even the transpose procedure, whatever its algebraic merits, is presented as an explicit construction rather than imported from a prior claim. Thus there is no circular step by the criteria of this review.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The scheme uses no fitted parameters and introduces no new physical or mathematical entities. It relies on standard interpolation, finite-field randomness, and the stated trust model; the only nonstandard assumptions are the correctness of the transpose procedure and a bijectivity claim in the privacy proof, both of which are load-bearing and the first is false.

assumptions (5)

standard math Polynomial interpolation over finite fields recovers all coefficients from N distinct evaluations when N matches the number of nonzero coefficients.
Invoked in Theorem 2 and the addition/multiplication procedures to justify reconstruction from worker outputs; standard result.
standard math Schwartz-Zippel guarantees existence of evaluation points alpha_i making generalized Vandermonde and coefficient matrices full rank with high probability as |F| tends to infinity.
Used in Theorem 2 proof to support the probabilistic correctness of interpolation.
domain assumption Workers are semi-honest and do not collude with the master; all links are secure and error-free; each share size is at most 1/k of the input.
Stated in Section II as the problem setting; the privacy conditions (4) and (5) depend on these trust and channel assumptions.
ad hoc to paper The transpose procedure correctly produces the matrix transpose, specifically that [A_{i1};...;A_{ik}] equals the i-th column block of A^T.
Assumed in Algorithm 6 Steps 7 and 9 and in Section VII-D Eq. (40); for block size m/k > 1 this is false, so the assumption is a load-bearing error.
ad hoc to paper In the privacy proof, the map from fresh random matrices to the t-1 messages received by the colluding set is bijective at each round.
Needed for the equality H(M|cond) = H(R|cond) in Appendix B Eq. (62); not proven in the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Secure Coded Multi-Party Computation for Massive Matrix Operations." pith.science (2026). https://pith.science/paper/QJFDRG2J

@misc{pith2026190804255,
  author       = {Pith},
  title        = {Pith review of: Secure Coded Multi-Party Computation for Massive Matrix Operations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QJFDRG2J}},
  note         = {Machine review of arXiv:1908.04255}
}

abstract

In this paper, we consider a secure multi-party computation problem (MPC), where the goal is to offload the computation of an arbitrary polynomial function of some massive private matrices (inputs) to a cluster of workers. The workers are not reliable. Some of them may collude to gain information about the input data (semi-honest workers). The system is initialized by sharing a (randomized) function of each input matrix to each server. Since the input matrices are massive, each share's size is assumed to be at most $1/k$ fraction of the input matrix, for some $k \in \mathbb{N}$. The objective is to minimize the number of workers needed to perform the computation task correctly, such that even if an arbitrary subset of $t-1$ workers, for some $t \in \mathbb{N}$, collude, they cannot gain any information about the input matrices. We propose a sharing scheme, called \emph{polynomial sharing}, and show that it admits basic operations such as adding and multiplication of matrices and transposing a matrix. By concatenating the procedures for basic operations, we show that any polynomial function of the input matrices can be calculated, subject to the problem constraints. We show that the proposed scheme can offer order-wise gain in terms of the number of workers needed, compared to the approaches formed by the concatenation of job splitting and conventional MPC approaches.

Figures

Figures reproduced from arXiv: 1908.04255 by the authors.

**Figure 1.** An MPC system including Γ = 3 private inputs X[1] , X[2], and X[3] ∈ F m×m, for m ∈ N, N = 9 workers, and a master. All communication links are secure and error free. The size of the shares given to each worker is a fraction of the size of the inputs. Input node γ sends X˜ γn ∈ F m× m k to worker n, for some k ∈ N, k|m. Workers process their inputs while interacting with each other. Finally worker n sends On to the … view at source ↗

**Figure 2.** The circuit representing the order of operations in calculating the function [PITH_FULL_IMAGE:figures/full_fig_p034_2.png] view at source ↗

**Figure 3.** The circuit representing the order of operations in calculating the function [PITH_FULL_IMAGE:figures/full_fig_p034_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: The circuit representing the order of computation for function [PITH_FULL_IMAGE:figures/full_fig_p035_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Private and Secure Distributed Matrix Multiplication with Flexible Communication Load
cs.IT 2019-09 conditional novelty 6.0 of 10

Secure generalized PolyDot codes give a flexible recovery-threshold and communication-load trade-off for private and secure distributed matrix multiplication.

Reference graph

Works this paper leans on

52 extracted references · 48 canonical work pages · cited by 1 Pith paper

[1]

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 Proceedings of IEEE International Symposium on Information Theory (ISIT) , pp. 1231–1235, 2018

work page 2018
[2]

The round complexity of secure protocols,

D. Beaver, S. Micali, and P. Rogaway, “The round complexity of secure protocols,” in In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing , pp. 503–513, 1990

work page 1990
[3]

Simpliﬁed vss and fast-track multiparty computations with applications to threshold cryptography,

R. Gennaro, M. O. Rabin, and T. Rabin, “Simpliﬁed vss and fast-track multiparty computations with applications to threshold cryptography,” in In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing , pp. 101–111, 1998

work page 1998
[4]

Completeness theorems for non-cryptographic fault-tolerant distributed computation,

M. Ben-Or, S. Goldwasser, and A. Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” in Proceedings of the twentieth annual ACM symposium on Theory of computing , pp. 1–10, 1988

work page 1988
[5]

Multiparty unconditionally secure protocols,

D. Chaum, C. Cr ´epeau, and I. Damg ˚ard, “Multiparty unconditionally secure protocols,” in In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC) , pp. 11–19, 1988

work page 1988
[6]

Efﬁcient multiparty protocols using circuit randomization,

D. Beaver, “Efﬁcient multiparty protocols using circuit randomization,” in Annual International Cryptology Conference , pp. 420–432, Springer, 1991. 24

work page 1991
[7]

A pragmatic introduction to secure multi-party computation,

D. Evans, V . Kolesnikov, and M. Rosulek, “A pragmatic introduction to secure multi-party computation,” Foundations and Trends in Privacy and Security , vol. 2, no. 2-3, pp. 70–246, 2018

work page 2018
[8]

How to share a secret,

A. Shamir, “How to share a secret,” Communications of the ACM , vol. 22, no. 11, pp. 612–613, 1979

1979

Show all 52 references

[9]

Recent results in scalable multi-party computation,

J. Saia and M. Zamani, “Recent results in scalable multi-party computation,” in Proceedings of International Conference on Current Trends in Theory and Practice of Informatics , pp. 24–44, 2015

2015
[10]

The tail at scale,

J. Dean and L. A. Barroso, “The tail at scale,” Communications of the ACM , vol. 56, no. 2, pp. 74–80, 2013

2013
[11]

Speeding up distributed machine learning using codes,

K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding up distributed machine learning using codes,” IEEE Transactions on Information Theory , vol. 64, no. 3, pp. 1514–1529, 2018

2018
[12]

High-dimensional coded matrix multiplication,

K. Lee, C. Suh, and K. Ramchandran, “High-dimensional coded matrix multiplication,” in Proceedings of IEEE International Symposium on Information Theory (ISIT) , pp. 2418–2422, 2017

2017
[13]

Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,

Q. Yu, M. Maddah-Ali, and S. Avestimehr, “Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,” in Advances in Neural Information Processing Systems , pp. 4403–4413, 2017

2017
[14]

Straggler mitigation in distributed matrix multiplication: Fundamental limits and optimal coding,

Q. Yu, M. Maddah-Ali, and A. Avestimehr, “Straggler mitigation in distributed matrix multiplication: Fundamental limits and optimal coding,” in Proceedings of IEEE International Symposium on Information Theory , pp. 2022–2026, 2018

2022
[15]

On the optimal recovery threshold of coded matrix multiplication,

M. Fahim, H. Jeong, F. Haddadpour, S. Dutta, V . Cadambe, and P. Grover, “On the optimal recovery threshold of coded matrix multiplication,” in Proceedings of 55th Annual Allerton Conference on Communication, Control, and Computing , pp. 1264–1270, 2018

2018
[16]

Short-dot: Computing large linear transforms distributedly using coded short dot products,

S. Dutta, V . Cadambe, and P. Grover, “Short-dot: Computing large linear transforms distributedly using coded short dot products,” in Advances In Neural Information Processing Systems , pp. 2092–2100, 2016

2016
[17]

Oversketch: Approximate matrix multiplication for the cloud,

V . Gupta, S. Wang, T. Courtade, and K. Ramchandran, “Oversketch: Approximate matrix multiplication for the cloud,” pp. 298–304, 2018

2018
[18]

Coded sparse matrix multiplication,

S. Wang, J. Liu, and N. Shroff, “Coded sparse matrix multiplication,” in Proceedings of 35th International Conference on Machine Learning (ICML), vol. 12, pp. 8176–8193, 2018

2018
[19]

Lagrange coded computing: Optimal design for resiliency, security, and privacy,

Q. Yu, S. Li, N. Raviv, S. M. M. Kalan, M. Soltanolkotabi, and S. A. Avestimehr, “Lagrange coded computing: Optimal design for resiliency, security, and privacy,” pp. 1215–1225, 2019

2019
[20]

Codedsketch: A coding scheme for distributed computation of approximated matrix multiplication,

T. Jahani-Nezhad and M. A. Maddah-Ali, “Codedsketch: A coding scheme for distributed computation of approximated matrix multiplication,” arXiv preprint arXiv:1812.10460 , 2018

2018 arXiv
[21]

Accessible privacy-preserving web-based data analysis for assessing and addressing economic inequalities,

A. Lapets, F. Jansen, K. D. Albab, R. Issa, L. Qin, M. Varia, and A. Bestavros, “Accessible privacy-preserving web-based data analysis for assessing and addressing economic inequalities,” in Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies, C...

2018
[22]

Bishop, Pattern Recognition and Machine Learning

C. Bishop, Pattern Recognition and Machine Learning . Springer-Verlag New York, 2006

2006
[23]

Entangled polynomial coding in limited-sharing multi-party computation,

H. A. Nodehi, S. R. H. Najarkolaei, and M. A. Maddah-Ali, “Entangled polynomial coding in limited-sharing multi-party computation,” in Proceedings of IEEE Information Theory Workshop , 2018

2018
[24]

Coding for private and secure multiparty computing,

Q. Yu, N. Raviv, and A. S. Avestimehr, “Coding for private and secure multiparty computing,” in 2018 IEEE Information Theory Workshop (ITW), pp. 1–5, IEEE, 2018

2018
[25]

Codedprivateml: A fast and privacy-preserving framework for distributed machine learning,

J. So, B. Guler, A. S. Avestimehr, and P. Mohassel, “Codedprivateml: A fast and privacy-preserving framework for distributed machine learning,” arXiv preprint arXiv:1902.00641 , 2019

1902 arXiv
[26]

On the capacity of secure distributed matrix multiplication,

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

2018
[27]

On the capacity and straggler-robustness of distributed secure matrix multiplication,

J. Kakar, S. Ebadifar, and A. Sezgin, “On the capacity and straggler-robustness of distributed secure matrix multiplication,” IEEE Access, vol. 7, pp. 45783–45799, 2019

2019
[28]

Gasp codes for secure distributed matrix multiplication,

R. G. DOliveira, S. El Rouayheb, and D. Karpuk, “Gasp codes for secure distributed matrix multiplication,” IEEE Transactions on Information Theory, 2020

2020
[29]

On the capacity of secure distributed matrix multiplication,

Z. Jia and S. A. Jafar, “On the capacity of secure distributed matrix multiplication,” arXiv preprint arXiv:1908.06957 , 2019

1908 arXiv
[30]

Private secure coded computation,

M. Kim and J. Lee, “Private secure coded computation,” in 2019 IEEE International Symposium on Information Theory (ISIT) , pp. 1097–1101, IEEE, 2019

2019
[31]

Private and secure distributed matrix multiplication with ﬂexible communication load,

M. Aliasgari, O. Simeone, and J. Kliewer, “Private and secure distributed matrix multiplication with ﬂexible communication load,” IEEE Transactions on Information Forensics and Security , vol. 15, pp. 2722–2734, 2020

2020
[32]

Private sequential function computation,

B. Tahmasebi and M. A. Maddah-Ali, “Private sequential function computation,” in 2019 IEEE International Symposium on Information Theory (ISIT), pp. 1667–1671, 2019

2019
[33]

Private function computation,

B. Tahmasebi and M. A. Maddah-Ali, “Private function computation,” in 2020 IEEE International Symposium on Information Theory (ISIT), pp. 1118–1123, 2020

2020
[34]

Numerical methods: analysis, algebra, ordinary differential equations,

N. S. Bakhvalov, “Numerical methods: analysis, algebra, ordinary differential equations,” 1977

1977
[35]

Fast polynomial factorization and modular composition,

K. S. Kedlaya and C. Umans, “Fast polynomial factorization and modular composition,” SIAM Journal on Computing , vol. 40, no. 6, pp. 1767–1802, 2011

2011
[36]

Horner’s method — Wikipedia, the free encyclopedia,

Wikipedia contributors, “Horner’s method — Wikipedia, the free encyclopedia,” 2020. [Online; accessed 5-June-2020]

2020
[37]

Practical covertly secure mpc for dishonest majority–or: breaking the spdz limits,

I. Damg ˚ard, M. Keller, E. Larraia, V . Pastro, P. Scholl, and N. P. Smart, “Practical covertly secure mpc for dishonest majority–or: breaking the spdz limits,” in European Symposium on Research in Computer Security , pp. 1–18, Springer, 2013

2013
[38]

A note on the communication complexity of multiparty computation in the correlated randomness model,

G. Couteau, “A note on the communication complexity of multiparty computation in the correlated randomness model,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques , pp. 473–503, Springer, 2019

2019
[39]

On the (in) efﬁciency of non-interactive secure multiparty computation,

M. Yoshida and S. Obana, “On the (in) efﬁciency of non-interactive secure multiparty computation,” Designs, Codes and Cryptography, vol. 86, no. 8, pp. 1793–1805, 2018

2018
[40]

An efﬁcient framework for unconditionally secure multiparty computation,

A. Choudhury and A. Patra, “An efﬁcient framework for unconditionally secure multiparty computation,” IEEE Transactions on Information Theory, vol. 63, no. 1, pp. 428–468, 2016. 25

2016
[41]

Secure coded multi-party computation for massive matrices with adversarial nodes,

M. A. M.-A. Seyed Reza Hoseini and M. R. Aref, “Secure coded multi-party computation for massive matrices with adversarial nodes,” in International Conference on Machine Learning (ICML) , 2019

2019
[42]

Generalized vandermonde determinants and applications,

G. Sobczyk, “Generalized vandermonde determinants and applications,” Aportaciones Matematicas, Serie Comunicaciones , vol. 30, pp. 203–213, 2002

2002
[43]

On the computation of the determinant of a generalized vandermonde matrix,

T. Kitamoto, “On the computation of the determinant of a generalized vandermonde matrix,” pp. 242–255, 2014

2014
[44]

Schur polynomial — Wikipedia, the free encyclopedia,

Wikipedia contributors, “Schur polynomial — Wikipedia, the free encyclopedia,” 2020. [Online; accessed 29-May-2020]

2020
[45]

An algebraic approach to network coding,

R. Koetter and M. M ´edard, “An algebraic approach to network coding,” IEEE/ACM Transactions on Networking (TON) , vol. 11, no. 5, pp. 782–795, 2003

2003
[46]

Fast probabilistic algorithms for veriﬁcation of polynomial identities,

J. T. Schwartz, “Fast probabilistic algorithms for veriﬁcation of polynomial identities,” Journal of the ACM (JACM) , vol. 27, no. 4, pp. 701–717, 1980

1980
[47]

Probabilistic algorithms for sparse polynomials,

R. Zippel, “Probabilistic algorithms for sparse polynomials,” in Symbolic and algebraic computation , pp. 216–226, Springer, 1979. 26 APPENDIX A PROOF OF THEOREM 2 In order to prove Theorem 2, we ﬁrst prove the following lemma. Lemma 4. Let A, B∈ Fm×m, and A = [A1, A2, ..., Ak...

1979
[48]

Therefore, in this case non of the coefﬁcients of H(x), is equal to zero

Case 1, k− 1≤t− 2: In this case one can see that we have (S1∪S 2∪S 3∪S 4) = [0, 2k2 + 2t− 4]. Therefore, in this case non of the coefﬁcients of H(x), is equal to zero. Thus, the number of nonzero coefﬁcients of H(x) is 2k2 + 2t− 3. 27
[49]

In this case we claim that the number of zero coefﬁcients of H(x) is (k−t + 1)(k− 1), thus the number of nonzero coefﬁcients is (2k2 + 2t− 3)− (k−t + 1)(k− 1) =k2 +kt +t− 2

Case 2, k−1>t−2: In this case, counting the number of non-zero coefﬁcients is more complicated, specially because the intersection S2∩S 3 is not zero. In this case we claim that the number of zero coefﬁcients of H(x) is (k−t + 1)(k− 1), thus the number of nonzero coefﬁcients i...
[50]

In order to represent this function, ﬁrst we multiply the last two matrices ( X[Γ−1], X[Γ]), then we multiply X[Γ−2] to the result of the previous operation and so on

Rule 1: Assume that the function is in the form of ∏Γ j=1 X[j]. In order to represent this function, ﬁrst we multiply the last two matrices ( X[Γ−1], X[Γ]), then we multiply X[Γ−2] to the result of the previous operation and so on. The order of computation is shown in Fig. 2. ...
[51]

In order to represent this function, ﬁrst we add the last two matrices ( X[Γ−1] + X[Γ]), then we add X[Γ−2] to the result of the previous operation, and so on

Rule 2: Assume that the function is in the form of ∑Γ j=1 X[j]. In order to represent this function, ﬁrst we add the last two matrices ( X[Γ−1] + X[Γ]), then we add X[Γ−2] to the result of the previous operation, and so on. The order of computation is shown in Fig. 3. Fig. 3. ...
[52]

The representation and order of computation are shown for an example in Fig.4

Rule 3: To represent a general function (67), and assign a speciﬁc order to the computations, we ﬁrst compute GM based on Rule 1, keep the result, and compute GM−1 based on Rule 1, and add up the result based on rule 2, and then compute GM−2 based on Rule 1, and so on. The rep...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

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 Proceedings of IEEE International Symposium on Information Theory (ISIT) , pp. 1231–1235, 2018

work page 2018

[2] [2]

The round complexity of secure protocols,

D. Beaver, S. Micali, and P. Rogaway, “The round complexity of secure protocols,” in In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing , pp. 503–513, 1990

work page 1990

[3] [3]

Simpliﬁed vss and fast-track multiparty computations with applications to threshold cryptography,

R. Gennaro, M. O. Rabin, and T. Rabin, “Simpliﬁed vss and fast-track multiparty computations with applications to threshold cryptography,” in In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing , pp. 101–111, 1998

work page 1998

[4] [4]

Completeness theorems for non-cryptographic fault-tolerant distributed computation,

M. Ben-Or, S. Goldwasser, and A. Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” in Proceedings of the twentieth annual ACM symposium on Theory of computing , pp. 1–10, 1988

work page 1988

[5] [5]

Multiparty unconditionally secure protocols,

D. Chaum, C. Cr ´epeau, and I. Damg ˚ard, “Multiparty unconditionally secure protocols,” in In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC) , pp. 11–19, 1988

work page 1988

[6] [6]

Efﬁcient multiparty protocols using circuit randomization,

D. Beaver, “Efﬁcient multiparty protocols using circuit randomization,” in Annual International Cryptology Conference , pp. 420–432, Springer, 1991. 24

work page 1991

[7] [7]

A pragmatic introduction to secure multi-party computation,

D. Evans, V . Kolesnikov, and M. Rosulek, “A pragmatic introduction to secure multi-party computation,” Foundations and Trends in Privacy and Security , vol. 2, no. 2-3, pp. 70–246, 2018

work page 2018

[8] [8]

How to share a secret,

A. Shamir, “How to share a secret,” Communications of the ACM , vol. 22, no. 11, pp. 612–613, 1979

1979