TY - JOUR

T1 - Secured distributed algorithms without hardness assumptions

AU - Barenboim, Leonid

AU - Levin, Harel

N1 - Publisher Copyright:
© 2022 Elsevier Inc.

PY - 2023/1

Y1 - 2023/1

N2 - We study algorithms in the LOCAL model that produce secured output. 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. As the extensive research in the distributed algorithms field yielded efficient decentralized algorithms, 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. However, 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. We present a novel approach, which 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 labeling and decomposition problems without requiring any hardness assumption, but only a private randomness generator in each vertex.

AB - We study algorithms in the LOCAL model that produce secured output. 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. As the extensive research in the distributed algorithms field yielded efficient decentralized algorithms, 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. However, 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. We present a novel approach, which 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 labeling and decomposition problems without requiring any hardness assumption, but only a private randomness generator in each vertex.

KW - Distributed algorithms

KW - Generic algorithms

KW - Graph coloring

KW - Multi-party computation

KW - Privacy preserving

UR - http://www.scopus.com/inward/record.url?scp=85139347139&partnerID=8YFLogxK

U2 - 10.1016/j.jpdc.2022.09.012

DO - 10.1016/j.jpdc.2022.09.012

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:85139347139

SN - 0743-7315

VL - 171

SP - 130

EP - 140

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

ER -