28-02-2013, 04:44 PM
Formal Secure Outsourcing of Linear Programming in Cloud Computing
Formal Secure.pdf (Size: 386.78 KB / Downloads: 38)
Abstract
Cloud Computing has great potential of providing
robust computational power to the society at reduced cost. It enables
customers with limited computational resources to outsource their
large computation workloads to the cloud, and economically enjoy
the massive computational power, bandwidth, storage, and even
appropriate software that can be shared in a pay-per-use manner. we
must design mechanisms that not only protect sensitive information
by enabling computations with encrypted data, but also protect
customers from malicious behaviors by enabling the validation of the
computation result.
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 arbitrary 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.
INTRODUCTION
LOUD 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. 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 hardware and software
and/or the operational overhead there in.
PROBLEM STATEMENT
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 customer has a large-scale linear programming
problem Φ (to be formally defined later) to be solved.
However, due to the lack of computing resources, like
processing power, memory, and storage etc., he cannot carry
out such expensive computation locally. Thus, the customer
resorts to CS for solving the LP computation and leverages
its computation capacity in a pay-per-use manner. Instead of
directly sending original problem Φ, the customer first uses a
secret K to map Φ into some encrypted version ΦK and
outsources problem ΦK to CS. After receiving the solution of
encrypted problem ΦK , the customer should be able to first
verify the answer via the appended proof Γ. If it’s correct, he
then uses the secret K to map the output into the desired
answer for the original problem Φ.
CONCLUSION
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. We also investigate duality theorem and derive a
set of necessary and sufficient condition for result verification.
Such a cheating resilience design can be bundled in the overall
mechanism with close-to-zero additional overhead. Both
security analysis and experiment results demonstrates the
immediate practicality of the proposed mechanism.