Must the Communication Graph of MPC Protocols be an Expander?
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Must the Communication Graph of MPC Protocols be an Expander?
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA17-09142S" target="_blank" >GA17-09142S: Modern algorithms: New challenges of complex data sets</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
JOURNAL OF CRYPTOLOGY
ISSN
0933-2790
e-ISSN
1432-1378
Volume of the periodical
36
Issue of the periodical within the volume
3
Country of publishing house
US - UNITED STATES
Number of pages
75
Pages from-to
20
UT code for WoS article
000985770900001
EID of the result in the Scopus database
2-s2.0-85159222466