Must the Communication Graph of MPC Protocols be an Expander?

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10476226" target="_blank" >RIV/00216208:11320/23:10476226 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=juChM2pXTV" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=juChM2pXTV</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00145-023-09460-8" target="_blank" >10.1007/s00145-023-09460-8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Must the Communication Graph of MPC Protocols be an Expander?

Popis výsledku v původním jazyce

Secure multiparty computation (MPC) on incomplete communication networks has been studied within two primary models: (1) where a partial network is fixed a priori, and thus corruptions can occur dependent on its structure, and (2) where edges in the communication graph are determined dynamically as part of the protocol. Whereas a rich literature has succeeded in mapping out the feasibility and limitations of graph structures supporting secure computation in the fixed-graph model (including strong classical lower bounds), these bounds do not apply in the latter dynamic-graph setting, which has recently seen exciting new results, but remains relatively unexplored. In this work, we initiate a similar foundational study of MPC within the dynamic-graph model. As a first step, we investigate the property of graph expansion. All existing protocols (implicitly or explicitly) yield communication graphs which are expanders, but it is not clear whether this is inherent. Our results consist of two types (for constant fraction of corruptions):Upper bounds: We demonstrate secure protocols whose induced communication graphs are expander graphs, within a wide range of settings (computational, information theoretic, with low locality, even with low locality adaptive security), each assuming some form of input-independent setup.notandLower bounds: In the plain model (no setup) with adaptive corruptions, we demonstrate that for certain functionalities, protocol can maintain a non-expanding communication graph against all adversarial strategies. Our lower bound relies only on protocol correctness (not privacy) and requires a surprisingly delicate argument. More generally, we provide a formal framework for analyzing the evolving communication graph of MPC protocols, giving a starting point for studying the relation between secure computation and further, more general graph properties.

Název v anglickém jazyce

Must the Communication Graph of MPC Protocols be an Expander?

Popis výsledku anglicky

Secure multiparty computation (MPC) on incomplete communication networks has been studied within two primary models: (1) where a partial network is fixed a priori, and thus corruptions can occur dependent on its structure, and (2) where edges in the communication graph are determined dynamically as part of the protocol. Whereas a rich literature has succeeded in mapping out the feasibility and limitations of graph structures supporting secure computation in the fixed-graph model (including strong classical lower bounds), these bounds do not apply in the latter dynamic-graph setting, which has recently seen exciting new results, but remains relatively unexplored. In this work, we initiate a similar foundational study of MPC within the dynamic-graph model. As a first step, we investigate the property of graph expansion. All existing protocols (implicitly or explicitly) yield communication graphs which are expanders, but it is not clear whether this is inherent. Our results consist of two types (for constant fraction of corruptions):Upper bounds: We demonstrate secure protocols whose induced communication graphs are expander graphs, within a wide range of settings (computational, information theoretic, with low locality, even with low locality adaptive security), each assuming some form of input-independent setup.notandLower bounds: In the plain model (no setup) with adaptive corruptions, we demonstrate that for certain functionalities, protocol can maintain a non-expanding communication graph against all adversarial strategies. Our lower bound relies only on protocol correctness (not privacy) and requires a surprisingly delicate argument. More generally, we provide a formal framework for analyzing the evolving communication graph of MPC protocols, giving a starting point for studying the relation between secure computation and further, more general graph properties.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA17-09142S" target="_blank" >GA17-09142S: Moderní algoritmy: Nové výzvy komplexních dat</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

JOURNAL OF CRYPTOLOGY

ISSN

0933-2790

e-ISSN

1432-1378

Svazek periodika

36

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

75

Strana od-do

20

Kód UT WoS článku

000985770900001

EID výsledku v databázi Scopus

2-s2.0-85159222466