Paper 2019/1298

An Efficient Passive-to-Active Compiler for Honest-Majority MPC over Rings

Mark Abspoel and Anders Dalskov and Daniel Escudero and Ariel Nof

Abstract

MPC over rings like $\mathbb Z_{2^{32}}$ or $\mathbb Z_{2^{64}}$ has received a lot of attention recently due to their potential benefits in implementation and performance. Several protocols for active security over these rings have been proposed recently, including an implementation in the dishonest majority setting due to Damgård et al. (S&P 2019) and in the popular three-party and one corruption setting. However, to this date, no concretely-efficient protocol for arithmetic computation over rings in the honest majority setting, which works for any number of parties, have been proposed. In this work, we present a new compiler for MPC over the ring $\mathbb Z_{2^{k}}$ in the honest majority setting, that takes several building blocks, which can be essentially instantiated using semi-honest protocols, and turn them into a maliciously secure protocol. Our compiler follows the framework of Chida et al. (CRYPTO 18) for finite fields, and makes it compatible for rings using techniques from the work of Cramer et al. (CRYPTO 18), with only small additional overhead. Per multiplication gate, our compiler requires only two invocations of a semi-honest multiplication protocol over the larger ring $\mathbb Z_{2^{k+s}}$, where $s$ is the statistical security parameter. As with previous works in this area aiming to achieve high efficiency, our protocol is secure with abort and does not achieve fairness, meaning that the adversary may receive output while the honest parties do not. We provide two efficient instantiations for our compiler. The first instantiation is for the three-party case and is based on replicated secret sharing, where the resulting protocol requires each party to send just $2(k+s)$ bits per multiplication gate. To the best of our knowledge, this is the most efficient three-party protocol for large rings to this date. Our second instantiation is for any number of parties. In this case we manage to instantiate our compiler with a variant of Shamir secret sharing that was recently proposed by Abspoel et al. (TCC 2019). We show that the theoretical constructions from Abspoel et al. (TCC 2019) can be instantiated efficiently and prove that they satisfy the properties required by our building blocks. The resulting protocol requires each party to send just $14(k+s) \log n$ bits per multiplication gate. To the best of our knowledge, this is the first concretely-efficient protocol for MPC over rings with an honest majority that works for any number of parties. We implemented our two protocols, run extensive experiments to measure their performance and report their efficiency. Our results prove that efficient honest-majority MPC over rings is possible.