Secure and Practical Outsourcing of Linear Programming in Cloud Computing


  Secure and Practical Outsourcing of Linear Programming in Cloud Computing.pdf (Size: 277.01 KB / Downloads: 0)


INTRODUCTION

Cloud Computing provides convenient on-demand network
access to a shared pool of configurable computing resources
that can be rapidly deployed with great efficiency and minimal
management overhead [1]. One fundamental advantage of the
cloud paradigm is computation outsourcing, where the computational
power of cloud customers is no longer limited by their
resource-constraint devices. By outsourcing the workloads into
the cloud, customers could enjoy the literally unlimited computing
resources in a pay-per-use manner without committing
any large capital outlays in the purchase of both hardware and
software and/or the operational overhead therein.


PROBLEM STATEMENT
A. System and Threat Model

We consider a computation outsourcing architecture involving
two different entities, as illustrated in Fig. 1: the
cloud customer, who has large amount of computationally
expensive LP problems to be outsourced to the cloud; the cloud
server (CS), which has significant computation resources and
provides utility computing services, such as hosting the public
LP solvers in a pay-per-use manner.


THE PROPOSED SCHEMES

This section presents our LP outsourcing scheme which
provides a complete outsourcing solution for – not only
the privacy protection of problem input/output, but also its
efficient result checking. We start from an overview of secure
LP outsourcing design framework and discuss a few basic
techniques and their demerits, which leads to a stronger problem
transformation design utilizing affine mapping. We then
discuss effective result verification by leveraging the duality
property of LP. Finally, we give the full scheme description.


Experiment Results

We now assess the practical efficiency of the proposed
secure and verifiable LP outsourcing scheme with experiments.
We implement the proposed mechanism including both the
customer and the cloud side processes in Matlab and utilize
the MOSEK optimization [20] through its Matlab interface to
solve the original LP problem  and encrypted LP problem
K. Both customer and cloud server computations in our experiment
are conducted on the same workstation with an Intel
Core 2 Duo processor running at 1.86 GHz with 4 GB RAM.


RELATED WORK
A. Work on Secure Computation Outsourcing
General secure computation outsourcing that fulfills all
aforementioned requirements, such as input/output privacy and
correctness/soundness guarantee has been shown feasible in
theory by Gennaro et al. [9]. However, it is currently not
practical due to its huge computation complexity. Instead
of outsourcing general functions, in the security community,
Atallah et al. explore a list of work [5], [7], [8], [10] for
securely outsourcing specific applications. The customized
solutions are expected to be more efficient than the general
way of constructing the circuits. In [5], they give the first
investigation of secure outsourcing of numerical and scientific
computation.


CONCLUDING REMARKS
In this paper, for the first time, we formalize the problem
of securely outsourcing LP computations in cloud computing,
and provide such a practical mechanism design which fulfills
input/output privacy, cheating resilience, and efficiency.
By explicitly decomposing LP computation outsourcing into
public LP solvers and private data, our mechanism design
is able to explore appropriate security/efficiency tradeoffs
via higher level LP computation than the general circuit
representation. We develop problem transformation techniques
that enable customers to secretly transform the original LP
into some arbitrary one while protecting sensitive input/output
information.