Secure outsourcing of large matrix determinant computation

doi:10.1007/s11704-019-9189-7

Front. Comput. Sci.

2020, Vol. 14

Issue (6) : 146807 https://doi.org/10.1007/s11704-019-9189-7

RESEARCH ARTICLE

Secure outsourcing of large matrix determinant computation

Jiayang LIU¹, Jingguo BI^2,³(

), Mu LI⁴

¹. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
². Beijing Research Institute of Telemetry, Beijing 100094, China
³. Institute for Advanced Study, Tsinghua University, Beijing 100084, China
⁴. Space Star Technology Co., Ltd, Beijing 100086, China

Download: PDF(309 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Jingguo BI

Just Accepted Date: 19 August 2019 Issue Date: 17 March 2020

Cite this article:

Jiayang LIU,Jingguo BI,Mu LI. Secure outsourcing of large matrix determinant computation[J]. Front. Comput. Sci., 2020, 14(6): 146807.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-019-9189-7
https://academic.hep.com.cn/fcs/EN/Y2020/V14/I6/146807

1	C Gentry. A fully homomorphic encryption scheme. Doctoral Dissertation, Stanford University, 2009. https://doi.org/10.1145/1536414.1536440
2	B Parno, J Howell, C Gentry, M Raykova. Pinocchio: nearly practical verifiable computation. In: Proceedings of 2013 IEEE Symposium on Security and Privacy. 2013, 238–252 https://doi.org/10.1109/SP.2013.47
3	Z Brakerski, V Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. SIAM Journal on Computing, 2014, 43(2): 831–871 https://doi.org/10.1137/120868669
4	Y Doröz, E öztürk, B Sunar. Accelerating fully homomorphic encryption in hardware. IEEE Transactions on Computers, 2015, 64(6): 1509–1521
5	G Alagic, Y Dulek, C Schaffner, F Speelman. 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 https://doi.org/10.1007/978-3-319-70694-8_16
6	A López-Alt, E Tromer, V Vaikuntanathan. Multikey fully homomorphic encryption and applications. SIAM Journal on Computing, 2017, 46(6): 1827–1892 https://doi.org/10.1137/14100124X
7	D Boneh, R Gennaro, S Goldfeder, A Jain, S Kim, P M R Rasmussen, A Sahai. Threshold cryptosystems from threshold fully homomorphic encryption. In: Proceedings of the 38th Annual International Cryptology Conference. 2018, 565–596 https://doi.org/10.1007/978-3-319-96884-1_19
8	V Goyal, O Pandey, A Sahai, B Waters. 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 https://doi.org/10.1145/1180405.1180418
9	B Waters. 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 https://doi.org/10.1007/978-3-642-19379-8_4
10	A B Lewko, B Waters. Decentralizing attribute-based encryption. In: Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2011, 568–588 https://doi.org/10.1007/978-3-642-20465-4_31
11	C Hu, N Zhang, H Li, X Cheng, X Liao. Body area network security: a fuzzy attribute-based signcryption scheme. IEEE Journal on Selected Areas in Communications, 2013, 31(9): 37–46 https://doi.org/10.1109/JSAC.2013.SUP.0513004
12	G Itkis, E Shen, M Varia, D Wilson, A Yerukhimovich. 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 https://doi.org/10.1007/978-3-662-54388-7_3
13	T V X Phuong, R Ning, C Xin, H Wu. 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	N Attrapadung. 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 https://doi.org/10.1007/978-3-030-17653-2_2
15	S Xu, G Yang, Y Mu. Revocable attribute-based encryption with decryption key exposure resistance and ciphertext delegation. Information Sciences, 2019, 479: 116–134 https://doi.org/10.1016/j.ins.2018.11.031
16	J Li, Q Yu, Y Zhang, J Shen. Key-policy attribute-based encryption against continual auxiliary input leakage. Information Sciences, 2019, 470: 175–188 https://doi.org/10.1016/j.ins.2018.07.077
17	J Cui, H Zhou, Y Xu, H Zhong. OOABKS: online/offline attributebased encryption for keyword search in mobile cloud. Information Sciences, 2019, 489: 63–77 https://doi.org/10.1016/j.ins.2019.03.043
18	S Hohenberger, A Lysyanskaya. How to securely outsource cryptographic computations. In: Proceedings of the 2nd International Conference on Theory of Cryptography. 2005, 264–282 https://doi.org/10.1007/978-3-540-30576-7_15
19	X Chen, J Li, J Ma, Q Tang, W Lou. New algorithms for secure outsourcing of modular exponentiations. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(9): 2386–2396 https://doi.org/10.1109/TPDS.2013.180
20	K Zhou, M H Afifi, J Ren. ExpSOS: secure and verifiable outsourcing of exponentiation operations for mobile clou computing. IEEE Transactions on Information Forensics and Security, 2017, 12(11): 2518–2531 https://doi.org/10.1109/TIFS.2017.2710941
21	M J Atallah, K B Frikken. Securely outsourcing linear algebra computations. In: Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security. 2010, 48–59 https://doi.org/10.1145/1755688.1755695
22	X Lei, X Liao, T Huang, F Heriniaina. Achieving security, robust cheating resistance, and high-efficiency for outsourcing large matrix multiplication computation to a malicious cloud. Information Sciences, 2014, 280: 205–217 https://doi.org/10.1016/j.ins.2014.05.014
23	X Lei, X Liao, T Huang, H Li . Cloud computing service: the case of large matrix determinant computation. IEEE Transactions on Services Computing, 2015, 8(5): 688–700 https://doi.org/10.1109/TSC.2014.2331694
24	C Wang, K Ren, J Wang, Q Wang. Harnessing the cloud for securely outsourcing large-scale systems of linear equations. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(6): 1172–1181 https://doi.org/10.1109/TPDS.2012.206
25	X Chen, X Huang, J Li, J Ma, W Lou, D S Wong. New algorithms for secure outsourcing of large-scale systems of linear equations. IEEE Transactions on Information Forensics and Security, 2015, 10(1): 69–78 https://doi.org/10.1109/TIFS.2014.2363765
26	C Hu, A Alhothaily, A Alrawais, X Cheng, C Sturtivant, H Liu. A secure and verifiable outsourcing scheme for matrix inverse computation. In: Proceedings of IEEE Conference on Computer Communications. 2017, 1–9 https://doi.org/10.1109/INFOCOM.2017.8057199
27	S Zhang, H Li, K Jia, Y S Dai, L Zhao. Efficient secure outsourcing computation of matrix multiplication in cloud computing. In: Proceedings of 2016 IEEE Global Communications Conference. 2016, 1–6 https://doi.org/10.1109/GLOCOM.2016.7841783
28	Y Sun, Y Yu, X Li, K Zhang, H Qian, Y Zhou. 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 https://doi.org/10.1007/978-3-319-40253-6_18
29	X Zhou, Y Ding, Z Wang, X Li, J Ye, Z Xu. Secure outsourcing algorithm of polynomials in cloud computing. In: Proceedings of the 28th International Conference on Software Engineering and Knowledge Engineering. 2016, 46–51 https://doi.org/10.18293/SEKE2016-022
30	X Jiang, M Kim, K E Lauter, Y Song. 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 https://doi.org/10.1145/3243734.3243837
31	Y Ren, N Ding, T Y Wang, H Lu, D Gu. New algorithms for verifiable outsourcing of bilinear pairings. Science China Information Sciences, 2016, 59(9): 99103 https://doi.org/10.1007/s11432-016-5550-8
32	X Luo, X Yang, X Niu. 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 https://doi.org/10.1007/978-3-319-59463-7_33
33	S Fu, Y Yu, M Xu. 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 https://doi.org/10.1007/978-3-319-68542-7_1
34	A Li, W Du, Q Li. 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 https://doi.org/10.1007/978-3-030-01701-9_31
35	C Wang, K Ren, J Wang. Secure optimization computation outsourcing in cloud computing: a case study of linear programming. IEEE Transactions on Computers, 2016, 65(1): 216–229 https://doi.org/10.1109/TC.2015.2417542
36	Z Cao, L Liu. A note on two schemes for secure outsourcing of linear programming. International Journal of Network Security, 2017, 19(2): 323–326
37	Y Ren, N Ding, X Zhang, H Lu, D Gu. 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 https://doi.org/10.1145/2897845.2897881
38	J Ye, Z Xu, Y Ding. Secure outsourcing of modular exponentiations in cloud and cluster computing. Cluster Computing, 2016, 19(2): 811–820 https://doi.org/10.1007/s10586-016-0571-z
39	J Cai, Y Ren, T Jiang. Verifiable outsourcing computation of modular exponentiations with single server. International Journal of Network Security, 2017, 19(3): 449–457
40	L Zhao, M Zhang, H Shen, Y Zhang, J Shen. Privacy-preserving outsourcing schemes of modular exponentiations using single untrusted cloud server. KSII Transactions on Internet and Information Systems, 2017, 11(2): 826–845 https://doi.org/10.3837/tiis.2017.02.011
41	X Liu, K K R Choo, R H Deng, R Lu, J Weng. Efficient and privacypreserving outsourced calculation of rational numbers. IEEE Transactions on Dependable and Secure Computing, 2018, 15(1): 27–39 https://doi.org/10.1109/TDSC.2016.2536601
42	S Salinas, C Luo, X Chen, W Liao, P Li. Efficient secure outsourcing of large-scale sparse linear systems of equations. IEEE Transactions on Big Data, 2018, 4(1): 26–39 https://doi.org/10.1109/TBDATA.2017.2679760
43	S Pan, F Zheng, W Zhu, Q Wang. 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 https://doi.org/10.1109/CNS.2018.8433195
44	Z Chen, A Fu, K Xiao, M Su, Y Yu, Y Wang. 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 https://doi.org/10.1109/ICC.2018.8422326
45	K Zhang, C Luo, P Li. Secure outsourcing of matrix convolutions. In: Proceedings of 2018 IEEE International Conference on Communications. 2018, 1–6 https://doi.org/10.1109/ICC.2018.8422483
46	Q Su, J Yu, C Tian, H Zhang, R Hao. How to securely outsource the inversion modulo a large composite number. Journal of Systems and Software, 2017, 129: 26–34 https://doi.org/10.1016/j.jss.2017.04.015
47	X Liu, B Qin, R H Deng, Y Li. An efficient privacy-preserving outsourced computation over public data. IEEE Transactions on Services Computing, 2017, 10(5): 756–770 https://doi.org/10.1109/TSC.2015.2511008
48	C Luo, K Zhang, S Salinas, P Li. Efficient privacy-preserving outsourcing of large-scale QR factorization. In: Proceedings of 2017 IEEE Trustcom/BigDataSE/ICESS. 2017, 917–924 https://doi.org/10.1109/Trustcom/BigDataSE/ICESS.2017.331
49	X Liu, B Qin, R H Deng, R Lu, J Ma. A privacy-preserving outsourced functional computation framework across large-scale multiple encrypted domains. IEEE Transactions on Computers, 2016, 65(12): 3567–3579 https://doi.org/10.1109/TC.2016.2543220
50	K Zhou, J Ren. Secure outsourcing of scalar multiplication on elliptic curves. In: Proceedings of 2016 IEEE International Conference on Communications. 2016, 1–5 https://doi.org/10.1109/ICC.2016.7511325
51	J Zhang, Y Yang, Z Wang. 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 https://doi.org/10.1109/ICPADS.2016.0066
52	B Peng. The determinant: a means to calculate volume. Recall, 2007, 21: a22
53	C F Gerald, P O Wheatley. Applied Numerical Analysis. 7th ed. Reading, MA, USA: Addison-Wesley, 2003
54	O Goldreich, S Micali, A Wigderson. 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 https://doi.org/10.1145/28395.28420
55	P Golle, I Mironov. Uncheatable distributed computations. In: Proceedings of the Cryptographer’s Track at RSA Conference. 2001, 425–440 https://doi.org/10.1007/3-540-45353-9_31
56	R Canetti, B Riva, G N Rothblum. Practical delegation of computation using multiple servers. In: Proceedings of the 18th ACM Conference on Computer and Communications Security. 2011, 445–454 https://doi.org/10.1145/2046707.2046759
57	R Gennaro, C Gentry, B Parno. Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Proceedings of the 30th Annual Cryptology Conference. 2010, 465–482 https://doi.org/10.1007/978-3-642-14623-7_25
58	R C Lyndon, P E Schupp, R Lyndon, P Schupp. Combinatorial Group Theory. Berlin, Germany: Springer-Verlag, 1977
59	R Motwani, P Raghavan. Randomized Algorithms. Cambridge, U.K.: Cambridge University Press, 1995 https://doi.org/10.1017/CBO9780511814075
60	Y Chen, P Q Nguyen. 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 https://doi.org/10.1007/978-3-642-29011-4_30

[1]

Article highlights

Download

[1]	Wei ZHENG, Ying WU, Xiaoxue WU, Chen FENG, Yulei SUI, Xiapu LUO, Yajin ZHOU. A survey of Intel SGX and its applications[J]. Front. Comput. Sci., 2021, 15(3): 153808-.
[2]	Najme MANSOURI, Mohammad Masoud JAVIDI, Behnam Mohammad Hasani ZADE. Hierarchical data replication strategy to improve performance in cloud computing[J]. Front. Comput. Sci., 2021, 15(2): 152501-.
[3]	Meysam VAKILI, Neda JAHANGIRI, Mohsen SHARIFI. Cloud service selection using cloud service brokers: approaches and challenges[J]. Front. Comput. Sci., 2019, 13(3): 599-617.
[4]	Qiang LIU, Xiaoshe DONG, Heng CHEN, Yinfeng WANG. IncPregel: an incremental graph parallel computation model[J]. Front. Comput. Sci., 2018, 12(6): 1076-1089.
[5]	Fei TIAN, Tao QIN, Tie-Yan LIU. Computational pricing in Internet era[J]. Front. Comput. Sci., 2018, 12(1): 40-54.
[6]	Xiong FU, Juzhou CHEN, Song DENG, Junchang WANG, Lin ZHANG. Layered virtual machine migration algorithm for network resource balancing in cloud computing[J]. Front. Comput. Sci., 2018, 12(1): 75-85.
[7]	Najme MANSOURI. Adaptive data replication strategy in cloud computing for performance improvement[J]. Front. Comput. Sci., 2016, 10(5): 925-935.
[8]	Haibao CHEN,Song WU,Hai JIN,Wenguang CHEN,Jidong ZHAI,Yingwei LUO,Xiaolin WANG. A survey of cloud resource management for complex engineering applications[J]. Front. Comput. Sci., 2016, 10(3): 447-461.
[9]	Zhaoning ZHANG,Dongsheng LI,Kui WU. Large-scale virtual machines provisioning in clouds:challenges and approaches[J]. Front. Comput. Sci., 2016, 10(1): 2-18.
[10]	Bing YU,Yanni HAN,Hanning YUAN,Xu ZHOU,Zhen XU. A cost-effective scheme supporting adaptive service migration in cloud data center[J]. Front. Comput. Sci., 2015, 9(6): 875-886.
[11]	Xiong FU,Chen ZHOU. Virtual machine selection and placement for dynamic consolidation in Cloud computing environment[J]. Front. Comput. Sci., 2015, 9(2): 322-330.
[12]	Solomon Guadie WORKU,Chunxiang XU,Jining ZHAO. Cloud data auditing with designated verifier[J]. Front. Comput. Sci., 2014, 8(3): 503-512.
[13]	Heng WU, Wenbo ZHANG, Jianhua ZHANG, Jun WEI, Tao HUANG. A benefit-aware on-demand provisioning approach for multi-tier applications in cloud computing[J]. Front Comput Sci, 2013, 7(4): 459-474.
[14]	Haibo MI, Huaimin WANG, Yangfan ZHOU, Michael Rung-Tsong LYU, Hua CAI, Gang YIN. An online service-oriented performance profiling tool for cloud computing systems[J]. Front Comput Sci, 2013, 7(3): 431-445.
[15]	Ling LIU. Computing infrastructure for big data processing[J]. Front Comput Sci, 2013, 7(2): 165-170.

Viewed

Full text

Abstract

Cited

Shared

Discussed