Document Open Access Logo

Secured Distributed Algorithms Without Hardness Assumptions

Authors Leonid Barenboim, Harel Levin

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.32.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Leonid Barenboim
  • Department of Mathematics and Computer Science, The Open University of Israel, Raanana, Israel
Harel Levin
  • Department of Physics, Nuclear Research Center-Negev, Giv'atayim, Israel
  • Department of Mathematics and Computer Science, The Open University of Israel, Raanana, Israel

Cite AsGet BibTex

Leonid Barenboim and Harel Levin. Secured Distributed Algorithms Without Hardness Assumptions. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.OPODIS.2020.32

Abstract

We study algorithms in the distributed message-passing model that produce secured output, for an input graph G. Specifically, each vertex computes its part in the output, the entire output is correct, but each vertex cannot discover the output of other vertices, with a certain probability. This is motivated by high-performance processors that are embedded nowadays in a large variety of devices. Furthermore, sensor networks were established to monitor physical areas for scientific research, smart-cities control, and other purposes. In such situations, it no longer makes sense, and in many cases it is not feasible, to leave the whole processing task to a single computer or even a group of central computers. As the extensive research in the distributed algorithms field yielded efficient decentralized algorithms for many classic problems, the discussion about the security of distributed algorithms was somewhat neglected. Nevertheless, many protocols and algorithms were devised in the research area of secure multi-party computation problem (MPC or SMC). However, the notions and terminology of these protocols are quite different than in classic distributed algorithms. As a consequence, the focus in those protocols was to work for every function f at the expense of increasing the round complexity, or the necessity of several computational assumptions. In this work, we present a novel approach, which rather than turning existing algorithms into secure ones, identifies and develops those algorithms that are inherently secure (which means they do not require any further constructions). This approach yields efficient secure algorithms for various locality problems, such as coloring, network decomposition, forest decomposition, and a variety of additional labeling problems. Remarkably, our approach does not require any hardness assumption, but only a private randomness generator in each vertex. This is in contrast to previously known techniques in this setting that are based on public-key encryption schemes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Security and privacy → Privacy-preserving protocols
  • Mathematics of computing → Graph coloring
  • Mathematics of computing → Graph algorithms
Keywords
  • distributed algorithms
  • privacy preserving
  • graph coloring
  • generic algorithms
  • multi-party computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Baruch Awerbuch, Michael Luby, Andrew V Goldberg, and Serge A Plotkin. Network decomposition and locality in distributed computation. In 30th Annual Symposium on Foundations of Computer Science, pages 364-369. IEEE, 1989. Google Scholar
  2. Leonid Barenboim and Michael Elkin. Sublogarithmic distributed mis algorithm for sparse graphs using nash-williams decomposition. Distributed Computing, 22(5-6):363-379, 2010. Google Scholar
  3. Leonid Barenboim and Michael Elkin. Distributed graph coloring: Fundamentals and recent developments. Synthesis Lectures on Distributed Computing Theory, 4(1):1-171, 2013. Google Scholar
  4. Leonid Barenboim, Michael Elkin, and Fabian Kuhn. Distributed (δ+1)-coloring in linear (in δ) time. SIAM Journal on Computing, 43(1):72-95, 2014. Google Scholar
  5. Leonid Barenboim and Harel Levin. Secured distributed algorithms without hardness assumptions, 2020. URL: http://arxiv.org/abs/2011.07863.
  6. Elette Boyle, Shafi Goldwasser, and Stefano Tessaro. Communication locality in secure multi-party computation. In Theory of Cryptography Conference, pages 356-376. Springer, 2013. Google Scholar
  7. Nishanth Chandran, Juan Garay, and Rafail Ostrovsky. Improved fault tolerance and secure computation on sparse networks. In International Colloquium on Automata, Languages, and Programming, pages 249-260. Springer, 2010. Google Scholar
  8. Richard Cole and Uzi Vishkin. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 206-219. ACM, 1986. Google Scholar
  9. Paul Erdös, Peter Frankl, and Zoltán Füredi. Families of finite sets in which no set is covered by the union ofr others. Israel Journal of Mathematics, 51(1):79-89, 1985. Google Scholar
  10. Juan A Garay and Rafail Ostrovsky. Almost-everywhere secure computation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 307-323. Springer, 2008. Google Scholar
  11. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game. In Proc. of the 19th Symp. on Theory of Computing, pages 218-229, 1987. Google Scholar
  12. Shai Halevi, Yuval Ishai, Abhishek Jain, Ilan Komargodski, Amit Sahai, and Eylon Yogev. Non-interactive multiparty computation without correlated randomness. In International Conference on the Theory and Application of Cryptology and Information Security, pages 181-211. Springer, 2017. Google Scholar
  13. Shai Halevi, Yuval Ishai, Abhishek Jain, Eyal Kushilevitz, and Tal Rabin. Secure multiparty computation with general interaction patterns. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 157-168. ACM, 2016. Google Scholar
  14. Öjvind Johansson. Simple distributed δ+ 1-coloring of graphs. Information Processing Letters, 70(5):229-232, 1999. Google Scholar
  15. Fabian Kuhn. Weak graph colorings: distributed algorithms and applications. In Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, pages 138-144. ACM, 2009. Google Scholar
  16. Nathan Linial. Distributive graph algorithms global solutions from local data. In Foundations of Computer Science, 1987., pages 331-335. IEEE, 1987. Google Scholar
  17. Nathan Linial and Michael Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. Google Scholar
  18. Michael Luby. Removing randomness in parallel computation without a processor penalty. Journal of Computer and System Sciences, 47(2):250-286, 1993. Google Scholar
  19. Alessandro Panconesi and Romeo Rizzi. Some simple distributed algorithms for sparse networks. Distributed computing, 14(2):97-100, 2001. Google Scholar
  20. Merav Parter and Eylon Yogev. Distributed computing made secure: A new cycle cover theorem. arXiv preprint arXiv:1712.01139, 2017. Google Scholar
  21. Merav Parter and Eylon Yogev. Secure distributed computing made (nearly) optimal. In Proc. of 38th Symp. on Principles of Distributed Computing, pages 107-116, 2019. Google Scholar
  22. Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 350-363, 2020. Google Scholar
  23. Andrew C Yao. Protocols for secure computations. In Foundations of Computer Science, 1982. SFCS'08., pages 160-164. IEEE, 1982. Google Scholar
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 Imprint Privacy Contact