Asymptotically-Good Arithmetic Secret Sharing over $\mathbb {Z}/p^{\ell }\mathbb {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 [ACD+19, TCC'19], a protocol based on the Shamir secret sharing over Z/p ℓ Z was presented. As in the eld case, its limitation is that the share size grows as the number of players increases. Then several MPC protocols were developed in [ACD+20, Asiacrypt'20] to overcome this limitation. However, (i) their oine 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 elds to rings; (iii) most importantly, the BGW model could not be applied via the secret sharing given in [ACD+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. Of independent interest, the new multiplicative triples check, introduced to solve (i), compares to [GSZ20, Crypto'20] in that it has constant latency and a dierent complexity trade-o, both in the particular case of nite elds and when lifted over rings Z/p ℓ Z. Finally, we lift Reverse Multiplication Friendly Embeddings (RMFE) from elds 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 [CCXY18, Crypto'18] and [DLN19, Crypto'19]. We can thus compile existing MPC protocols over elds, including [PS21, EC'21], into ones over rings Z/2 ℓ 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 nite elds obtained from existing computational techniques. Then we present, and implement, an ecient algorithm to Hensel-lift the generating matrix of the code, such that the multiplicative conditions are preserved over Supported by Horizon 2020 74079(ALGSTRONGCRYPTO) and NSFC under grant 12031011 and the National Key Research and Development Project 2020YFA0712300 rings. On the other hand, a random lifting of codes over rings does not preserve multiplicativity in general. Finally we provide ecient methods for sharing and reconstruction over rings.