Cryptology ePrint Archive: Report 2019/832

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

Ronald Cramer and 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 [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 [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, which we introduce for (i), has better asymptotic complexity than the one of [Crypto'20], 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 \cite[Crypto'18] and [Crypto'19]. We can thus compile existing MPC protocols over fields, including [EC'21], into ones over rings $\Z/2^{\ell}\Z$ with same complexity.

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.

Category / Keywords: foundations / cryptographic protocols

Original Publication (with major differences): IACR-CRYPTO-2021

Date: received 17 Jul 2019, last revised 18 Oct 2021

Contact author: matthieu rambaud at telecom-paris fr

Available format(s): PDF | BibTeX Citation

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

Version: 20211018:005801 (All versions of this report)

Short URL: ia.cr/2019/832


[ Cryptology ePrint archive ]