**Asymptotically Good Multiplicative LSSS over Galois Rings and Applications to MPC over Z/p^k Z**

*Mark Abspoel and Ronald Cramer and Ivan Damgård and Daniel Escudero and Matthieu Rambaud and Chaoping Xing and Chen Yuan*

**Abstract: **We study information-theoretic multiparty computation (MPC) protocols over rings $\mathbb{Z}/p^k \mathbb{Z}$ that have good asymptotic communication complexity for a large number of players. An important ingredient for such protocols is arithmetic secret sharing, i.e., linear secret-sharing schemes with multiplicative properties. The standard way to obtain these over fields is with a family of linear codes $C$, such that $C$, $C^\perp$ and $C^2$ are asymptotically good (strongly multiplicative). For our purposes here it suffices if the square code $C^2$ is not the whole space, i.e., has codimension at least 1 (multiplicative).

Our approach is to lift such a family of codes defined over a finite field $\mathbb F$ to a Galois ring, which is a local ring that has $\mathbb F$ as its residue field and that contains $\mathbb{Z}/p^k \mathbb{Z}$ as a subring, and thus enables arithmetic that is compatible with both structures. Although arbitrary lifts preserve the distance and dual distance of a code, as we demonstrate with a counterexample, the multiplicative property is not preserved. We work around this issue by showing a dedicated lift that preserves \emph{self-orthogonality} (as well as distance and dual distance), for $p \geq 3$. Self-orthogonal codes are multiplicative, therefore we can use existing results of asymptotically good self-dual codes over fields to obtain arithmetic secret sharing over Galois rings. For $p = 2$ we obtain multiplicativity by using existing techniques of secret-sharing using both $C$ and $C^\perp$, incurring a constant overhead. As a result, we obtain asymptotically good arithmetic secret-sharing schemes over Galois rings.

With these schemes in hand, we extend existing field-based MPC protocols to obtain MPC over $\mathbb{Z}/p^k \mathbb{Z}$, in the setting of a submaximal adversary corrupting less than a fraction $1/2 - \varepsilon$ of the players, where $\varepsilon > 0$ is arbitrarily small. We consider 3 different corruption models. For passive and active security with abort, our protocols communicate $O(n)$ bits per multiplication. For full security with guaranteed output delivery we use a preprocessing model and get $O(n)$ bits per multiplication in the online phase and $O(n \log n)$ bits per multiplication in the offline phase. Thus, we obtain true linear bit complexities, without the common assumption that the ring size depends on the number of players.

**Category / Keywords: **cryptographic protocols / Multiparty Computation, Galois Rings, Coding Theory

**Original Publication**** (with major differences): **IACR-ASIACRYPT-2020

**Date: **received 9 Oct 2020, last revised 15 Oct 2020

**Contact author: **escudero at cs au dk,m a abspoel@cwi nl

**Available format(s): **PDF | BibTeX Citation

**Note: **This is the full version of the corresponding paper at ASIACRYPT 2020

**Version: **20201015:072809 (All versions of this report)

**Short URL: **ia.cr/2020/1256

[ Cryptology ePrint archive ]