Paper 2024/1473

A Note on Low-Communication Secure Multiparty Computation via Circuit Depth-Reduction

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: 1) Fractionally linear-communication MPC in the correlated randomness model: We provide an $$-party protocol for computing an $$-input, $$-output $$-arithmetic circuit with $$ internal gates (over any basis of binary gates) with communication complexity $$, which can be improved to $$ (at the cost of increasing the computational overhead from a small constant factor to a large one). Previously, comparable protocols either used more than $$ bits of communication, required super-polynomial computation, were restricted to layered circuits, or tolerated a sub-optimal corruption threshold. 2) Sublinear-Communication MPC: Assuming the existence of $$-party Homomorphic Secret Sharing for logarithmic depth circuits (respectively doubly logarithmic depth circuits), we show there exists sublinear-communication secure $$-party computation for \emph{all} $$-depth (resp.~$$-depth) circuits. Previously, this result was limited to $$-depth (resp.~$$-depth) circuits, or to circuits with a specific structure (e.g. layered). 3) The 1-out-of-M-OT complexity of MPC: We introduce the `` 1-out-of-M-OT complexity of MPC'' of a function $$, denoted $$, as the number of oracle calls required to securely compute $$ in the 1-out-of-M-OT hybrid model. We establish the following upper bound: for every $$, $$, where $$ 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.