{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:29:33Z","timestamp":1761294573458,"version":"build-2065373602"},"reference-count":32,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T00:00:00Z","timestamp":1675123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"UCD Seed Funding-Horizon Scanning scheme","award":["54584","1815322","1908756","2107370"],"award-info":[{"award-number":["54584","1815322","1908756","2107370"]}]},{"name":"U.S. National Science Foundation","award":["54584","1815322","1908756","2107370"],"award-info":[{"award-number":["54584","1815322","1908756","2107370"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Large matrix multiplications commonly take place in large-scale machine-learning applications. Often, the sheer size of these matrices prevent carrying out the multiplication at a single server. Therefore, these operations are typically offloaded to a distributed computing platform with a master server and a large amount of workers in the cloud, operating in parallel. For such distributed platforms, it has been recently shown that coding over the input data matrices can reduce the computational delay by introducing a tolerance against straggling workers, i.e., workers for which execution time significantly lags with respect to the average. In addition to exact recovery, we impose a security constraint on both matrices to be multiplied. Specifically, we assume that workers can collude and eavesdrop on the content of these matrices. For this problem, we introduce a new class of polynomial codes with fewer non-zero coefficients than the degree +1. We provide closed-form expressions for the recovery threshold and show that our construction improves the recovery threshold of existing schemes in the literature, in particular for larger matrix dimensions and a moderate to large number of colluding workers. In the absence of any security constraints, we show that our construction is optimal in terms of recovery threshold.<\/jats:p>","DOI":"10.3390\/e25020266","type":"journal-article","created":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T02:29:03Z","timestamp":1675218543000},"page":"266","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Straggler- and Adversary-Tolerant Secure Distributed Matrix Multiplication Using Polynomial Codes"],"prefix":"10.3390","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1857-0365","authenticated-orcid":false,"given":"Eimear","family":"Byrne","sequence":"first","affiliation":[{"name":"School of Mathematics and Statistics, University College Dublin, D04 V1W8 Dublin, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1614-7464","authenticated-orcid":false,"given":"Oliver W.","family":"Gnilke","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Aalborg University, 9220 Aalborg, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0942-8006","authenticated-orcid":false,"given":"J\u00f6rg","family":"Kliewer","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ 07410, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,1,31]]},"reference":[{"key":"ref_1","unstructured":"Janzamin, M., Sedghi, H., and Anandkumar, A. (2015). Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods. arXiv."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3055281","article-title":"Efficient redundancy techniques for latency reduction in cloud systems","volume":"2","author":"Joshi","year":"2017","journal-title":"ACM Trans. Model. Perform. Eval. Comput. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Lee, K., Suh, C., and Ramchandran, K. (2017, January 25\u201330). High-dimensional coded matrix multiplication. Proceedings of the IEEE International Symposium on Information Theory (ISIT), Aachen, Germany.","DOI":"10.1109\/ISIT.2017.8006963"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1514","DOI":"10.1109\/TIT.2017.2736066","article-title":"Speeding Up Distributed Machine Learning Using Codes","volume":"64","author":"Lee","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","unstructured":"Yu, Q., Maddah-Ali, M., and Avestimehr, S. (2017, January 4\u20139). Polynomial codes: An optimal design for high-dimensional coded matrix multiplication. Proceedings of the Advances in Neural Information Processing Systems, Long Beach, CA, USA."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TIT.2017.2756959","article-title":"A fundamental tradeoff between computation and communication in distributed computing","volume":"64","author":"Li","year":"2017","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Aliasgari, M., Simeone, O., and Kliewer, J. (2019). Distributed and Private Coded Matrix Computation with Flexible Communication Load. arXiv.","DOI":"10.1109\/ISIT.2019.8849606"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1109\/TIFS.2018.2846601","article-title":"Secure Distributed Computing With Straggling Servers Using Polynomial Codes","volume":"14","author":"Yang","year":"2019","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"4038","DOI":"10.1109\/TIT.2020.2975021","article-title":"GASP Codes for Secure Distributed Matrix Multiplication","volume":"66","author":"Karpuk","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1109\/JSAIT.2021.3102882","article-title":"Degree Tables for Secure Distributed Matrix Multiplication","volume":"2","author":"Heinlein","year":"2021","journal-title":"IEEE J. Sel. Areas Inf. Theory"},{"key":"ref_11","unstructured":"Yu, Q., Raviv, N., So, J., and Avestimehr, A.S. (2018). Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy. arXiv."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"45783","DOI":"10.1109\/ACCESS.2019.2908024","article-title":"On the Capacity and Straggler-Robustness of Distributed Secure Matrix Multiplication","volume":"7","author":"Kakar","year":"2019","journal-title":"IEEE Access"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Chang, W.T., and Tandon, R. (2018, January 9\u201313). On the capacity of secure distributed matrix multiplication. Proceedings of the 2018 IEEE Global Communications Conference (GLOBECOM), Abu Dhabi, United Arab Emirates.","DOI":"10.1109\/GLOCOM.2018.8647313"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Chang, W.T., and Tandon, R. (2019, January 25\u201328). On the Upload versus Download Cost for Secure and Private Matrix Multiplication. Proceedings of the 2019 IEEE Information Theory Workshop (ITW), Gotland, Sweden.","DOI":"10.1109\/ITW44776.2019.8989342"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Dutta, S., Bai, Z., Jeong, H., Low, T.M., and Grover, P. (2018, January 17\u201322). A unified coded deep neural network training strategy based on generalized PolyDot codes. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437852"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1109\/TIT.2019.2929328","article-title":"On the Optimal Recovery Threshold of Coded Matrix Multiplication","volume":"66","author":"Dutta","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2722","DOI":"10.1109\/TIFS.2020.2972166","article-title":"Private and Secure Distributed Matrix Multiplication With Flexible Communication Load","volume":"15","author":"Aliasgari","year":"2020","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1920","DOI":"10.1109\/TIT.2019.2963864","article-title":"Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding","volume":"66","author":"Yu","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Yu, Q., and Avestimehr, A.S. (2020, January 21\u201326). Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the \u201cCubic\u201d Barrier. Proceedings of the 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA.","DOI":"10.1109\/ISIT44484.2020.9174167"},{"key":"ref_20","unstructured":"Wang, H.-P., and Duursma, I. (2020). Parity-Checked Strassen Algorithm. arXiv."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"955","DOI":"10.1109\/JSAC.2022.3142355","article-title":"Bivariate Polynomial Codes for Secure Distributed Matrix Multiplication","volume":"40","author":"Hasirciolu","year":"2022","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1109\/TIFS.2022.3147638","article-title":"Private and Secure Distributed Matrix Multiplication Schemes for Replicated or MDS-Coded Servers","volume":"17","author":"Li","year":"2022","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Machado, R.A., D\u2019Oliveira, R.G.L., Rouayheb, S.E., and Heinlein, D. (2021, January 23\u201325). Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication. Proceedings of the 2021 XVII International Symposium \u201cProblems of Redundancy in Information and Control Systems\u201d (REDUNDANCY), Prague, Czech Republic.","DOI":"10.1109\/REDUNDANCY52534.2021.9606447"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Makkonen, O., and Hollanti, C. (2022). General Framework for Linear Secure Distributed Matrix Multiplication with Byzantine Servers. arXiv.","DOI":"10.1109\/ITW54588.2022.9965828"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"4666","DOI":"10.1109\/TIT.2022.3158868","article-title":"Secure Distributed Matrix Computation With Discrete Fourier Transform","volume":"68","author":"Mital","year":"2022","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Machado, R.A., and Manganiello, F. (2022). Root of Unity for Secure Distributed Matrix Multiplication: Grid Partition Case. arXiv.","DOI":"10.1109\/ITW54588.2022.9965858"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1109\/JSAIT.2022.3181144","article-title":"A Systematic Approach towards Efficient Private Matrix Multiplication","volume":"3","author":"Zhu","year":"2022","journal-title":"IEEE J. Sel. Areas Inf. Theory"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1006\/jsco.1996.0125","article-title":"The Magma algebra system. I. The user language","volume":"24","author":"Bosma","year":"1997","journal-title":"J. Symb. Comput."},{"key":"ref_29","unstructured":"Sedoglavic, A. (2022, October 28). Yet Another Catalogue of Fast Matrix Multiplication Algorithms. Available online: https:\/\/fmm.univ-lille.fr\/."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1038\/s41586-022-05172-4","article-title":"Discovering faster matrix multiplication algorithms with reinforcement learning","volume":"610","author":"Fawzi","year":"2022","journal-title":"Nature"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1109\/12.990131","article-title":"On the inherent space complexity of fast parallel multipliers for GF(2\/sup m\/)","volume":"51","author":"Elia","year":"2002","journal-title":"IEEE Trans. Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s00200-011-0160-6","article-title":"Polynomial evaluation over finite fields: New algorithms and complexity bounds","volume":"23","author":"Elia","year":"2012","journal-title":"Appl. Algebra Eng. Commun. Comput."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/2\/266\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:20:00Z","timestamp":1760120400000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/2\/266"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,31]]},"references-count":32,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,2]]}},"alternative-id":["e25020266"],"URL":"https:\/\/doi.org\/10.3390\/e25020266","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2023,1,31]]}}}