Paper 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 deals with (1) asymptotics of ``strongly-multiplicative'' arithmetic secret sharing over an arbitrary fixed ring $R_\ell:=\mathbb{Z}/p^{\ell}\mathbb{Z}$ ($p>0$ prime, $\ell>0$ an integer) and supporting an unbounded number of players $n$, and with (2) its applications to communication complexity of arithmetic MPC over this ring. For each integer $r>0$, let $R_\ell(r)$ be the degree-$r$ Galois-ring extension of $R_\ell$, with maximal ideal $p$, residue field $(R_\ell(r))/p=\mathbb{F}_{p^{r}}$, and $|R_\ell(r)|= p^{\ell r}$. Using theory of AG-codes over finite fields and over rings, combined with nontrivial algebraic-geometric lifting techniques, we show that, for arbitrary fixed ring $R_\ell=\mathbb{Z}/p^{\ell}\mathbb{Z}$, there is a fixed integer $\hat{r}=\hat{r}(p)>0$ and a (dense) family of $R_\ell(\hat{r})$-linear codes $C$ of unbounded length such that: -- Denoting the reduction of $C$ modulo $p$ (an $\mathbb{F}_{p^{\hat{r}}}$-linear code) by $\overline{C}$, each of $\overline{C}$, $(\overline{C})^{\bot}$ (dual), $(\overline{C})^{\ast 2}$ ("square under Schur-product'') is asymptotically good. -- Each of $C$, $C^{\bot}$, $C^{\ast 2}$ is free over $R_\ell(\hat{r})$, with the same dimension as its reduction. Therefore, each has the same minimum distance as its reduction. Particularly, each is asymptotically good. -- All constructions are efficient. This implies arithmetic secret sharing over the fixed ring $\mathbb{Z}/p^{\ell}\mathbb{Z}$ (rather, the constant-degree extension) with unbounded (dense) $n$, secret-space dimension $\Omega(n)$, share-space dimension $O(1)$, $t$-privacy $\Omega(n)$ with $t$-wise share-uniformity and $1/3 - t/n>0$ a constant arbitrarily close to 0, and, ---last-but-not-least---, ``multiplicativity-locality'' $n-t$. This extends Chen-Cramer (CRYPTO 2006), which only works over any (large enough) finite fields, significantly. Concrete parameters we show here are at least as large. We also show a similar lifting result for asymptotically-good reverse multiplication-friendly embeddings (RFME) and we show how to get an asymptotically-good alternative for the functionality of "hyper-invertible matrices" (essential for efficient active-security MPC), as the latter are inherently asymptotically-bad. Finally, we give two applications to general arithmetic MPC over $\mathbb{Z}/p^{\ell}\mathbb{Z}$ (in the BGW-model with active, perfect security) with communication complexity significantly better than the obvious approach based on combining MPC over $\mathbb{F}_p$ with added circuitry for emulation of the basic $\mathbb{Z}/p^{\ell}\mathbb{Z}$-operations over $\mathbb{F}_p$. Concretely, recent results by Cascudo-Cramer-Xing-Yuan on amortized complexity of MPC (CRYPTO 2018) are now achievable over these rings instead of finite fields, with the same asymptotic complexity and adversary rates.