Welcome to the resource topic for 2024/1473
Title:
A Note on LowCommunication Secure Multiparty Computation via Circuit DepthReduction
Authors: Pierre Charbit, Geoffroy Couteau, Pierre Meyer, Reza Naserasr
Abstract:We consider the graphtheoretic problem of removing (few) nodes from a directed acyclic graph in order to reduce its depth. While this problem is intractable in the general case, we provide a variety of algorithms in the case where the graph is that of a circuit of fanin (at most) two, and explore applications of these algorithms to secure multiparty computation with low communication. Over the past few years, a paradigm for lowcommunication secure multiparty computation has found success based on decomposing a circuit into lowdepth chunks''. This approach was however previously limited to circuits with a
layered’’ structure. Our graphtheoretic approach extends this paradigm to all circuits. In particular, we obtain the following contributions:

Fractionally linearcommunication MPC in the correlated randomness model: We provide an Nparty protocol for computing an ninput, moutput \mathsf{F}arithmetic circuit with s internal gates (over any basis of binary gates) with communication complexity (\frac{2}{3}s + n + m)\cdot N\cdot\log \mathsf{F}, which can be improved to ((1+\epsilon)\cdot\frac{2}{5}s+n+m)\cdot N\cdot\log \mathsf{F} (at the cost of increasing the computational overhead from a small constant factor to a large one). Previously, comparable protocols either used more than s\cdot N\cdot \log \mathsf{F} bits of communication, required superpolynomial computation, were restricted to layered circuits, or tolerated a suboptimal corruption threshold.

SublinearCommunication MPC:
Assuming the existence of Nparty Homomorphic Secret Sharing for logarithmic depth circuits (respectively doubly logarithmic depth circuits), we show there exists sublinearcommunication secure Nparty computation for \emph{all} \log^{1+o(1)}depth (resp.~(\log\log)^{1+o(1)}depth) circuits. Previously, this result was limited to (\mathcal{O}(\log))depth (resp.~(\mathcal{O}(\log\log))depth) circuits, or to circuits with a specific structure (e.g. layered). 
The 1outofMOT complexity of MPC:
We introduce the `` 1outofMOT complexity of MPC’’ of a function f, denoted C_M(f), as the number of oracle calls required to securely compute f in the 1outofMOT hybrid model. We establish the following upper bound: for every M\geq 2, C_N(f) \leq (1+g(M))\cdot \frac{2 f}{5}, where g(M) is an explicit vanishing function.
We also obtain additional contributions to reducing the amount of bootstrapping for fully homomorphic encryption, and to other types of sublinearcommunication MPC protocols such as those based on correlated symmetric private information retrieval.
ePrint: https://eprint.iacr.org/2024/1473
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .