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 informationtheoretic 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 secretsharing 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{selforthogonality} (as well as distance and dual distance), for $p \geq 3$. Selforthogonal codes are multiplicative, therefore we can use existing results of asymptotically good selfdual codes over fields to obtain arithmetic secret sharing over Galois rings. For $p = 2$ we obtain multiplicativity by using existing techniques of secretsharing using both $C$ and $C^\perp$, incurring a constant overhead. As a result, we obtain asymptotically good arithmetic secretsharing schemes over Galois rings. With these schemes in hand, we extend existing fieldbased 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.
Note: This is the full version of the corresponding paper at ASIACRYPT 2020
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in ASIACRYPT 2020
 Keywords
 Multiparty ComputationGalois RingsCoding Theory
 Contact author(s)

escudero @ cs au dk
m a abspoel @ cwi nl  History
 20201015: revised
 20201014: received
 See all versions
 Short URL
 https://ia.cr/2020/1256
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1256, author = {Mark Abspoel and Ronald Cramer and Ivan Damgård and Daniel Escudero and Matthieu Rambaud and Chaoping Xing and Chen Yuan}, title = {Asymptotically Good Multiplicative LSSS over Galois Rings and Applications to MPC over Z/p^k Z}, howpublished = {Cryptology ePrint Archive, Paper 2020/1256}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1256}}, url = {https://eprint.iacr.org/2020/1256} }