Efficient Distributed Linear Programming with Limited Disclosure - Data and Applications Security and Privacy XXV Access content directly
Conference Papers Year : 2011

Efficient Distributed Linear Programming with Limited Disclosure

Yuan Hong
  • Function : Author
  • PersonId : 1004168
Jaideep Vaidya
  • Function : Author
  • PersonId : 986164
Haibing Lu
  • Function : Author
  • PersonId : 1016209


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.
Fichier principal
Vignette du fichier
978-3-642-22348-8_14_Chapter.pdf (292.04 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01586592 , version 1 (13-09-2017)





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⟩
75 View
61 Download



Gmail Facebook X LinkedIn More