Securely Solving Classical Network Flow Problems

详细信息    查看全文

• 作者：Abdelrahaman Aly (15)
  Mathieu Van Vyve (15)
  
  15. Universit茅 catholique de Louvain ; CORE ; Voie du Roman Pays 34 ; 1348 ; Louvain-la-Neuve ; Belgium
  
• 关键词：Network Flows ; Multi ; party computation ; Secure collaboration
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：8949
• 期：1
• 页码：205-221
• 全文大小：289 KB
• 参考文献：1. Yao, A.C.C.: Protocols for secure computations (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, pp. 160鈥?64. IEEE (1982)
  2. Shamir, A (1979) How to share a secret. Commun. ACM 22: pp. 612-613 8.359176" target="_blank" title="It opens in new window">CrossRef
  3. Paillier, P Public-Key cryptosystems based on composite degree residuosity classes. In: Stern, J eds. (1999) Advances in Cryptology - EUROCRYPT 鈥?9. Springer, Heidelbergpp. 223 8910-X_16" target="_blank" title="It opens in new window">CrossRef
  4. Ahuja, RK, Magnanti, TL, Orlin, JB (1993) Network Flows: Theory, Algorithms, and Applications. Prentice-Hall Inc., Upper Saddle River
  5. Aly, A, Cuvelier, E, Mawet, S, Pereira, O, Vyve, M Securely solving simple combinatorial graph problems. In: Sadeghi, A-R eds. (2013) Financial Cryptography and Data Security. Springer, Heidelberg, pp. 239-257 8-3-642-39884-1_21" target="_blank" title="It opens in new window">CrossRef
  6. Launchbury, J., Diatchki, I.S., DuBuisson, T., Adams-Moran, A.:Efficient lookup-table protocol in secure multiparty computation. In: Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming, ICFP 2012, pp. 189鈥?00. ACM, New York (2012)
  7. Brickell, J, Shmatikov, V Privacy-preserving graph algorithms in the semi-honest model. In: Roy, B eds. (2005) Advances in Cryptology - ASIACRYPT 2005. Springer, Heidelberg, pp. 236-252 CrossRef
  8. Blanton, M., Steele, A., Alisagari, M.: Data-oblivious graph algorithms for secure computation and outsourcing. In: Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security, ASIA CCS 2013, pp. 207鈥?18. ACM, New York (2013)
  9. Wang, X., Nayak, K., Liu, C., Shi, E., Stefanov, E., Huang, Y.: Oblivious data structures. Cryptology ePrint Archive, Report 2014/185 (2014). http://eprint.iacr.org/
  10. Lu, S., Ostrovsky, R.: Distributed oblivious ram for secure two-party computation. Cryptology ePrint Archive, Report 2011/384 (2011). http://eprint.iacr.org/
  11. Gordon, S.D., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., Vahlis, Y.: Secure two-party computation in sublinear (amortized) time. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS 2012, pp. 513鈥?24. ACM, New York (2012)
  12. Liu, C., Huang, Y., Shi, E., Katz, J., Hicks, M.: Automating efficient ram-model secure computation. In: 35th IEEE Symposium on Security and Privacy (2014)
  13. Keller, M., Scholl, P.: Efficient, oblivious data structures for mpc. IACR Cryptology ePrint Archive, 137 (2014)
  14. Maurer, U (2006) Secure multi-party computation made simple. Discrete Appl. Math. 154: pp. 370-381 CrossRef
  15. Damg氓rd, IB, Nielsen, JB Universally composable efficient multiparty computation from threshold homomorphic encryption. In: Boneh, D eds. (2003) Advances in Cryptology - CRYPTO 2003. Springer, Heidelberg, pp. 247-264 8-3-540-45146-4_15" target="_blank" title="It opens in new window">CrossRef
  16. Goldberg, AV, Tarjan, RE (1989) Finding minimum-cost circulations by canceling negative cycles. J. ACM 4: pp. 873-886 8" target="_blank" title="It opens in new window">CrossRef
  17. Karp, RM (1978) A characterization of the minimum cycle mean in a digraph. Discrete Math. 3: pp. 309-311 8)90078-X" target="_blank" title="It opens in new window">CrossRef
  18. Klein, M (1967) A primal method for minimal cost flows with applications to the assignment and transportation problems. Manag. Sci. 14: pp. 205-220 87/mnsc.14.3.205" target="_blank" title="It opens in new window">CrossRef
  19. Busacker, R, Saaty, T (1965) Finite Graphs and Networks: An Introduction with Applications. McGraw-Hill, New York
  20. Geisler, M.: Cryptographic protocols: theory and implementation. Ph.D. thesis, Aarhus University Denmark, Department of Computer Science (2010)
  21. Toft, T.: Primitives and applications for multi-party computation. Ph.D. thesis, Department of Computer Science, Aarhus University (2007)
  
• 作者单位：Information Security and Cryptology - ICISC 2014
• 丛书名：978-3-319-15942-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

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 multi-level supply chains that want to share routes without disclosing sensible information; amongst others.