Must the Communication Graph of MPC Protocols be an Expander?

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10387368" target="_blank" >RIV/00216208:11320/18:10387368 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1007/978-3-319-96878-0_9" target="_blank" >https://doi.org/10.1007/978-3-319-96878-0_9</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-96878-0_9" target="_blank" >10.1007/978-3-319-96878-0_9</a>

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: Upper bounds: We demonstrate secure protocols whose induced communication graphs are not expanders, within a wide range of settings (computational, information theoretic, with low locality, and adaptive security), each assuming some form of input-independent setup. Lower bounds: In the setting without setup and adaptive corruptions, we demonstrate that for certain functionalities, no 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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

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)

Publication year

2018

Confidentiality

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

Article name in the collection

Lecture Notes in Computer Science

ISBN

978-3-319-96877-3

ISSN

0302-9743

e-ISSN

neuvedeno

Number of pages

30

Pages from-to

243-272

Publisher name

Neuveden

Place of publication

Neuveden

Event location

Santa Barbara, CA, USA

Event date

Aug 19, 2018

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—