Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

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 LIU1, Jingguo BI2,3(), Mu LI4
1. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
2. Beijing Research Institute of Telemetry, Beijing 100094, China
3. Institute for Advanced Study, Tsinghua University, Beijing 100084, China
4. 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