Welcome to the resource topic for 2024/1473
Title:
A Note on Low-Communication Secure Multiparty Computation via Circuit Depth-Reduction
Authors: Pierre Charbit, Geoffroy Couteau, Pierre Meyer, Reza Naserasr
Abstract:We consider the graph-theoretic 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 fan-in (at most) two, and explore applications of these algorithms to secure multiparty computation with low communication. Over the past few years, a paradigm for low-communication secure multiparty computation has found success based on decomposing a circuit into low-depth chunks''. This approach was however previously limited to circuits with a layered’’ structure. Our graph-theoretic approach extends this paradigm to all circuits. In particular, we obtain the following contributions:
-
Fractionally linear-communication MPC in the correlated randomness model: We provide an N-party protocol for computing an n-input, m-output \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 super-polynomial computation, were restricted to layered circuits, or tolerated a sub-optimal corruption threshold.
-
Sublinear-Communication MPC:
Assuming the existence of N-party Homomorphic Secret Sharing for logarithmic depth circuits (respectively doubly logarithmic depth circuits), we show there exists sublinear-communication secure N-party 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 1-out-of-M-OT complexity of MPC:
We introduce the `` 1-out-of-M-OT complexity of MPC’’ of a function f, denoted C_M(f), as the number of oracle calls required to securely compute f in the 1-out-of-M-OT 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 sublinear-communication 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 .