Securely Solving Classical Network Flow Problems
(2015) Information Security and Cryptology - ICISC 2014 — ISBN: [978-3-319-15942-3], p. 205-221, published
Files
CORE_RP_3192.pdf
Open Access - Adobe PDF
- 662.47 KB
Details
- Authors
- 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; distribution problems, retailer/supplier selection in multilevel supply chains that want to share routes without disclosing sensible information; amongst others.
- Affiliations
Citations
Aly, A., & Van Vyve, M. (2015). Securely Solving Classical Network Flow Problems. In Lee J. and Kim J. (eds) (ed.), Information Security and Cryptology - ICISC 2014 (p. p. 205-221). Springer. https://doi.org/10.1007/978-3-319-15943-0_13