Paper 2020/1256

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

Mark Abspoel, Ronald Cramer, Ivan Damgård, Daniel Escudero, Matthieu Rambaud, 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 $$ to a Galois ring, which is a local ring that has $$ as its residue field and that contains $$ 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 $$. 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 $$ we obtain multiplicativity by using existing techniques of secret-sharing using both $$ and $$, 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 $$, in the setting of a submaximal adversary corrupting less than a fraction $$ of the players, where $$ is arbitrarily small. We consider 3 different corruption models. For passive and active security with abort, our protocols communicate $$ bits per multiplication. For full security with guaranteed output delivery we use a preprocessing model and get $$ bits per multiplication in the online phase and $$ 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.

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