Scalable Multiparty Computation from Non-linear Secret Sharing

A long line of work has investigated the design of scalable secure multiparty computation (MPC) protocols with computational and communication complexity independent of the number of parties (beyond any dependence on the circuit size). We present the first unconditionally-secure MPC protocols for arithmetic circuits over large fields with total computation \(\ensuremath {\mathcal {O}\left( {|C|\log |F|}\right) }\) , where |C| and |F| denote the circuit and field size, respectively. Prior work could either achieve similar complexity only in communication, or required highly structured circuits, or expensive circuit transformations. To obtain our results, we depart from the prior approach of share packing in linear secret-sharing schemes; instead, we use an “unpacking” approach via non-linear secret sharing.