Search Results

Documents authored by Yogev, Eylon

Document
DOI: 10.4230/LIPIcs.ITCS.2023.71
Secure Distributed Network Optimization Against Eavesdroppers

Authors: Yael Hitron, Merav Parter, and Eylon Yogev

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{hitron_et_al:LIPIcs.ITCS.2023.71,
  author =	{Hitron, Yael and Parter, Merav and Yogev, Eylon},
  title =	{{Secure Distributed Network Optimization Against Eavesdroppers}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{71:1--71:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.71},
  URN =		{urn:nbn:de:0030-drops-175746},
  doi =		{10.4230/LIPIcs.ITCS.2023.71},
  annote =	{Keywords: congest, secure computation, network optimization}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.27
Broadcast CONGEST Algorithms Against Eavesdroppers

Authors: Yael Hitron, Merav Parter, and Eylon Yogev

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
An eavesdropper is a passive adversary that aims at extracting private information on the input and output values of the network’s participants, by listening to the traffic exchanged over a subset of edges in the graph. We consider secure congest algorithms for the basic broadcast task, in the presence of eavesdropper (edge) adversaries. For D-diameter n-vertex graphs with edge connectivity Θ(f), we present f-secure broadcast algorithms that run in Õ(D+√{f n}) rounds. These algorithms transmit some broadcast message m^* to all the vertices in the graph, in a way that is information-theoretically secure against an eavesdropper controlling any subset of at most f edges in the graph. While our algorithms are heavily based on network coding (secret sharing), we also show that this is essential. For the basic problem of secure unicast we demonstrate a network coding gap of Ω(n) rounds. In the presence of vertex adversaries, known as semi-honest, we introduce the Forbidden-Set Broadcast problem: In this problem, the vertices of the graph are partitioned into two sets, trusted and untrusted, denoted as R, F ⊆ V, respectively, such that G[R] is connected. It is then desired to exchange a secret message m^* between all the trusted vertices while leaking no information to the untrusted set F. Our algorithm works in Õ(D+√|R|) rounds and its security guarantees hold even when all the untrusted vertices F are controlled by a (centralized) adversary.
Cite as

Yael Hitron, Merav Parter, and Eylon Yogev. Broadcast CONGEST Algorithms Against Eavesdroppers. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hitron_et_al:LIPIcs.DISC.2022.27,
  author =	{Hitron, Yael and Parter, Merav and Yogev, Eylon},
  title =	{{Broadcast CONGEST Algorithms Against Eavesdroppers}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.27},
  URN =		{urn:nbn:de:0030-drops-172186},
  doi =		{10.4230/LIPIcs.DISC.2022.27},
  annote =	{Keywords: congest, edge-connectivity, secret sharing}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.24
Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs

Authors: Gal Arnon, Alessandro Chiesa, and Eylon Yogev

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
Hardness of approximation aims to establish lower bounds on the approximability of optimization problems in NP and beyond. We continue the study of hardness of approximation for problems beyond NP, specifically for stochastic constraint satisfaction problems (SCSPs). An SCSP with 𝗄 alternations is a list of constraints over variables grouped into 2𝗄 blocks, where each constraint has constant arity. An assignment to the SCSP is defined by two players who alternate in setting values to a designated block of variables, with one player choosing their assignments uniformly at random and the other player trying to maximize the number of satisfied constraints. In this paper, we establish hardness of approximation for SCSPs based on interactive proofs. For 𝗄 ≤ O(log n), we prove that it is AM[𝗄]-hard to approximate, to within a constant, the value of SCSPs with 𝗄 alternations and constant arity. Before, this was known only for 𝗄 = O(1). Furthermore, we introduce a natural class of 𝗄-round interactive proofs, denoted IR[𝗄] (for interactive reducibility), and show that several protocols (e.g., the sumcheck protocol) are in IR[𝗄]. Using this notion, we extend our inapproximability to all values of 𝗄: we show that for every 𝗄, approximating an SCSP instance with O(𝗄) alternations and constant arity is IR[𝗄]-hard. While hardness of approximation for CSPs is achieved by constructing suitable PCPs, our results for SCSPs are achieved by constructing suitable IOPs (interactive oracle proofs). We show that every language in AM[𝗄 ≤ O(log n)] or in IR[𝗄] has an O(𝗄)-round IOP whose verifier has constant query complexity (regardless of the number of rounds 𝗄). In particular, we derive a "sumcheck protocol" whose verifier reads O(1) bits from the entire interaction transcript.
Cite as

Gal Arnon, Alessandro Chiesa, and Eylon Yogev. Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{arnon_et_al:LIPIcs.CCC.2022.24,
  author =	{Arnon, Gal and Chiesa, Alessandro and Yogev, Eylon},
  title =	{{Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.24},
  URN =		{urn:nbn:de:0030-drops-165867},
  doi =		{10.4230/LIPIcs.CCC.2022.24},
  annote =	{Keywords: hardness of approximation, interactive oracle proofs, stochastic satisfaction problems}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.89
Optimal Short Cycle Decomposition in Almost Linear Time

Authors: Merav Parter and Eylon Yogev

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Short cycle decomposition is an edge partitioning of an unweighted graph into edge-disjoint short cycles, plus a small number of extra edges not in any cycle. This notion was introduced by Chu et al. [FOCS'18] as a fundamental tool for graph sparsification and sketching. Clearly, it is most desirable to have a fast algorithm for partitioning the edges into as short as possible cycles, while omitting few edges. The most naïve procedure for such decomposition runs in time O(m * n) and partitions the edges into O(log n)-length edge-disjoint cycles plus at most 2n edges. Chu et al. improved the running time considerably to m^{1+o(1)}, while increasing both the length of the cycles and the number of omitted edges by a factor of n^{o(1)}. Even more recently, Liu-Sachdeva-Yu [SODA'19] showed that for every constant delta in (0,1] there is an O(m * n^{delta})-time algorithm that provides, w.h.p., cycles of length O(log n)^{1/delta} and O(n) extra edges. In this paper, we significantly improve upon these bounds. We first show an m^{1+o(1)}-time deterministic algorithm for computing nearly optimal cycle decomposition, i.e., with cycle length O(log^2 n) and an extra subset of O(n log n) edges not in any cycle. This algorithm is based on a reduction to low-congestion cycle covers, introduced by the authors in [SODA'19]. We also provide a simple deterministic algorithm that computes edge-disjoint cycles of length 2^{1/epsilon} with n^{1+epsilon}* 2^{1/epsilon} extra edges, for every epsilon in (0,1]. Combining this with Liu-Sachdeva-Yu [SODA'19] gives a linear time randomized algorithm for computing cycles of length poly(log n) and O(n) extra edges, for every n-vertex graphs with n^{1+1/delta} edges for some constant delta. These decomposition algorithms lead to improvements in all the algorithmic applications of Chu et al. as well as to new distributed constructions.
Cite as

Merav Parter and Eylon Yogev. Optimal Short Cycle Decomposition in Almost Linear Time. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 89:1-89:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{parter_et_al:LIPIcs.ICALP.2019.89,
  author =	{Parter, Merav and Yogev, Eylon},
  title =	{{Optimal Short Cycle Decomposition in Almost Linear Time}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{89:1--89:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.89},
  URN =		{urn:nbn:de:0030-drops-106653},
  doi =		{10.4230/LIPIcs.ICALP.2019.89},
  annote =	{Keywords: Cycle decomposition, low-congestion cycle cover, graph sparsification}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.40
Congested Clique Algorithms for Graph Spanners

Authors: Merav Parter and Eylon Yogev

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
Graph spanners are sparse subgraphs that faithfully preserve the distances in the original graph up to small stretch. Spanner have been studied extensively as they have a wide range of applications ranging from distance oracles, labeling schemes and routing to solving linear systems and spectral sparsification. A k-spanner maintains pairwise distances up to multiplicative factor of k. It is a folklore that for every n-vertex graph G, one can construct a (2k-1) spanner with O(n^{1+1/k}) edges. In a distributed setting, such spanners can be constructed in the standard CONGEST model using O(k^2) rounds, when randomization is allowed. In this work, we consider spanner constructions in the congested clique model, and show: - a randomized construction of a (2k-1)-spanner with O~(n^{1+1/k}) edges in O(log k) rounds. The previous best algorithm runs in O(k) rounds; - a deterministic construction of a (2k-1)-spanner with O~(n^{1+1/k}) edges in O(log k +(log log n)^3) rounds. The previous best algorithm runs in O(k log n) rounds. This improvement is achieved by a new derandomization theorem for hitting sets which might be of independent interest; - a deterministic construction of a O(k)-spanner with O(k * n^{1+1/k}) edges in O(log k) rounds.
Cite as

Merav Parter and Eylon Yogev. Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{parter_et_al:LIPIcs.DISC.2018.40,
  author =	{Parter, Merav and Yogev, Eylon},
  title =	{{Congested Clique Algorithms for Graph Spanners}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.40},
  URN =		{urn:nbn:de:0030-drops-98298},
  doi =		{10.4230/LIPIcs.DISC.2018.40},
  annote =	{Keywords: Distributed Graph Algorithms, Spanner, Congested Clique}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.60
The Journey from NP to TFNP Hardness

Authors: Pavel Hubácek, Moni Naor, and Eylon Yogev

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one of the main research objectives in the context of TFNP is to search for efficient algorithms for its subclasses, and at the same time proving hardness results where efficient algorithms cannot exist. Currently, no problem in TFNP is known to be hard under assumptions such as NP hardness, the existence of one-way functions, or even public-key cryptography. The only known hardness results are based on less general assumptions such as the existence of collision-resistant hash functions, one-way permutations less established cryptographic primitives (e.g. program obfuscation or functional encryption). Several works explained this status by showing various barriers to proving hardness of TFNP. In particular, it has been shown that hardness of TFNP hardness cannot be based on worst-case NP hardness, unless NP=coNP. Therefore, we ask the following question: What is the weakest assumption sufficient for showing hardness in TFNP? In this work, we answer this question and show that hard-on-average TFNP problems can be based on the weak assumption that there exists a hard-on-average language in NP. In particular, this includes the assumption of the existence of one-way functions. In terms of techniques, we show an interesting interplay between problems in TFNP, derandomization techniques, and zero-knowledge proofs.
Cite as

Pavel Hubácek, Moni Naor, and Eylon Yogev. The Journey from NP to TFNP Hardness. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 60:1-60:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hubacek_et_al:LIPIcs.ITCS.2017.60,
  author =	{Hub\'{a}cek, Pavel and Naor, Moni and Yogev, Eylon},
  title =	{{The Journey from NP to TFNP Hardness}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{60:1--60:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.60},
  URN =		{urn:nbn:de:0030-drops-81627},
  doi =		{10.4230/LIPIcs.ITCS.2017.60},
  annote =	{Keywords: TFNP, derandomization, one-way functions, average-case hardness}
}
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 About DROPS Imprint Privacy Contact