2026-07-22T17:01:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17574 2024-03-06T10:59:57Z ddc:004 open_access

Secure Distributed Network Optimization Against Eavesdroppers Hitron, Yael Parter, Merav Yogev, Eylon congest secure computation network optimization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yael Hitron and Merav Parter and Eylon Yogev 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.71 urn:nbn:de:0030-drops-175746 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.71 eng https://creativecommons.org/licenses/by/4.0/legalcode