Secure outsourcing of large matrix determinant computation

Abstract

Cloud computing provides the capability to connect resource-constrained clients with a centralized and shared pool of resources, such as computational power and storage on demand. Large matrix determinant computation is almost ubiquitous in computer science and requires largescale data computation. Currently, techniques for securely outsourcing matrix determinant computations to untrusted servers are of utmost importance, and they have practical value as well as theoretical significance for the scientific community. In this study, we propose a secure outsourcing method for large matrix determinant computation. We employ some transformations for privacy protection based on the original matrix, including permutation and mix-row/mixcolumn operations, before sending the target matrix to the cloud. The results returned from the cloud need to be decrypted and verified to obtain the correct determinant. In comparison with previously proposed algorithms, our new algorithm achieves a higher security levelwith greater cloud efficiency. The experimental results demonstrate the efficiency and effectiveness of our algorithm.

Keywords

cloud computing / large-scale data computation / matrix determinant computation / secure outsourcing

References

[1] Gentry C. A fully homomorphic encryption scheme. Doctoral Dissertation, Stanford University, 2009.

[2] Parno B, Howell J, Gentry C, Raykova M. Pinocchio: nearly practical verifiable computation. In: Proceedings of 2013 IEEE Symposium on Security and Privacy. 2013, 238–252

[3] Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE. SIAM Journal on Computing, 2014, 43(2): 831–871

[4] Doröz Y, öztürk E, Sunar B. Accelerating fully homomorphic encryption in hardware. IEEE Transactions on Computers, 2015, 64(6): 1509–1521

[5] Alagic G, Dulek Y, Schaffner C, Speelman F. Quantum fully homomorphic encryption with verification. In: Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information Security. 2017, 438–467

[6] López-Alt A, Tromer E, Vaikuntanathan V. Multikey fully homomorphic encryption and applications. SIAM Journal on Computing, 2017, 46(6): 1827–1892

[7] Boneh D, Gennaro R, Goldfeder S, Jain A, Kim S, Rasmussen P M R, Sahai A. Threshold cryptosystems from threshold fully homomorphic encryption. In: Proceedings of the 38th Annual International Cryptology Conference. 2018, 565–596

[8] Goyal V, Pandey O, Sahai A, Waters B. Attribute-based encryption for fine-grained access control of encrypted data. In: Proceedings of the 13th ACM Conference on Computer and Communications Security. 2006, 89–98

[9] Waters B. Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization. In: Proceedings of the 14th International Conference on Practice and Theory in Public Key Cryptography. 2011, 53–70

[10] Lewko A B, Waters B. Decentralizing attribute-based encryption. In: Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2011, 568–588

[11] Hu C, Zhang N, Li H, Cheng X, Liao X. Body area network security: a fuzzy attribute-based signcryption scheme. IEEE Journal on Selected Areas in Communications, 2013, 31(9): 37–46

[12] Itkis G, Shen E, Varia M, Wilson D, Yerukhimovich A. Boundedcollusion attribute-based encryption from minimal assumptions. In: Proceedings of the 20th International Conference on Practice and Theory in Public Key Cryptography. 2017, 67–87

[13] Phuong T V X, Ning R, Xin C, Wu H. Puncturable attribute-based encryption for secure data delivery in internet of things. In: Proceedings of 2018 IEEE Conference on Computer Communications. 2018, 1511–1519

[14] Attrapadung N. Unbounded dynamic predicate compositions in attribute-based encryption. In: Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2019, 34–67

[15] Xu S, Yang G, Mu Y. Revocable attribute-based encryption with decryption key exposure resistance and ciphertext delegation. Information Sciences, 2019, 479: 116–134

[16] Li J, Yu Q, Zhang Y, Shen J. Key-policy attribute-based encryption against continual auxiliary input leakage. Information Sciences, 2019, 470: 175–188

[17] Cui J, Zhou H, Xu Y, Zhong H. OOABKS: online/offline attributebased encryption for keyword search in mobile cloud. Information Sciences, 2019, 489: 63–77

[18] Hohenberger S, Lysyanskaya A. How to securely outsource cryptographic computations. In: Proceedings of the 2nd International Conference on Theory of Cryptography. 2005, 264–282

[19] Chen X, Li J, Ma J, Tang Q, Lou W. New algorithms for secure outsourcing of modular exponentiations. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(9): 2386–2396

[20] Zhou K, Afifi M H, Ren J. ExpSOS: secure and verifiable outsourcing of exponentiation operations for mobile clou computing. IEEE Transactions on Information Forensics and Security, 2017, 12(11): 2518–2531

[21] Atallah M J, Frikken K B. Securely outsourcing linear algebra computations. In: Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security. 2010, 48–59

[22] Lei X, Liao X, Huang T, Heriniaina F. Achieving security, robust cheating resistance, and high-efficiency for outsourcing large matrix multiplication computation to a malicious cloud. Information Sciences, 2014, 280: 205–217

[23] Lei X, Liao X, Huang T, Li H. Cloud computing service: the case of large matrix determinant computation. IEEE Transactions on Services Computing, 2015, 8(5): 688–700

[24] Wang C, Ren K, Wang J, Wang Q. Harnessing the cloud for securely outsourcing large-scale systems of linear equations. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(6): 1172–1181

[25] Chen X, Huang X, Li J, Ma J, Lou W, Wong D S. New algorithms for secure outsourcing of large-scale systems of linear equations. IEEE Transactions on Information Forensics and Security, 2015, 10(1): 69–78

[26] Hu C, Alhothaily A, Alrawais A, Cheng X, Sturtivant C, Liu H. A secure and verifiable outsourcing scheme for matrix inverse computation. In: Proceedings of IEEE Conference on Computer Communications. 2017, 1–9

[27] Zhang S, Li H, Jia K, Dai Y S, Zhao L. Efficient secure outsourcing computation of matrix multiplication in cloud computing. In: Proceedings of 2016 IEEE Global Communications Conference. 2016, 1–6

[28] Sun Y, Yu Y, Li X, Zhang K, Qian H, Zhou Y. Batch verifiable computation with public verifiability for outsourcing polynomials and matrix computations. In: Proceedings of the 21st Australasian Conference on Information Security and Privacy. 2016, 293–309

[29] Zhou X, Ding Y, Wang Z, Li X, Ye J, Xu Z. Secure outsourcing algorithm of polynomials in cloud computing. In: Proceedings of the 28th International Conference on Software Engineering and Knowledge Engineering. 2016, 46–51

[30] Jiang X, Kim M, Lauter K E, Song Y. Secure outsourced matrix computation and application to neural networks. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018, 1209–1222

[31] Ren Y, Ding N, Wang T Y, Lu H, Gu D. New algorithms for verifiable outsourcing of bilinear pairings. Science China Information Sciences, 2016, 59(9): 99103

[32] Luo X, Yang X, Niu X. An efficient and secure outsourcing algorithm for bilinear pairing computation. In: Proceedings of the 5th International Conference on Emerging Internetworking, Data & Web Technologies. 2017, 328–339

[33] Fu S, Yu Y, Xu M. Practical privacy-preserving outsourcing of largescale matrix determinant computation in the cloud. In: Proceedings of International Conference on Cloud Computing and Security. 2017, 3–15

[34] Li A, Du W, Li Q. Privacy-preserving outsourcing of large-scale nonlinear programming to the cloud. In: Proceedings of International Conference on Security and Privacy in Communication Networks. 2018, 569–587

[35] Wang C, Ren K,Wang J. Secure optimization computation outsourcing in cloud computing: a case study of linear programming. IEEE Transactions on Computers, 2016, 65(1): 216–229

[36] Cao Z, Liu L. A note on two schemes for secure outsourcing of linear programming. International Journal of Network Security, 2017, 19(2): 323–326

[37] Ren Y, Ding N, Zhang X, Lu H, Gu D. Verifiable outsourcing algorithms for modular exponentiations with improved checkability. In: Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security. 2016, 293–303

[38] Ye J, Xu Z, Ding Y. Secure outsourcing of modular exponentiations in cloud and cluster computing. Cluster Computing, 2016, 19(2): 811–820

[39] Cai J, Ren Y, Jiang T. Verifiable outsourcing computation of modular exponentiations with single server. International Journal of Network Security, 2017, 19(3): 449–457

[40] Zhao L, Zhang M, Shen H, Zhang Y, Shen J. Privacy-preserving outsourcing schemes of modular exponentiations using single untrusted cloud server. KSII Transactions on Internet and Information Systems, 2017, 11(2): 826–845

[41] Liu X, Choo K K R, Deng R H, Lu R, Weng J. Efficient and privacypreserving outsourced calculation of rational numbers. IEEE Transactions on Dependable and Secure Computing, 2018, 15(1): 27–39

[42] Salinas S, Luo C, Chen X, Liao W, Li P. Efficient secure outsourcing of large-scale sparse linear systems of equations. IEEE Transactions on Big Data, 2018, 4(1): 26–39

[43] Pan S, Zheng F, Zhu W, Wang Q. Harnessing the cloud for secure and efficient outsourcing of non-negative matrix factorization. In: Proceedings of 2018 IEEE Conference on Communications and Network Security. 2018, 1–9

[44] Chen Z, Fu A, Xiao K, Su M, Yu Y, Wang Y. Secure and verifiable outsourcing of large-scale matrix inversion without precondition in cloud computing. In: Proceedings of 2018 IEEE International Conference on Communications. 2018, 1–6

[45] Zhang K, Luo C, Li P. Secure outsourcing of matrix convolutions. In: Proceedings of 2018 IEEE International Conference on Communications. 2018, 1–6

[46] Su Q, Yu J, Tian C, Zhang H, Hao R. How to securely outsource the inversion modulo a large composite number. Journal of Systems and Software, 2017, 129: 26–34

[47] Liu X, Qin B, Deng R H, Li Y. An efficient privacy-preserving outsourced computation over public data. IEEE Transactions on Services Computing, 2017, 10(5): 756–770

[48] Luo C, Zhang K, Salinas S, Li P. Efficient privacy-preserving outsourcing of large-scale QR factorization. In: Proceedings of 2017 IEEE Trustcom/BigDataSE/ICESS. 2017, 917–924

[49] Liu X, Qin B, Deng R H, Lu R, Ma J. A privacy-preserving outsourced functional computation framework across large-scale multiple encrypted domains. IEEE Transactions on Computers, 2016, 65(12): 3567–3579

[50] Zhou K, Ren J. Secure outsourcing of scalar multiplication on elliptic curves. In: Proceedings of 2016 IEEE International Conference on Communications. 2016, 1–5

[51] Zhang J, Yang Y, Wang Z. Outsourcing large-scale systems of linear matrix equations in cloud computing. In: Proceedings of the 22nd IEEE International Conference on Parallel and Distributed Systems. 2016, 438–447

[52] Peng B. The determinant: a means to calculate volume. Recall, 2007, 21: a22

[53] Gerald C F, Wheatley P O. Applied Numerical Analysis. 7th ed. Reading, MA, USA: Addison-Wesley, 2003

[54] Goldreich O, Micali S, Wigderson A. How to play any mental game or a completeness theorem for protocols with honest majority. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing. 1987, 218–229

[55] Golle P, Mironov I. Uncheatable distributed computations. In: Proceedings of the Cryptographer’s Track at RSA Conference. 2001, 425–440

[56] Canetti R, Riva B, Rothblum G N. Practical delegation of computation using multiple servers. In: Proceedings of the 18th ACM Conference on Computer and Communications Security. 2011, 445–454

[57] Gennaro R, Gentry C, Parno B. Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Proceedings of the 30th Annual Cryptology Conference. 2010, 465–482

[58] Lyndon R C, Schupp P E, Lyndon R, Schupp P. Combinatorial Group Theory. Berlin, Germany: Springer-Verlag, 1977

[59] Motwani R, Raghavan P. Randomized Algorithms. Cambridge, U.K.: Cambridge University Press, 1995

[60] Chen Y, Nguyen P Q. Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers. In: Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2012, 502–519

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature