{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T23:34:51Z","timestamp":1778024091509,"version":"3.51.4"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T00:00:00Z","timestamp":1602720000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T00:00:00Z","timestamp":1602720000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Big Data"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>With the advent of cloud-based parallel processing techniques, services such as MapReduce have been considered by many businesses and researchers for different applications of big data computation including matrix multiplication, which has drawn much attention in recent years. However, securing the computation result integrity in such systems is an important challenge, since public clouds can be vulnerable against the misbehavior of their owners (especially for economic purposes) and external attackers. In this paper, we propose an efficient approach using Merkle tree structure to verify the computation results of matrix multiplication in MapReduce systems while enduring an acceptable overhead, which makes it suitable in terms of scalability. Using the Merkle tree structure, we record fine-grained computation results in the tree nodes to make strong commitments for workers; they submit a commitment value to the verifier which is then used to challenge their computation results\u2019 integrity using elected input data as verification samples. Evaluation outcomes show significant improvements comparing with the state-of-the-art technique; in case of 300*300 matrices, 73% reduction in generated proof size, 61% reduction in the proof construction time, and 95% reduction in the verification time.<\/jats:p>","DOI":"10.1186\/s40537-020-00362-1","type":"journal-article","created":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T20:02:46Z","timestamp":1602792166000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient verification of parallel matrix multiplication in public cloud: the MapReduce case"],"prefix":"10.1186","volume":"7","author":[{"given":"Ramtin","family":"Bagheri","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7269-779X","authenticated-orcid":false,"given":"Morteza","family":"Amini","sequence":"additional","affiliation":[]},{"given":"Somayeh","family":"Dolatnezhad Samarin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,10,15]]},"reference":[{"key":"362_CR1","unstructured":"IDC, Digital Universe: The Speed of Data Creation is Rapidly Accelerating. 2014. https:\/\/www.emc.com\/collateral\/analyst-reports\/idc-digital-universe-2014.pdf."},{"issue":"1","key":"362_CR2","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean J, Ghemawat S. Mapreduce. Commun ACM. 2008;51(1):107. https:\/\/doi.org\/10.1145\/1327452.1327492. arXiv:10.1.1.135.4448.","journal-title":"Commun ACM"},{"key":"362_CR3","doi-asserted-by":"crossref","unstructured":"Russkov A, Shchur L. Matrix multiplication and universal scalability of the time on the intel scalable processors, In: Journal of Physics: Conference Series, Vol. 1163, IOP Publishing, 2019;0 12079.","DOI":"10.1088\/1742-6596\/1163\/1\/012079"},{"key":"362_CR4","doi-asserted-by":"crossref","unstructured":"Vasudevan A, Anderson A, Gregg D. Parallel multi channel convolution using general matrix multiplication, In: 2017 IEEE 28th International Conference on Application-specific Systems, Architectures and Processors (ASAP), IEEE, 2017;19\u201324.","DOI":"10.1109\/ASAP.2017.7995254"},{"issue":"5","key":"362_CR5","first-page":"109","volume":"7","author":"MM AL-Laham","year":"2015","unstructured":"AL-Laham MM. Encryption-decryption rgb color image using matrix multiplication. Int J Comput Sci Inform Technol. 2015;7(5):109\u201319.","journal-title":"Int J Comput Sci Inform Technol"},{"key":"362_CR6","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1016\/j.procs.2012.09.058","volume":"12","author":"F Highland","year":"2012","unstructured":"Highland F, Stephenson J. Fitting the problem to the paradigm: algorithm characteristics required for effective use of mapreduce. Procedia Comput Sci. 2012;12:212\u20137.","journal-title":"Procedia Comput Sci"},{"key":"362_CR7","doi-asserted-by":"publisher","unstructured":"Ballard G, Demmel J, Holtz O, Lipshitz B, Schwartz O. Communication-optimal parallel algorithm for strassen\u2019s matrix multiplication, In: Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and architectures - SPAA \u201912, ACM Press, 2012. https:\/\/doi.org\/10.1145\/2312005.2312044.","DOI":"10.1145\/2312005.2312044"},{"issue":"7","key":"362_CR8","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1002\/cpe.4330060702","volume":"6","author":"J Choi","year":"1994","unstructured":"Choi J, Walker DW, Dongarra JJ. Pumma: parallel universal matrix multiplication algorithms on distributed memory concurrent computers. Concurrency Pract Exp. 1994;6(7):543\u201370. https:\/\/doi.org\/10.1002\/cpe.4330060702.","journal-title":"Concurrency Pract Exp"},{"issue":"1","key":"362_CR9","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0167-8191(87)90060-3","volume":"4","author":"GC Fox","year":"1987","unstructured":"Fox GC, Otto SW, Hey AJ. Matrix algorithms on a hypercube I: matrix multiplication. Parallel Comput. 1987;4(1):17\u201331.","journal-title":"Parallel Comput"},{"issue":"2","key":"362_CR10","doi-asserted-by":"publisher","first-page":"1242","DOI":"10.1109\/ICDMW.2010.155","volume":"33199","author":"Z Sun","year":"2010","unstructured":"Sun Z, Li T, Rishe N. Large-scale matrix factorization using MapReduce. Proceed IEEE Int Conf Data Min ICDM. 2010;33199(2):1242\u20138. https:\/\/doi.org\/10.1109\/ICDMW.2010.155.","journal-title":"Proceed IEEE Int Conf Data Min ICDM"},{"key":"362_CR11","first-page":"11","volume":"26","author":"J Zheng","year":"2013","unstructured":"Zheng J, Zhu R, Shen Y. Sparse matrix multiplication algorithm based on mapreduce. J Zhongkai Univ Agri Engineer. 2013;26:11.","journal-title":"J Zhongkai Univ Agri Engineer"},{"issue":"1","key":"362_CR12","first-page":"93","volume":"13","author":"S Deng","year":"2016","unstructured":"Deng S, Wenhua W. Efficient matrix multiplication in hadoop. Int J Comput Sci Appl. 2016;13(1):93\u2013104.","journal-title":"Int J Comput Sci Appl"},{"key":"362_CR13","doi-asserted-by":"crossref","unstructured":"Kadhum M, Qasem M H, Sleit A, Sharieh A. Efficient MapReduce Matrix Multiplication with Optimized Mapper Set, In: R. Silhavy, R. Senkerik, Z. Kominkova Oplatkova, Z. Prokopova, P. Silhavy (Eds.), Cybernetics and Mathematics Applications in Intelligent Systems, Vol. 574, Springer International Publishing, 2017;186\u2013196.","DOI":"10.1007\/978-3-319-57264-2_19"},{"key":"362_CR14","doi-asserted-by":"publisher","unstructured":"Merkle R C. A Digital Signature Based on a Conventional Encryption Function, In: C. Pomerance (Ed.), Advances in Cryptology \u2014 CRYPTO \u201987, Vol. 293, Springer Berlin Heidelberg, 1988. https:\/\/doi.org\/10.1007\/3-540-48184-2_32.","DOI":"10.1007\/3-540-48184-2_32"},{"key":"362_CR15","doi-asserted-by":"crossref","unstructured":"Du W, Jia J, Mangal Manish, Murugesan Mummoorthy, Uncheatable grid computing, In: 24th International Conference on Distributed Computing Systems, 2004. Proceedings., IEEE, 2004;4\u201311.","DOI":"10.1109\/ICDCS.2004.1281562"},{"key":"362_CR16","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1109\/CCGrid.2015.16","volume":"2015","author":"C Liao","year":"2015","unstructured":"Liao C, Squicciarini A. Towards provenance-based anomaly detection in MapReduce, Proceedings - 2015 IEEE\/ACM 15th International Symposium on Cluster. Cloud Grid Comput CCGrid. 2015;2015:647\u201356. https:\/\/doi.org\/10.1109\/CCGrid.2015.16.","journal-title":"Cloud Grid Comput CCGrid"},{"key":"362_CR17","doi-asserted-by":"publisher","unstructured":"Yoon E, Squicciarini A. Toward Detecting Compromised MapReduce Workers through Log Analysis, In: Proceedings of the IEEE\/ACM 14th International Symposium on Cluster, Cloud and Grid Computing, IEEE, 2014;41\u201350. https:\/\/doi.org\/10.1109\/CCGrid.2014.120.","DOI":"10.1109\/CCGrid.2014.120"},{"key":"362_CR18","doi-asserted-by":"crossref","unstructured":"Wagner D, Soto P. Mimicry attacks on host-based intrusion detection systems, In: Proceedings of the 9th ACM Conference on Computer and Communications Security, ACM, 2002;255\u2013264.","DOI":"10.1145\/586110.586145"},{"key":"362_CR19","doi-asserted-by":"publisher","unstructured":"Ruan A, Martin A. TMR: Towards a Trusted MapReduce Infrastructure, In: Proceedings of the IEEE 8th World Congress on Services, IEEE. 2012;141\u2013148. https:\/\/doi.org\/10.1109\/SERVICES.2012.28.","DOI":"10.1109\/SERVICES.2012.28"},{"key":"362_CR20","doi-asserted-by":"publisher","unstructured":"Bissiriou C A A, Zbakh M. Towards Secure Tag-MapReduce Framework in Cloud, In: Proceedings of the IEEE 2nd International Conference on Big Data Security on Cloud, IEEE. 2016;96\u2013104. https:\/\/doi.org\/10.1109\/BigDataSecurity-HPSC-IDS.2016.78.","DOI":"10.1109\/BigDataSecurity-HPSC-IDS.2016.78"},{"key":"362_CR21","doi-asserted-by":"publisher","unstructured":"Zhang C, Chang E C, Yap R H C. Tagged-mapreduce: A general framework for secure computing with mixed-sensitivity data on hybrid clouds, In: Proceeding of the IEEE\/ACM 14th International Symposium on Cluster, Cloud and Grid Computing, 2014;31\u201340. https:\/\/doi.org\/10.1109\/CCGrid.2014.96.","DOI":"10.1109\/CCGrid.2014.96"},{"key":"362_CR22","doi-asserted-by":"publisher","unstructured":"Ding Y, Wang H, Chen S, Tang X, Fu H, Shi P. PIIM: Method of Identifying Malicious Workers in the MapReduce System with an Open Environment, In: Proceedings of the IEEE 8th International Symposium on Service Oriented System Engineering, IEEE, 2014;326\u2013331. https:\/\/doi.org\/10.1109\/SOSE.2014.47.","DOI":"10.1109\/SOSE.2014.47"},{"key":"362_CR23","doi-asserted-by":"publisher","unstructured":"Huang C, Zhu S, Wu D. Towards Trusted Services: Result Verification Schemes for MapReduce, In: Proceedings of the IEEE\/ACM 12th International Symposium on Cluster, Cloud and Grid Computing, IEEE, 2012;41\u201348. https:\/\/doi.org\/10.1109\/CCGrid.2012.77.","DOI":"10.1109\/CCGrid.2012.77"},{"key":"362_CR24","doi-asserted-by":"publisher","unstructured":"Kamvar S D, Schlosser M T, Garcia-Molina H. The Eigentrust algorithm for reputation management in P2P networks, In: Proceedings of the ACM 12th international conference on World Wide Web, ACM Press, New York, 2003;640. https:\/\/doi.org\/10.1145\/775240.775242.","DOI":"10.1145\/775240.775242"},{"key":"362_CR25","doi-asserted-by":"publisher","unstructured":"Wei W, Du J, Yu T, Gu X. SecureMR: A Service Integrity Assurance Framework for MapReduce, In: Proceedings of the IEEE Annual Computer Security Applications Conference, IEEE, 2009;73\u201382. https:\/\/doi.org\/10.1109\/ACSAC.2009.17.","DOI":"10.1109\/ACSAC.2009.17"},{"key":"362_CR26","doi-asserted-by":"publisher","DOI":"10.1587\/transinf.E97.D.721","author":"Y Ding","year":"2014","unstructured":"Ding Y, Wang H, Wei L, Chen S, Fu H, Xu X. VAWS: constructing trusted open computing system of mapReduce with verified participants E97.D. IEICE Transact Informat Syst. 2014;. https:\/\/doi.org\/10.1587\/transinf.E97.D.721.","journal-title":"IEICE Transact Informat Syst"},{"key":"362_CR27","doi-asserted-by":"publisher","unstructured":"Bendahmane A, Essaaidi M, Moussaoui A E, Younes A. Result verification mechanism for MapReduce computation integrity in cloud computing, In: Proceedings of the IEEE International Conference on Complex Systems (ICCS), IEEE, 2012;1\u20136. https:\/\/doi.org\/10.1109\/ICoCS.2012.6458583.","DOI":"10.1109\/ICoCS.2012.6458583"},{"key":"362_CR28","doi-asserted-by":"publisher","unstructured":"Khan S M, Hamlen K W. Hatman: Intra-cloud Trust Management for Hadoop, in: Preceedings of the IEEE 5th International Conference on Cloud Computing, IEEE, 2012;494\u2013501. https:\/\/doi.org\/10.1109\/CLOUD.2012.64.","DOI":"10.1109\/CLOUD.2012.64"},{"key":"362_CR29","doi-asserted-by":"publisher","unstructured":"Samuel T A, Abdul Nizar M. Credibility-based result verification for Map-reduce, In: Proceedings of the IEEE Annual India Conference (INDICON), IEEE, 2014;1\u20136. https:\/\/doi.org\/10.1109\/INDICON.2014.7030682.","DOI":"10.1109\/INDICON.2014.7030682"},{"key":"362_CR30","doi-asserted-by":"publisher","unstructured":"Wang Y, Wei J. VIAF: Verification-Based Integrity Assurance Framework for MapReduce, In: Proceedings of the IEEE 4th International Conference on Cloud Computing, IEEE, 2011;300\u2013307. https:\/\/doi.org\/10.1109\/CLOUD.2011.33.","DOI":"10.1109\/CLOUD.2011.33"},{"key":"362_CR31","doi-asserted-by":"publisher","unstructured":"Wang Y, Wei J, Srivatsa M. Result Integrity Check for MapReduce Computation on Hybrid Clouds, In: Proceedings of the IEEE 6th International Conference on Cloud Computing, IEEE, 2013;847\u2013854. https:\/\/doi.org\/10.1109\/CLOUD.2013.118.","DOI":"10.1109\/CLOUD.2013.118"},{"issue":"1","key":"362_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.future.2013.07.001","volume":"30","author":"Z Xiao","year":"2014","unstructured":"Xiao Z, Xiao Y. Achieving accountable MapReduce in cloud computing. Futur Generat Comput Syst. 2014;30(1):1\u201313. https:\/\/doi.org\/10.1016\/j.future.2013.07.001.","journal-title":"Futur Generat Comput Syst"},{"issue":"8","key":"362_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TBDATA.2016.2599928","volume":"14","author":"Y Wang","year":"2016","unstructured":"Wang Y, Shen Y, Wang H, Cao J, Jiang X. MtMR: ensuring MapReduce computation integrity with Merkle tree-based verifications. IEEE Transact Big Data. 2016;14(8):1. https:\/\/doi.org\/10.1109\/TBDATA.2016.2599928.","journal-title":"IEEE Transact Big Data"},{"key":"362_CR34","doi-asserted-by":"crossref","unstructured":"Freivalds R. Fast probabilistic algorithms, In: International Symposium on Mathematical Foundations of Computer Science, Springer, 1979;57\u201369.","DOI":"10.1007\/3-540-09526-8_5"},{"key":"362_CR35","doi-asserted-by":"crossref","unstructured":"Thaler J. Time-optimal interactive proofs for circuit evaluation, In: Annual Cryptology Conference, Springer, 2013;71\u201389.","DOI":"10.1007\/978-3-642-40084-1_5"},{"key":"362_CR36","volume-title":"Engineering Vibration, Communication and Information Processing","author":"M Kumar","year":"2019","unstructured":"Kumar M, Vardhan M. Engineering Vibration, Communication and Information Processing, vol. 478. Singapore: Springer; 2019 10.1007\/978-981-13-1642-5."},{"issue":"6","key":"362_CR37","doi-asserted-by":"publisher","first-page":"5076","DOI":"10.1109\/JIOT.2018.2867113","volume":"5","author":"S Zhang","year":"2018","unstructured":"Zhang S, Li H, Dai Y, Li J, He M, Lu R. Verifiable outsourcing computation for matrix multiplication with improved efficiency and applicability. IEEE Int Things J. 2018;5(6):5076\u201388. https:\/\/doi.org\/10.1109\/JIOT.2018.2867113.","journal-title":"IEEE Int Things J"},{"key":"362_CR38","doi-asserted-by":"publisher","unstructured":"Bultel X, Ciucanu R, Giraud M, Lafourcade P. Secure Matrix Multiplication with MapReduce, In: Proceedings of the 12th International Conference on Availability, Reliability and Security - ARES \u201917, ACM Press, New York, New York, USA, 2017;1\u201310. https:\/\/doi.org\/10.1145\/3098954.3098989.","DOI":"10.1145\/3098954.3098989"},{"key":"362_CR39","doi-asserted-by":"publisher","unstructured":"Zhang S, Li H, Jia K, Dai Y, Zhao L. Efficient secure outsourcing computation of matrix multiplication in cloud computing, 2016 IEEE Global Communications Conference, GLOBECOM 2016 - Proceedings https:\/\/doi.org\/10.1109\/GLOCOM.2016.7841783.","DOI":"10.1109\/GLOCOM.2016.7841783"},{"key":"362_CR40","doi-asserted-by":"crossref","unstructured":"Bowers K D, Juels A, Oprea A. Hail: A high-availability and integrity layer for cloud storage, In: Proceedings of the 16th ACM conference on Computer and communications security, ACM, 2009;187\u2013198.","DOI":"10.1145\/1653662.1653686"}],"container-title":["Journal of Big Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s40537-020-00362-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s40537-020-00362-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s40537-020-00362-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:02:51Z","timestamp":1634256171000},"score":1,"resource":{"primary":{"URL":"https:\/\/journalofbigdata.springeropen.com\/articles\/10.1186\/s40537-020-00362-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,15]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["362"],"URL":"https:\/\/doi.org\/10.1186\/s40537-020-00362-1","relation":{},"ISSN":["2196-1115"],"issn-type":[{"value":"2196-1115","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,15]]},"assertion":[{"value":"23 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"86"}}