Efficient Secure Outsourcing of Large-scale Convex Separable Programming for Big Data
Abstract:
Big data has become a key basis of innovation and intelligence, potentially making our lives more convenient and bringing new opportunities to the modern society. Towards this goal, a critical underlying task is to solve a series of large-scale fundamental problems. Conducting such large-scale data analytics in a timely manner requires a large amount of computing resources, which may not be available for individuals and small companies in practice. By outsourcing their computations to the cloud, clients can solve such problems in a cost-effective way. However, confidential data stored at the cloud is vulnerable to cyber attacks, and thus needs to be protected. Previous works employ cryptographic techniques like homomorphic encryption, which significantly increase the computational complexity of solving a large-scale problem at the cloud and is impractical for big data applications. For the first time in the literature, we present an efficient secure outsourcing scheme for convex separable programming problems (CSPs). In particular, we first develop efficient matrix and vector transformation schemes only based on arithmetic operations that are computationally indistinguishable both in value and in structure under a chosen-plaintext attack (CPA). Then, we design a secure outsourcing scheme in which the client and the cloud collaboratively solve the transformed problems. The client can efficiently verify the correctness of returned results to prevent any malicious behavior of the cloud. Theoretical correctness and privacy analysis together show that the proposed scheme obtains optimal results and that the cloud cannot learn private information from the client’s concealed data. We conduct extensive simulations on Amazon Elastic Cloud Computing (EC2) platform and find that our proposed scheme provides significant time savings to the clients.
Existing System:
To tackle the data privacy issues in outsourcing paradigm for cloud computing, there have been some existing schemes that are designed and applied to encrypt and outsource basic mathematical problems. For example, Yan et al. [19] propose a deduplication scheme while preserving the privacy of data storage in the cloud. Jiang et al. [20] investigate the secure data integrity auditing for shared dynamic data. Our previous works in [21], [22] study the secure outsourcing of linear systems of equations and quadratic programming problems. Zhou et al. provide a privacypreserving outsourcing tool that focuses on a quadratic programming problem [23]. Outsourcing methods for modular exponentiation, image reconstruction, linear regression and database are also reported in [24], [25], [26], [27], respectively. Moreover, there are privacy-preserving outsourcing schemes for matrix operations, including matrix inversion [14], [28], matrix determinant [29], and matrix multiplication [30]. These works can be generally classified into two categories: cryptographic approaches and transformation based approaches. In particular, there are some works based on traditional cryptographic techniques for secure outsourcing of large-scale computations to the cloud to protect and analyze clients’ data. Gennaro et al.
Proposed System:
We propose an efficient secure outsourcing algorithm for solving large-scale CSPs. Specifically, we consider a CSP where the objective function and constraints are composed of convex functions. Firstly we develop an efficient transformation scheme to preserve the privacy of vectors and matrices. We prove that the secure transformation of vector and matrices is computationally indistinguishable both in value and structure under a chosen plaintext attack (CPA). Then, we utilize the characteristics of CSPs and linearize the convex functions in the CSP problem with arbitrary accuracy, which results in solving a series of secure large-scale linear programming (LP) problems in the cloud. Next, we securely outsource the LP problems to the cloud for solutions. To ensure the returned results’ integrity, we adopt a light-weight scheme to effectively verify the correctness of the final results.
CONCLUSIONS:
In this paper, we have investigated the problem of secure outsourcing of large-scale CSPs. To the best of our knowledge, this is the first work to solve CSPs in a secure manner in cloud computing. To protect the client’s private data, we have developed efficient vector and matrix transformation and permutation schemes that are solely based on linear algebra. We have shown that the values and positions of the transformed data are computationally indistinguishable from random vector and and matrices under chosenplaintext attack (CPA), or CPA-secure. Therefore, the client can confidently share the transformed data with the cloud. The proposed secure linear approximation algorithm can enable the cloud server to efficiently find the solution while protecting the client’s privacy. In addition, the correctness of the returned results from the cloud can be efficiently verified by the client to prevent any malicious behavior of the cloud. The theoretical privacy analysis has demonstrated that the privacy of client’s data is well preserved. Experimental results on Amazon Elastic Compute Cloud (EC2) have shown that the proposed algorithm can efficiently solve the large-scale CSPs with noticeable time savings for the client. Moreover, our proposed scheme requires the client to help the cloud solve the problem, which incurs communication cost. In the future work, we plan to design a non-interactive secure outsourcing of CSPs scheme so that the client does not need to be involved during the process.
REFERENCES:
[1] V. Turner, J. F. Gantz, D. Reinsel, and S. Minton, “The digital universe of opportunities: rich data and the increasing value of the internet of things,” IDC Analyze the Future, Apr. 2014.
[2] E. Bender, “Big data in biomedicine,” Nature, vol. 527, no. 7576, pp. S1–S1, Apr. 2015.
[3] G. Adomavicius and A. Tuzhilin, “Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions,” IEEE Trans. on knowledge and data engineering, vol. 17, no. 6, pp. 734–749, Jun. 2005.
[4] A. Ipakchi and F. Albuyeh, “Grid of the future,” IEEE Power and Energy Magazine, vol. 7, no. 2, pp. 52–62, Mar. 2009.
[5] S. M. Stefanov, Separable programming: theory and methods. Springer Science & Business Media, Nov. 2013.
[6] W. Liao, W. Du, S. Salinas, and P. Li, “Efficient privacy-preserving outsourcing of large-scale convex separable programming for smart cities,” in IEEE 14th International Conference on Smart City. IEEE, Dec. 2016.
[7] W. Liao, M. Li, S. Salinas, P. Li, and M. Pan, “Energy-sourceaware cost optimization for green cellular networks with strong stability,” IEEE Trans. on Emerging Topics in Computing, vol. 4, no. 4, pp. 541–555, 2016.
[8] D. P. Bertsekas, Nonlinear programming. Athena scientific Belmont, Sep. 1999.
[9] B.-L. Lu and K. Ito, “Converting general nonlinear programming problems into separable programming problems with feedforward neural networks,” Neural networks, vol. 16, no. 7, pp. 1059–1074, Sep. 2003.
[10] I. A. T. Hashem, I. Yaqoob, N. B. Anuar, S. Mokhtar, A. Gani, and S. U. Khan, “The rise of “big data” on cloud computing: Review and open research issues,” Information Systems, vol. 47, pp. 98–115, Jan. 2015.
[11] W. Venters and E. A. Whitley, “A critical review of cloud computing: researching desires and realities,” Journal of Information Technology, vol. 27, no. 3, pp. 179–197, Sep. 2012.
[12] S. Marston, Z. Li, S. Bandyopadhyay, J. Zhang, and A. Ghalsasi, “Cloud computing– the business perspective,” Decision support systems, vol. 51, no. 1, pp. 176–189, Apr. 2011.