  With the rapid increase in computing, storage and networking resources, data
is not only collected and stored, but also analyzed. This creates a serious
privacy problem which often inhibits the use of this data. In this chapter, we
investigate and resolve the privacy issues in a fundamental optimization
problem -- linear programming (LP) which is formulated by data collected from
different parties. We first consider the case where the objective function and
constraints of the linear programming problem are not partitioned between two
parties where one party privately holds the objective function while the other
party privately holds the constraints. Second, we present a privacy preserving
technique for the case that objective function and constraints are arbitrarily
partitioned between two parties where each party privately holds a share of
objective function and constraints. Finally, we extend the technique for
securely solving two-party arbitrarily partitioned linear programming problems
to a multi-party scenario. In summary, we propose a set of efficient and secure
transformation based techniques that create significant value-added benefits of
being independent of the specific algorithms used for solving the linear
programming problem.
