Secure and Practical Outsourcing of Linear Programming in Cloud Computing
Secure and Practical Outsourcing of
Linear
Programming
in Cloud Computing
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. Despite the tremendous
benefits, security is the primary obstacle that prevents the wide adoption of
this promising computing model, especially for customers when their
confidential data are consumed and produced during the computation. Treating
the cloud as an intrinsically insecure computing platform from the viewpoint of
the cloud customers, 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. 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 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.
Existing
System:
We first formulate private
data owned by the customer for LP problem as a set of matrices and vectors.
This higher level representation allows us to apply a set of efficient privacy-preserving
problem transformation techniques, including matrix multiplication and affine
mapping, to transform the original LP problem into some arbitrary one while
protecting the sensitive input/output information. One crucial benefit of this
higher level problem transformation method is that existing algorithms and
tools for LP solvers can be directly reused by the cloud server. Although the
generic mechanism defined at circuit level, can even allow the customer to hide
the fact that the outsourced computation is LP, we believe imposing this more
stringent security measure than necessary would greatly affect the efficiency.
To validate the computation result, we utilize the fact that the result is from
cloud server solving the transformed LP problem.
Disadvantage:
We
consider a computation outsourcing architecture involving two different entities,
as illustrated. 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.
Proposed
System:
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.
Advantage:
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.
Hardware Requirements
·
System : Pentium
IV 2.4 GHz.
·
Hard Disk : 40 GB.
·
Floppy Drive :
1.44 Mb.
·
Monitor : 15
VGA Color.
·
Mouse : Logitech.
·
Ram : 512 MB.
Software Requirements
·
Operating System : Windows
xp , Linux
·
Language : Java1.4 or more
·
Technology :
Swing, AWT
·
Back End : NO Data Bases
Module Description
1. Mechanism Design Framework
2.
Basic Techniques
3.
Enhanced Techniques via Affine
Mapping
4.
Result Verification
Mechanism Design Framework:
We propose to apply problem transformation for mechanism
design. The general framework is adopted from a generic approach, while our
instantiation is completely different and novel. In this framework, the process
on cloud server can be represented by algorithm ProofGen and the process on
customer can be organized into three algorithms (KeyGen, ProbEnc, ResultDec).
These four algorithms are summarized below and will be instantiated later.
• KeyGen(1k) → {K}. This
is a randomized key generation algorithm which takes a system security
parameter k, and returns a
secret key K that is used later
by customer to encrypt the target LP problem.
• ProbEnc(K,_) → {_K}. This algorithm encrypts the input tuple _ into _K with the secret key K.
According to problem transformation, the encrypted input _K has the same form as _, and thus defines the problem to be solved
in the cloud.
• ProofGen(_K) → {(y, ��)}. This algorithm augments a generic solver that solves the problem _K
to produce both the output y and a proof ��. The
output y later
decrypts to x, and �� is used later by
the customer to verify the correctness of y or x.
• ResultDec(K,_, y, ��) → {x,⊥}. This algorithm
may choose to verify either y or
x via the proof ��. In any
case, a correct output x
is produced by decrypting y using the secret K. The algorithm outputs ⊥ when the
validation fails, indicating the cloud server was not performing the
computation faithfully.
Basic Techniques
Before
presenting the details of our proposed mechanism, we study in this subsection a
few basic techniques and show that the input encryption based on these
techniques along may result in an unsatisfactory mechanism. However, the
analysis will give insights on how a stronger mechanism should be designed.
Note that to simplify the presentation, we assume that the cloud server
honestly performs the computation, and defer the discussion on soundness to a
later section.
1) Hiding equality
constraints (A,
b): First of all, a randomly generated m × m non-singular matrix Q can
be part of the secret key K. The customer can apply the matrix to Eq. (2) for
the following constraints transformation, Ax = b ⇒ A′x = b′
where A′ = QA and b′ = Qb.
Enhanced Techniques via Affine Mapping
To enhance the
security strength of LP outsourcing, we must be able to change the feasible
region of original LP and at the same time hide output vector x during the
problem input encryption. We propose to encrypt the feasible region of _ by
applying an affine mapping on the decision variables x. This design principle
is based on the following observation: ideally, if we can arbitrarily transform
the feasible area of problem _ from one vector space to another and keep the
mapping
function as the secret key, there is no way for cloud server
to learn the original feasible area information. Further, such a linear mapping
also serves the important purpose of output hiding.
Result Verification
Till now, we have been assuming the server is honestly performing the
computation, while being interested learning information of original LP
problem. However, such semihonest model is not strong enough to capture the
adversary behaviors in the real world. In many cases, especially when the
computation on the cloud requires a huge amount of computing resources, there
exists strong financial incentives for the cloud server to be “lazy”. They
might either be not willing to commit service-level-agreed computing resources
to save cost, or even be malicious just to sabotage any following up
computation at the customers. Since the cloud server promises to solve the LP
problem _K = (A′,B′, b′, c′), we propose to solve the result verification
problem by designing a method to verify the correctness of the solution y of _K.
The soundness condition would be a corollary thereafter when we present the
whole mechanism in the next section. Note that
in our design, the workload required for customers on the
result verification is substantially cheaper than solving the LP problem on
their own, which ensures the great computation savings for secure LP
outsourcing.
The LP problem does not necessarily have an optimal
solution. There are three cases as follows.
• Normal: There is an optimal solution with finite
objective value.
• Infeasible: The constraints cannot be all satisfied
at the same time.
• Unbounded: For the standard form in Eq. (1), the
objective function can be arbitrarily small while the constraints are all
satisfied.
Categories:
0 comments:
Post a Comment