SCIENCE CHINA Information Sciences, Volume 61, Issue 3: 032112(2018) https://doi.org/10.1007/s11432-017-9208-3

Privacy-preserving large-scale systems of linear equations in outsourcing storage and computation

More info
  • ReceivedMar 18, 2017
  • AcceptedAug 16, 2017
  • PublishedFeb 2, 2018


Along with the prevalence of cloud computing, it can be realised to efficiently outsource costly storage or computations to cloud servers. Recently, secure outsourcing mechanism has received more and more attention. We focus on secure outsourcing storage and computation for large-scale systems of linear equations (LEs) in this paper. Firstly, we construct a new efficient matrix encryption scheme. Then we exploit this encryption scheme to develop a new algorithm which can implement outsourcing storage and computation for large-scale linear equations in the semi-honest setting. Compared with the previous work, the proposed algorithm requires lower storage overhead and is with competitive efficiency.


This work was supported in part by National Natural Science Foundation of China (Grant Nos. 61371083, 61373154, 61632012, 61672239), Prioritized Development Projects through the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20130073130004), and Shanghai High-Tech Field Project (Grant No. 16511101400).


[1] Cloud Security Alliance. Security guidance for critical areas of focus in cloud computing. 2009. http://www.cloudsecurityalliance.org. Google Scholar

[2] Wang C, Ren K, Wang J. Secure optimization computation outsourcing in cloud computing: a case study of linear programming. IEEE Comput Soc, 2016, 65: 216--229. Google Scholar

[3] Loftus J, Smart N P. Secure outsourced computation. In: Proceedings of International Conference on Cryptology in Africa, Dakar, 2011. 1--20. Google Scholar

[4] Zhou J, Cao Z F, Dong X L, et al. EVOC: more efficient verifiable outsourced computation from any one-way trapdoor function. In: Proceedings of IEEE International Conference on Communications, London, 2015. 7444--7449. Google Scholar

[5] Pearson S, Benameur A. Privacy, security and trust issues arising from cloud computing. In: Proceeding of IEEE Second International Conference on Cloud Computing Technology and Science, Indianapolis, 2010. 693--702. Google Scholar

[6] Zissis D, Lekkas D. Addressing cloud computing security issues. Future Gener Comput Syst, 2012, 28: 583--592. Google Scholar

[7] Sen J. Security and privacy issues in cloud computing. Comput Sci, 2013, 7: 238--252. Google Scholar

[8] Cao Z F. New trends of information security — how to change peoples life style? Sci China Inf Sci, 2016, 59: 050106. Google Scholar

[9] Benzi M. Preconditioning techniques for large linear systems: a survey. J Comput Phys, 2002, 182: 418--477. Google Scholar

[10] Edelman A. Large dense numerical linear algebra in 1993: the parallel computing influence. Int J High Perform Comput Appl, 1993, 7: 113--128. Google Scholar

[11] Wang C, Ren K, Wang J, et al. Harnessing the cloud for securely outsourcing large-scale systems of linear equations. IEEE Trans Parall Distrib Syst, 2013, 24: 1172--1181. Google Scholar

[12] Salinas S, Luo C Q, Chen X H, et al. Efficient secure outsourcing of large-scale linear systems of equations. In: Proceedings of IEEE Conference on Computer Communications, Hong Kong, 2015. 281--292. Google Scholar

[13] Chen X F, Huang X Y, Li J, et al. New algorithms for secure outsourcing of large-scale systems of linear equations. IEEE Trans Inf Foren Secur, 2015, 10: 69--78. Google Scholar

[14] Gennaro R, Gentry C, Parno B. Non-interactive verifiable computing: outsourcing computation to untrusted workers. Lect Notes Comput Sci, 2010, 6223: 465--482. Google Scholar

[15] Yao A C. Protocols for secure computations. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. Washington: IEEE, 1982. 160--164. Google Scholar

[16] Gentry C. Fully homomorphic encryption using ideal lattices. In: Proceedings of ACM Symposium on Theory of Computing, Bethesda, 2009. 169--178. Google Scholar

[17] Atallah M J, Frikken K B. Securely outsourcing linear algebra computations. In: Proceedings of ACM Symposium on Information, Computer and Communications Security, Beijing, 2010. 48--59. Google Scholar

[18] Nassar M, Erradi A, Malluhi Q M. Practical and secure outsourcing of matrix computations to the cloud. In: Proceedings of the 33rd International Conference on Distributed Computing Systems, Pennsylvania, 2013. 70--75. Google Scholar

[19] Li D M, Dong X L, Cao Z F. Secure and privacy-preserving pattern matching in outsourced computing. Secur Commun Netw, 2016, 9: 3444--3451. Google Scholar

[20] Lei X Y, Liao X F, Huang T W, et al. Outsourcing large matrix inversion computation to a public cloud. IEEE Trans Cloud Comput, 2013, 1: 78--87. Google Scholar

[21] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In: Proceedings of International Conference on Theory and Application of Cryptographic Techniques, Prague, 1999. 223--238. Google Scholar

[22] Bellare M. Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of ACM Conference on Computer and Communications Security, Virginia, 1993. 62--73. Google Scholar

[23] Goldwasser S, Micali S, Rivest R L. A digital signature scheme secure against adaptive chosen-message attacks. Soc Ind Appl Math, 1988, 17: 281--308. Google Scholar

[24] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM, 1978, 21: 120--126. Google Scholar

[25] Williams H. A modification of the RSA public-key encryption procedure. IEEE Trans Inf Theory, 1980, 26: 726--729. Google Scholar

[26] Blum L. A simple unpredictable pseudo-random number generator. SIAM J Comput, 1986, 15: 364--383. Google Scholar

[27] Hohenberger S, Lysyanskaya A. How to securely outsource cryptographic computations. Theory Cryptogr, 2005, 3378: 264--282. Google Scholar

[28] Liu X M, Deng R H, Ding W X, et al. Privacy-preserving outsourced calculation on floating point numbers. IEEE Trans Inf Foren Secur, 2017, 11: 2513--2527. Google Scholar

  • Figure 1

    Framework for our scheme.

  • Figure 2

    (Color online) Computation cost in the user side.

  • Figure 3

    (Color online) Storage cost in the user side.

  • Table 1   Comparison with the existing schemes
    Scheme [11] Scheme [12] Scheme [13] Our scheme
    Storage cost O($n^2$) O($n^2$ ) O($n^2$ ) O(1)
    Computation of ProbGen ($2n^2+n)M+2.25k^2n^2M$ $(4n^2+4n)M$ $((2\lambda+1)n^2+\lambda~n)M$ $(2n^2+n)M+1.5knM$
    Computation of solve $2.25k^2LnM$ $(22Ln-4L)M$ $\lambda~nM$ $1.5knM+nM$
    Communication round $L$ $L$ 1 1

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号