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.
Type de document :
Communication dans un congrès
Yingjiu Li. 23th Data and Applications Security (DBSec), Jul 2011, Richmond, VA, United States. Springer, Lecture Notes in Computer Science, LNCS-6818, pp.170-185, 2011, Data and Applications Security and Privacy XXV. 〈10.1007/978-3-642-22348-8_14〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01586592
Contributeur : Hal Ifip <>
Soumis le : mercredi 13 septembre 2017 - 08:56:10
Dernière modification le : mercredi 13 septembre 2017 - 14:28:18
Document(s) archivé(s) le : jeudi 14 décembre 2017 - 12:32:44

Fichier

978-3-642-22348-8_14_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Yuan Hong, Jaideep Vaidya, Haibing Lu. Efficient Distributed Linear Programming with Limited Disclosure. Yingjiu Li. 23th Data and Applications Security (DBSec), Jul 2011, Richmond, VA, United States. Springer, Lecture Notes in Computer Science, LNCS-6818, pp.170-185, 2011, Data and Applications Security and Privacy XXV. 〈10.1007/978-3-642-22348-8_14〉. 〈hal-01586592〉

Partager

Métriques

Consultations de la notice

20

Téléchargements de fichiers

6