More Web Proxy on the site http://driver.im/

research-article

Secure Optimization Computation Outsourcing in Cloud Computing: A Case Study of Linear Programming

Authors:

Jia WangAuthors Info & Claims

IEEE Transactions on Computers, Volume 65, Issue 1

Pages 216 - 229

https://doi.org/10.1109/TC.2015.2417542

Published: 01 January 2016 Publication History

Abstract

Cloud computing enables an economically promising paradigm of computation outsourcing. However, how to protect customers confidential data processed and generated during the computation is becoming the major security concern. Focusing on engineering computing and optimization tasks, this paper investigates secure outsourcing of widely applicable linear programming (LP) computations. Our mechanism design explicitly decomposes LP computation outsourcing into public LP solvers running on the cloud and private LP parameters owned by the customer. The resulting flexibility allows us to explore appropriate security/efficiency tradeoff via higher-level abstraction of LP computation than the general circuit representation. Specifically, by formulating private LP problem as a set of matrices/vectors, we develop efficient privacy-preserving problem transformation techniques, which allow customers to transform the original LP into some random one while protecting sensitive input/output information. To validate the computation result, we further explore the fundamental duality theorem of LP and derive the necessary and sufficient conditions that correct results must satisfy. Such result verification mechanism is very efficient and incurs close-to-zero additional cost on both cloud server and customers. Extensive security analysis and experiment results show the immediate practicability of our mechanism design.

References

[1]

C. Wang, K. Ren, and J. Wang, “Secure and practical outsourcing of linear programming in cloud computing,” in Proc. IEEE INFOCOM , 2011, pp. 820–828.

[2]

P. Mell, and T. Grance, (2011). The NIST definition of cloud computing, Referenced on Nov. 23rd, 2013 [Online]. Available: http://csrc.nist.gov/publications/PubsSPs.html#800-145

[3]

Cloud Security Alliance. (2009). Security guidance for critical areas of focus in cloud computing [Online]. Available: http://www.cloudsecurityalliance.org

[4]

C. Gentry, “Computing arbitrary functions of encrypted data,” Commun. ACM, vol. 53, no. 3, pp. 97– 105, 2010.

Digital Library

[5]

M. J. Atallah, K. N. Pantazopoulos, J. R. Rice, and E. H. Spafford, “Secure outsourcing of scientific computations,” Adv. Comput., vol. 54, pp. 216–272, 2001.

[6]

S. Hohenberger and A. Lysyanskaya, “How to securely outsource cryptographic computations,” in Proc. 2nd Int. Conf. Theory Cryptography, 2005, pp. 264–282.

[7]

M. J. Atallah and J. Li, “Secure outsourcing of sequence comparisons,” Int. J. Inf. Sec. , vol. 4, no. 4, pp. 277–287, 2005.

Digital Library

[8]

D. Benjamin and M. J. Atallah, “Private and cheating-free outsourcing of algebraic computations,” in Proc. Int. Conf. Privacy, Secur., Trust, 2008, pp. 240–245.

[9]

R. Gennaro, C. Gentry, and B. Parno, “ Non-interactive verifiable computing: Outsourcing computation to untrusted workers,” in Proc. 30th Annu. Conf. Adv. Cryptol., Aug. 2010, pp. 465– 482.

[10]

M. Atallah and K. Frikken, “Securely outsourcing linear algebra computations,” in Proc. 5th ACM Symp. Inf., Comput. Commun. Security, 2010, pp. 48–59.

[11]

A. C.-C. Yao, “Protocols for secure computations (extended abstract),” in Proc. 23rd Annu. Symp. Found. Comput. Sci., 1982, pp. 160–164.

[12]

C. Gentry, “Fully homomorphic encryption using ideal lattices,” in Proc. 41st Annu. ACM Symp. Theory Comput., 2009, pp. 169 –178.

[13]

D. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd ed. New York, NY, USA: Springer, 2008.

[14]

C. Wang, N. Cao, K. Ren, and W. Lou, “Enabling secure and efficient ranked keyword search over outsourced cloud data,” IEEE Trans. Parallel Distrib. Syst., vol. 23, no. 8, pp. 1467–1479, Aug. 2012.

Digital Library

[15]

S. Yu, C. Wang, K. Ren, and W. Lou, “Achieving secure, scalable, and fine-grained access control in cloud computing,” in Proc. IEEE INFOCOM, 2010, pp. 1–9.

[16]

S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, U.K.: Cambridge Univ. Press, 2004.

[17]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. Cambridge, MA, USA: MIT Press, 2008.

[18]

C. Jansson, “An NP-hardness result for nonlinear systems,” Reliable Comput., vol. 4, no. 4, pp. 345 –350, 1998.

[19]

P. Van Hentenryck, D. McAllester, and D. Kapur, “ Solving polynomial systems using a branch and prune approach,” SIAM J. Numerical Anal. , vol. 34, no. 2, pp. 797–827, 1997.

Digital Library

[20]

V. Strassen, “Gaussian elimination is not optimal,” Numer. Math., vol. 13, pp. 354–356, 1969.

Digital Library

[21]

D. Coppersmith and S. Winograd, “Matrix multiplication via arithmetic progressions,” in Proc. 19th Annu. ACM Symp. Theory Comput., 1987, pp. 1–6.

[22]

P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in Proc. 17th Int. Conf. Theory Appl. Cryptographic Tech., 1999, pp. 223–238.

Digital Library

[23]

A. Shamir, “How to share a secret,” Commun. ACM , vol. 22, no. 11, pp. 612–613, 1979.

Digital Library

[24]

W. Du and M. J. Atallah, “ Secure multi-party computation problems and their applications: A review and open problems,” in Proc. New Secur. Paradigms Workshop, 2001, pp. 13 –22.

[25]

J. Li and M. J. Atallah, “ Secure and private collaborative linear programming,” in Proc. Int. Conf. Collaborative Comput., 2006, pp. 1–8.

[26]

T. Toft, “Solving linear programs using multiparty computation,” in Proc. 13th Int. Conf. Financial Cryptography Data Security, 2009, pp. 90–107.

[27]

J. Vaidya, “A secure revised simplex algorithm for privacy-preserving linear programming,” in Proc. IEEE Int. Conf. Adv. Inf. Netw. Appl., 2009, pp. 347–354.

[28]

O. Catrina and S. De Hoogh, “Secure multiparty linear programming using fixed-point arithmetic,” in Proc. 15th Eur. Conf. Res. Comput. Security, 2010, pp. 134– 150.

Digital Library

[29]

W. Du, “A study of several specific secure two-party computation problems, ” Ph.D. dissertation, Comput. Sci. Dept., Purdue Univ., West Lafayette, IN, USA, 2001.

[30]

J. Vaidya, “Privacy-preserving linear programming,” in Proc. 24th ACM Symp. Appl. Comput., 2009, pp. 2002–2007.

[31]

A. Bednarz, N. Bean, and M. Roughan, “Hiccups on the road to privacy-preserving linear programming,” in Proc. ACM Workshop Privacy Electron. Soc., 2009, pp. 117–120.

[32]

O. L. Mangasarian, “Privacy-preserving linear programming,” Optim. Lett., vol. 5, pp. 165–172, 2011.

[33]

O. L and. Mangasarian, “ Privacy-preserving horizontally partitioned linear programs,” Optim. Lett. , vol. 6, no. 3, pp. 431–436, 2012.

[34]

S. Goldwasser, Y. Kalai, and G. Rothblum, “ Delegating computation: interactive proofs for muggles,” in Proc. 40th Annu. ACM Symp. Theory Comput., 2008, pp. 113–122.

[35]

P. Golle and I. Mironov, “Uncheatable distributed computations,” in Proc. Conf. Topics Cryptol.: The Cryptographer's Track RSA, 2001, pp. 425–440.

[36]

D. Szajda, B. G. Lawson, and J. Owen, “Hardening functions for large scale distributed computations,” in Proc. IEEE Symp. Secur. Privacy , 2003, pp. 216–224.

[37]

W. Du, J. Jia, M. Mangal, and M. Murugesan, “Uncheatable grid computing,” in Proc. 24th Int. Conf. Distrib. Comput. Syst., 2004, pp. 4 –11.

Cited By

Yang WWu SFei JZeng XDing YXia Z(2024)A Bitcoin-based Secure Outsourcing Scheme for Optimization Problem in Multimedia Internet of ThingsACM Transactions on Multimedia Computing, Communications, and Applications10.1145/363748920:6(1-23)Online publication date: 8-Mar-2024
https://dl.acm.org/doi/10.1145/3637489
Zhang ZZhu HXie M(2024)Differential privacy may have a potential optimization effect on some swarm intelligence algorithms besides privacy-preservingInformation Sciences: an International Journal10.1016/j.ins.2023.119870654:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.ins.2023.119870
Luo YZhang SZhang SLiu JWang YYang S(2023)A Secure and Efficient Framework for Outsourcing Large-scale Matrix Determinant and Linear EquationsACM Transactions on Embedded Computing Systems10.1145/361101422:5(1-22)Online publication date: 26-Sep-2023
https://dl.acm.org/doi/10.1145/3611014
Show More Cited By

Index Terms

Secure Optimization Computation Outsourcing in Cloud Computing: A Case Study of Linear Programming

Index terms have been assigned to the content through auto-classification.

Recommendations

On linear programming relaxations for solving polynomial programming problems
Highlights
- Theoretically compared the tightness of the J-set relaxation with the recursive McCormick relaxations.
Abstract
This paper studies linear programming (LP) relaxations for solving polynomial programming problems. A polynomial programming problem can be equivalently formulated as a quadratically constrained quadratic program (QCQP) by introducing ...
Parametric global optimisation for bilevel programming

We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower's) ...
Valid Linear Programming Bounds for Exact Mixed-Integer Programming

Fast computation of valid linear programming LP bounds serves as an important subroutine for solving mixed-integer programming problems exactly. We introduce a new method for computing valid LP bounds designed for this application. The algorithm ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 65, Issue 1

Jan. 2016

342 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © 2015.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 January 2016

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yang WWu SFei JZeng XDing YXia Z(2024)A Bitcoin-based Secure Outsourcing Scheme for Optimization Problem in Multimedia Internet of ThingsACM Transactions on Multimedia Computing, Communications, and Applications10.1145/363748920:6(1-23)Online publication date: 8-Mar-2024
https://dl.acm.org/doi/10.1145/3637489
Zhang ZZhu HXie M(2024)Differential privacy may have a potential optimization effect on some swarm intelligence algorithms besides privacy-preservingInformation Sciences: an International Journal10.1016/j.ins.2023.119870654:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.ins.2023.119870
Luo YZhang SZhang SLiu JWang YYang S(2023)A Secure and Efficient Framework for Outsourcing Large-scale Matrix Determinant and Linear EquationsACM Transactions on Embedded Computing Systems10.1145/361101422:5(1-22)Online publication date: 26-Sep-2023
https://dl.acm.org/doi/10.1145/3611014
Sun XTian CHu CTian WZhang HYu J(2022)Privacy-Preserving and verifiable SRC-based face recognition with cloud/edge server assistanceComputers and Security10.1016/j.cose.2022.102740118:COnline publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1016/j.cose.2022.102740
Sharma PJindal RBorah M(2022)A Review of Blockchain-Based Applications and ChallengesWireless Personal Communications: An International Journal10.1007/s11277-021-09176-7123:2(1201-1243)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s11277-021-09176-7
Akbar MMahmood SMeshram CAlsanad AGumaei AAlQahtani S(2022)Barriers of managing cloud outsource software development projects: a multivocal studyMultimedia Tools and Applications10.1007/s11042-021-11245-981:25(35571-35594)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11042-021-11245-9
Sharma PJindal RBorah M(2021)Blockchain-based decentralized architecture for cloud storage systemJournal of Information Security and Applications10.1016/j.jisa.2021.10297062:COnline publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.jisa.2021.102970
Sharma PJindal RBorah M(2020)Blockchain Technology for Cloud StorageACM Computing Surveys10.1145/340395453:4(1-32)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3403954
Zhang YXiao XYang LXiang YZhong S(2020)Secure and Efficient Outsourcing of PCA-Based Face RecognitionIEEE Transactions on Information Forensics and Security10.1109/TIFS.2019.294787215(1683-1695)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1109/TIFS.2019.2947872
Zhou QTian CZhang HYu JLi F(2020)How to securely outsource the extended euclidean algorithm for large-scale polynomials over finite fieldsInformation Sciences: an International Journal10.1016/j.ins.2019.10.007512:C(641-660)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1016/j.ins.2019.10.007
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents