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 multi-party 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" non-secure distributed algorithm that runs in
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- MPCdistributed algorithm
- Contact author(s)
- eylony @ gmail com
- History
- 2018-12-28: last of 2 revisions
- 2017-12-08: 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}, url = {https://eprint.iacr.org/2017/1182} }