Welcome to the resource topic for 2020/1256
Title:
Asymptotically Good Multiplicative LSSS over Galois Rings and Applications to MPC over Z/p^k Z
Authors: Mark Abspoel, Ronald Cramer, Ivan Damgård, Daniel Escudero, Matthieu Rambaud, Chaoping Xing, 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.
ePrint: https://eprint.iacr.org/2020/1256
Talk: https://www.youtube.com/watch?v=QmoK2e3oQ7I
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .