Document Open Access Logo

Secure Distributed Network Optimization Against Eavesdroppers

Authors Yael Hitron, Merav Parter, Eylon Yogev

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.71.pdf
  • Filesize: 0.78 MB
  • 20 pages

Document Identifiers

Author Details

Yael Hitron
  • Weizmann Institute of Science, Rehovot, Israel
Merav Parter
  • Weizmann Institute of Science, Rehovot, Israel
Eylon Yogev
  • Bar-Ilan University, Ramat-Gan, Israel

Funding

  • Parter, Merav: This project is funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 949083).
  • Yogev, Eylon: Supported in part by a grant from the Israel Science Foundation (no. 2893/22), and by an Alon Young Faculty Fellowship.

Cite AsGet BibTex

Yael Hitron, Merav Parter, and Eylon Yogev. Secure Distributed Network Optimization Against Eavesdroppers. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 71:1-71:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.71

Abstract

We present a new algorithmic framework for distributed network optimization in the presence of eavesdropper adversaries, also known as passive wiretappers. In this setting, the adversary is listening to the traffic exchanged over a fixed set of edges in the graph, trying to extract information on the private input and output of the vertices. A distributed algorithm is denoted as f-secure, if it guarantees that the adversary learns nothing on the input and output for the vertices, provided that it controls at most f graph edges. Recent work has presented general simulation results for f-secure algorithms, with a round overhead of D^Θ(f), where D is the diameter of the graph. In this paper, we present a completely different white-box, and yet quite general, approach for obtaining f-secure algorithms for fundamental network optimization tasks. Specifically, for n-vertex D-diameter graphs with (unweighted) edge-connectivity Ω(f), there are f-secure congest algorithms for computing MST, partwise aggregation, and (1+ε) (weighted) minimum cut approximation, within Õ(D+f √n) congest rounds, hence nearly tight for f = Õ(1). Our algorithms are based on designing a secure algorithmic-toolkit that leverages the special structure of congest algorithms for global optimization graph problems. One of these tools is a general secure compiler that simulates light-weight distributed algorithms in a congestion-sensitive manner. We believe that these tools set the ground for designing additional secure solutions in the congest model and beyond.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • congest
  • secure computation
  • network optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis. Brief announcement: Almost universally optimal distributed laplacian solver. In Alessia Milani and Philipp Woelfel, editors, PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25-29, 2022, pages 372-374. ACM, 2022. Google Scholar
  2. Ning Cai and Raymond W Yeung. Secure network coding on a wiretap network. IEEE Transactions on Information Theory, 57(1):424-435, 2010. Google Scholar
  3. Justin Y. Chen, Shyam Narayanan, and Yinzhan Xu. All-pairs shortest path distances with differential privacy: Improved algorithms for bounded and unbounded weights. CoRR, abs/2204.02335, 2022. Google Scholar
  4. Danny Dolev, Cynthia Dwork, Orli Waarts, and Moti Yung. Perfectly secure message transmission. In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I, pages 36-45. IEEE Computer Society, 1990. Google Scholar
  5. Michael Elkin. A simple deterministic distributed MST algorithm with near-optimal time and message complexities. J. ACM, 67(2):13:1-13:15, 2020. URL: https://doi.org/10.1145/3380546.
  6. Jon Feldman, Tal Malkin, Cliff Stein, and Rocco A Servedio. On the capacity of secure network coding. In Proc. 42nd Annual Allerton Conference on Communication, Control, and Computing, pages 63-68. Cambridge University Press, 2004. Google Scholar
  7. Juan A. Garay, Shay Kutten, and David Peleg. A sub-linear time distributed algorithm for minimum-weight spanning trees (extended abstract). In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 659-668. IEEE Computer Society, 1993. URL: https://doi.org/10.1109/SFCS.1993.366821.
  8. Mohsen Ghaffari. Near-optimal scheduling of distributed algorithms. In Chryssis Georgiou and Paul G. Spirakis, editors, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21-23, 2015, pages 3-12. ACM, 2015. Google Scholar
  9. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks II: low-congestion shortcuts, mst, and min-cut. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 202-219. SIAM, 2016. Google Scholar
  10. Mohsen Ghaffari and Bernhard Haeupler. Low-congestion shortcuts for graphs excluding dense minors. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC '21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 213-221. ACM, 2021. Google Scholar
  11. Mohsen Ghaffari and Goran Zuzic. Universally-optimal distributed exact min-cut. In Alessia Milani and Philipp Woelfel, editors, PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25-29, 2022, pages 281-291. ACM, 2022. Google Scholar
  12. Oded Goldreich. The Foundations of Cryptography - Volume 2: Basic Applications. Cambridge University Press, 2004. URL: https://doi.org/10.1017/CBO9780511721656.
  13. Bernhard Haeupler. The quest for universally-optimal distributed algorithms (invited talk). In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 1:1-1:1. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  14. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Near-optimal low-congestion shortcuts on bounded parameter graphs. In Cyril Gavoille and David Ilcinkas, editors, Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings, volume 9888 of Lecture Notes in Computer Science, pages 158-172. Springer, 2016. Google Scholar
  15. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Low-congestion shortcuts without embedding. Distributed Comput., 34(1):79-90, 2021. Google Scholar
  16. Bernhard Haeupler, David Wajc, and Goran Zuzic. Universally-optimal distributed algorithms for known topologies. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1166-1179. ACM, 2021. Google Scholar
  17. Yael Hitron and Merav Parter. General CONGEST compilers against adversarial edges. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 24:1-24:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  18. Yael Hitron, Merav Parter, and Eylon Yogev. Broadcast CONGEST algorithms against eavesdroppers. In Christian Scheideler, editor, 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA, volume 246 of LIPIcs, pages 27:1-27:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  19. Taisuke Izumi, Naoki Kitamura, Takamasa Naruse, and Gregory Schwartzman. Fully polynomial-time distributed computation in low-treewidth graphs. In Kunal Agrawal and I-Ting Angelina Lee, editors, SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11-14, 2022, pages 11-22. ACM, 2022. Google Scholar
  20. Kamal Jain. Security based on network topology against the wiretapping attack. IEEE Wirel. Commun., 11(1):68-71, 2004. Google Scholar
  21. Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography, Second Edition. CRC Press, 2014. Google Scholar
  22. Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, and Taisuke Izumi. Low-congestion shortcut and graph parameters. Distributed Comput., 34(5):349-365, 2021. Google Scholar
  23. Shimon Kogan and Merav Parter. Low-congestion shortcuts in constant diameter graphs. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC '21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 203-211. ACM, 2021. Google Scholar
  24. Frank Thomson Leighton, Bruce M. Maggs, and Satish Rao. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Comb., 14(2):167-186, 1994. Google Scholar
  25. Xiaoye Li, Jing Yang, Zhenlong Sun, and Jianpei Zhang. Differential privacy for edge weights in social networks. Secur. Commun. Networks, 2017:4267921:1-4267921:10, 2017. Google Scholar
  26. Jaroslav Nešetřil, Eva Milková, and Helena Nešetřilová. Otakar borůvka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Mathematics, 233:3-36, April 2001. URL: https://doi.org/10.1016/S0012-365X(00)00224-7.
  27. Merav Parter and Eylon Yogev. Distributed algorithms made secure: A graph theoretic approach. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1693-1710. SIAM, 2019. Google Scholar
  28. Merav Parter and Eylon Yogev. Low congestion cycle covers and their applications. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1673-1692, 2019. Google Scholar
  29. Merav Parter and Eylon Yogev. Secure distributed computing made (nearly) optimal. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 107-116, 2019. Google Scholar
  30. David Peleg. Time-optimal leader election in general networks. J. Parallel Distributed Comput., 8(1):96-99, 1990. Google Scholar
  31. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, USA, 2000. Google Scholar
  32. David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed MST construction. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pages 253-261. IEEE Computer Society, 1999. Google Scholar
  33. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 363-372. ACM, 2011. Google Scholar
  34. Adam Sealfon. Shortest paths and distances with differential privacy. In Tova Milo and Wang-Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 29-41. ACM, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact