Securely solving classical network flow problems

Mathieu Van Vyve () and Abdelrahaman Aly ()
Additional contact information
Mathieu Van Vyve: Université catholique de Louvain, CORE, Belgium
Abdelrahaman Aly: Université catholique de Louvain, CORE, Belgium

No 2014057, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We investigate how to solve several classical network flow problems using secure multi-party computation. We consider the shortest path problem, the Minimum Mean Cycle problem and the Minimum Cost Flow problem. To the best of our knowledge, this is the first time the two last problems have been addressed in a general multi-party computation setting. Furthermore, our study highlights the complexity gaps between traditional and secure implementations of the solutions, to later test its implementation. It also explores various trade-offs between performance and security. Additionally it provides protocols that can be used as building blocks to solve complex problems. Applications of our work can be found in: communication networks, routing data from rival company hubs; benchmarking, comparing several IT appliances configurations of rival companies; distribution problems, retailer/supplier selection in multi-level supply chains that want to share routes without disclosing sensible information; amongst others.

Keywords: network flows; multi-party computation; secure collaboration (search for similar items in EconPapers)
JEL-codes: C61 C65 (search for similar items in EconPapers)
Date: 2014-09-30
New Economics Papers: this item is included in nep-cmp and nep-tre
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2014.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2014057

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().