Abstract-The growth of the Internet has created tremendous the negotiations, of actually exchanging the resources, etc.). opportunities for online collaborations. These often involve col-Although there are so many situations where collaboration laborative optimizations where the two parties are, for example, is mutually advantageous, it often does not occur and its jointly minimizing costs without violating their own particular . . techniques and protocols that carry this out without either excess of bandwidth, inventory, production capacity, etc, can party revealing to the other anything about their own private be damaging to the company's future negotiating position (or inputs to the optimization (other than, unavoidably, what can even to its stock price and the survival of its management). The be deduced from the collaboratively computed optimal solution). formulation of such online collaboration often leads to a linearFor example, two organizations who jointly invest in a project programming formulation, and the task is then to solve this may want to minimize some linear objective function while satp isfying both organizations' private and confidential constraints. problem so that both parties achieve their benefits yet without Constraints are usually private when they reveal too much about revealing their private/proprietary data. Consider the following the organizations' financial health, its future business strategy, example where there are n resources that are shared by Alice etc. Linear programming problems have been widely studied in and Bob according to some initial partition, each of the two the literature. However, the existing solutions (e.g., the simplex parties has a private valuation function for each resource, and method) do not extend to the above-mentioned framework in . g which the linear constraints are shared by the two parties, who the goal is to re-partiton the resources so as to achieve the do not want to disclose their own to the other party. In this paper, optimal win-win outcome. we give an efficient protocol for solving linear programming Example 1: Alice and Bob share n resources. We use pi to problems in the honest-but-curious model, such that neither denote Alice's fraction of resource i, hence 1 -pi is Bob's party reveals anything about their private input to the other * --party (other than what can be inferred from the result). The inta fon. Le a' bi's privatemalion so urce amount of communication and computation done by our protocol i, bi be Bob's; the al's and bi's are normalized so that Zi a= is proportional to the time complexity of the simplex method, a Ei bi = K where K is fixed (so a party cannot increase widely used linear programming algorithm. We also provide a its valuation of a resource without decreasing its valuation practical solution that prevents certain malicious behavior of the of another resource). Alice and Bob want to re-allocate their
Li and Atallah REF addressed the collaborative linear programming problem between two parties where the objective function and constraints can be arbitrarily partitioned, and proposed a secure simplex method for such problem based on homomorphic encryption and scrambled circuit evaluation.
Secure and Private Collaborative Linear Programming
2006 International Conference on Collaborative Computing: Networking, Applications and Worksharing
2006 International Conference on Collaborative Computing: Networking, Applications and Worksharing
Computer Science