Paper 2019/832

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

Ronald Cramer, Matthieu Rambaud, and Chaoping Xing

Abstract

This paper studies information-theoretically secure multiparty computation (MPC) over rings $\Z/p^{\ell}\Z$. In the work of [ACD+, TCC'19], a protocol based on the Shamir secret sharing over $\Z/p^{\ell}\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 [ACD+, 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^{\ell}\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 [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. Of independent interest, the new multiplicative triples check, introduced to solve (i), compares to [GSZ, Crypto'20] in that it has constant latency and a different complexity trade-off, both in the particular case of finite fields and when lifted over rings $\Z/p^{\ell}\Z$. Finally, we lift Reverse Multiplication Friendly Embeddings (RMFE) from fields to rings, with same (linear) complexity. Note that RMFE has become a standard amortization technique for communication complexity in MPC in the regime over many instances of the same circuit, as in [CCXY, Crypto'18] and [DLN, Crypto'19]. We can thus compile existing MPC protocols over fields, including [PS, EC'21], into ones over rings $\Z/2^{\ell}\Z$ with same complexities. 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.

Note: Corrected comparison with Polychroniadou-Song EC'21, wrt. the proceedings version.