Skip to Main content Skip to Navigation
Conference papers

Efficient Distributed Linear Programming with Limited Disclosure

Abstract : In today’s networked world, resource providers and consumers are distributed globally and locally. However, with resource constraints, optimization is necessary to ensure the best possible usage of such scarce resources. Distributed linear programming (DisLP) problems allow collaborative agents to jointly maximize profits (or minimize costs) with a linear objective function while conforming to several shared as well as local linear constraints. Since each agent’s share of the global constraints and the local constraints generally refer to its private limitations or capacities, serious privacy problems may arise if such information is revealed. While there have been some solutions proposed that allow secure computation of such problems, they typically rely on inefficient protocols with enormous communication cost. In this paper, we present a secure and extremely efficient protocol to solve DisLP problems where constraints are arbitrarily partitioned and no variable is shared between agents. In the entire protocol, each agent learns only a partial solution (about its variables), but learns nothing about the private input/output of other agents, assuming semi-honest behavior. We present a rigorous security proof and communication cost analysis for our protocol and experimentally validate the costs, demonstrating its robustness.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01586592
Contributor : Hal Ifip <>
Submitted on : Wednesday, September 13, 2017 - 8:56:10 AM
Last modification on : Friday, August 9, 2019 - 3:24:28 PM
Long-term archiving on: : Thursday, December 14, 2017 - 12:32:44 PM

File

978-3-642-22348-8_14_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Yuan Hong, Jaideep Vaidya, Haibing Lu. Efficient Distributed Linear Programming with Limited Disclosure. 23th Data and Applications Security (DBSec), Jul 2011, Richmond, VA, United States. pp.170-185, ⟨10.1007/978-3-642-22348-8_14⟩. ⟨hal-01586592⟩

Share

Metrics

Record views

111

Files downloads

248