Secure and practical outsourcing of linear programming in cloud computing

By Kui Ren, Jia Wang. 2011 Proceedings IEEE INFOCOM, 2011

354 citations recorded by the source corpus.

Cloud computing enables customers with limited computational resources to outsource large-scale computational tasks to the cloud, where massive computational power can be easily utilized in a pay-per-use manner. However, security is the major concern that prevents the wide adoption of computation outsourcing in the cloud, especially when end-user's confidential data are processed and produced during the computation. Thus, secure outsourcing mechanisms are in great need to not only protect sensitive information by enabling computations with encrypted data, but also protect customers from malicious behaviors by validating the computation result. Such a mechanism of general secure computation outsourcing was recently shown to be feasible in theory, but to design mechanisms that are practically efficient remains a very challenging problem. Focusing on engineering computing and optimization tasks, this paper investigates secure outsourcing of widely applicable linear programming (LP) computations. In order to achieve practical efficiency, our mechanism design explicitly decomposes the 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 computations than the general circuit representation. In particular, by formulating private data owned by the customer for LP problem as a set of matrices and vectors, we are able to develop a set of efficient privacy-preserving problem transformation techniques, which allow customers to transform original LP problem into some random one while protecting sensitive input/output information. To validate the computation result, we further explore the fundamental duality theorem of LP computation and derive the necessary and sufficient conditions that correct result must satisfy. Such result verification mechanism is extremely 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/6b8edd0a6631ea436d7f178e69050e983d189431

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

New Algorithms for Secure Outsourcing of Modular Exponentiations (2012, background): “Recently, Wang et al. [49] presented efficient mechanisms for secure outsourcing of linear programming computations.”
Security and privacy for storage and computation in cloud computing (2014, background): “2 Most of the current secure multi-computation (SMC) protocols are at the theoretical level and may be impractical implementation in cloud computing [32] .”
Securely Outsourcing Attribute-Based Encryption with Checkability (2014, background): “Recently, Wang et al. [17] presented efficient mechanisms for secure outsourcing of linear programming computation.”
Secure Cloud Services: Matrix Multiplication Revisited (2013, methodology): “Protecting numerical data in scientific computing, processed by untrusted cloud computing poses a considerable challenges.”
Identity-Based Encryption with Outsourced Revocation in Cloud Computing (2015, background): “[35] presented efficient mechanisms for secure outsourcing of linear programming computation.”
ADMM Based Privacy-Preserving Decentralized Optimization (2017, background): “However, despite successful applications in cloud based control and optimization [26]–[29], conventional cryptographic techniques cannot be applied directly in a completely decentralized setting without the assistance of aggregators/third parties (note that traditional secure multi-party computation”
Verifying computations with state (2013, background): “2522733 the remote hardware and use attestation [60, 63], but what if the hardware is faulty? The client could use a tailored solution [8, 13, 18, 28, 39, 58, 70, 73, 75], but such solutions are not available for all applications.”