Paper 2017/1182
Distributed Algorithms Made Secure: A Graph Theoretic Approach
Merav Parter and Eylon Yogev
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 (e.g., distributed networks of selfish agents, decentralized digital currency such as Bitcoin). While being quite an unfamiliar notion in the classical distributed setting, the notion of secure multiparty computation (MPC) is one of the main themes in the Cryptographic community. The existing secure MPC protocols do not quite fit the framework of classical distributed models in which only messages of bounded size are sent on graph edges in each round. 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" nonsecure distributed algorithm that runs in $r$ rounds, and turns it into a secure algorithm that runs in $\widetilde{O}(r \cdot D \cdot poly(\Delta))$ rounds where $\Delta$ is the maximum degree in the graph and $D$ is its diameter. A "natural" distributed algorithm is one where the local computation at each node can be performed in polynomial time. An interesting advantage of our approach is that it allows one to decouple between the price of locality and the price of \emph{security} of a given graph function $f$. The security of the compiled algorithm is informationtheoretic but holds only against a semihonest 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 \in V(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 $e \in G$ appears in at most $c$ different trees. We show a construction of private neighborhood trees with $d=\widetilde{O}(\Delta \cdot D)$ and $c=\widetilde{O}(D)$, both these bounds are \emph{existentially} optimal.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 MPCdistributed algorithm
 Contact author(s)
 eylony @ gmail com
 History
 20181228: last of 2 revisions
 20171208: received
 See all versions
 Short URL
 https://ia.cr/2017/1182
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/1182, author = {Merav Parter and Eylon Yogev}, title = {Distributed Algorithms Made Secure: A Graph Theoretic Approach}, howpublished = {Cryptology ePrint Archive, Paper 2017/1182}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/1182}}, url = {https://eprint.iacr.org/2017/1182} }