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 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.

Category / Keywords: foundations / cryptographic protocols / multiparty computation, amortization, information-theoretical security, arithmetic secret sharing, multiplication-friendly embeddings

Date: received 17 Jul 2019, last revised 17 Jul 2019

Contact author: matthieu rambaud at telecom-paristech fr

Available format(s): PDF | BibTeX Citation

Version: 20190718:065945 (All versions of this report)

Short URL: ia.cr/2019/832


[ Cryptology ePrint archive ]