Asymptotically-Good Arithmetic Secret Sharing over Z/ p^ℓZ with Strong Multiplication and Its Applications to Efficient MPC

This paper studies information-theoretically secure multiparty computation (MPC) over rings Z/ p^ℓZ. In the work of [Abs+19a, TCC’19], a protocol based on the Shamir secret sharing over Z/ p^ℓZ was presented. As in the field case, its limitation is that the share size grows as the number of players increases. Then several MPC protocols were developed in [Abs+20, Asiacrypt’20] to overcome this limitation. However, (i) their offline multiplication gate has super-linear communication complexity in the number of players; (ii) the share size is doubled for the most important case, namely over Z/ 2 ^ℓZ due to infeasible lifting of self-orthogonal codes from fields to rings; (iii) most importantly, the BGW model could not be applied via the secret sharing given in [Abs+20, Asiacrypt’20] due to lack of strong multiplication. In this paper we overcome all the drawbacks mentioned above. Of independent interest, we establish an arithmetic secret sharing with strong multiplication, which is the most important primitive in the BGW model. Incidentally, our solution to (i) has some advantages over the concurrent one of [PS21, EC’21], since it is direct, is only one-page long, and furthermore carries over Z/ p^ℓZ. Finally, we lift Reverse Multiplication Friendly Embeddings (RMFE) from fields to rings, with same (linear) complexity. Note that RMFE has become a standard technique for communication complexity in MPC in the regime over many instances of the same circuit, as in [Cas+18, Crypto’18] and [DLN19, Crypto’19]. We thus recover the same amortized complexity of MPC over Z/ 2 ^ℓZ than over fields. To obtain our theoretical results, we use the existence of lifts of curves over rings, then use the known results stating that Riemann-Roch spaces are free modules. To make our scheme practical, we start from good algebraic geometry codes over finite fields obtained from existing computational techniques. Then we present, and implement, an efficient algorithm to Hensel-lift the generating matrix of the code, such that the multiplicative conditions are preserved over rings. On the other hand, a random lifting of codes over rings does not preserve multiplicativity in general. Finally we provide efficient methods for sharing and reconstruction over rings.