Distributed algorithms made secure: a graph theoretic approach

DOI10.1137/1.9781611975482.102MaRDI QIDQ5236286zbMATH OpenOpenAlexFDO

Authors Eylon Yogev, M. Parter

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.01139

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Cryptography (94A60) Distributed algorithms (68W15) Privacy of data (68P27)

Abstract: In the area of distributed graph algorithms a number of network's entities with local views solve some computational task by exchanging messages with their neighbors. Quite unfortunately, an inherent property of most existing distributed algorithms is that throughout the course of their execution, the nodes get to learn not only their own output but rather learn quite a lot on the inputs or outputs of many other entities. This leakage of information might be a major obstacle in settings where the output (or input) of network's individual is a private information. In this paper, we introduce a new framework for emph{secure distributed graph algorithms} and provide the first emph{general compiler} that takes any "natural" non-secure distributed algorithm that runs in $r$ rounds, and turns it into a secure algorithm that runs in $widetildeO(rcdotDcdotpoly(Delta))$ rounds where $Delta$ is the maximum degree in the graph and $D$ is its diameter. The security of the compiled algorithm is information-theoretic but holds only against a semi-honest adversary that controls a single node in the network. This compiler is made possible due to a new combinatorial structure called emph{private neighborhood trees}: a collection of $n$ trees $T(u_1),ldots,T(u_n)$, one for each vertex $u_{i}inV(G)$, such that each tree $T(u_i)$ spans the neighbors of $u_i$ {em without going through $u_i$}. Intuitively, each tree $T(u_i)$ allows all neighbors of $u_i$ to exchange a emph{secret} that is hidden from $u_i$, which is the basic graph infrastructure of the compiler. In a $(d,c)$-private neighborhood trees each tree $T(u_i)$ has depth at most $d$ and each edge $einG$ appears in at most $c$ different trees. We show a construction of private neighborhood trees with $d=widetildeO(DeltacdotD)$ and $c=widetildeO(D)$.

Recommendations

• Almost-Everywhere Secure Computation
• Secure Hypergraphs: Privacy from Partial Broadcast
• Topology-hiding computation on all graphs
• Privacy-Preserving Graph Algorithms in the Semi-honest Model
• Invited talk: Resilient distributed algorithms

Cited in

(5)

• Deciding and verifying network properties locally with few output bits
• Invited talk: Resilient distributed algorithms
• A reduction theorem for randomized distributed algorithms under weak adversaries
• Privacy-Preserving Graph Algorithms in the Semi-honest Model
• Distributed CONGEST Algorithms against Mobile Adversaries

This page was built for publication: Distributed algorithms made secure: a graph theoretic approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236286)