Welcome to the resource topic for 2021/1025
Title:
Efficient Information-Theoretic Multi-Party Computation over Non-Commutative Rings
Authors: Daniel Escudero, Eduardo Soria-Vazquez
Abstract:We construct the first efficient MPC protocol that only requires black-box access to a non-commutative ring R. Previous results in the same setting were efficient only either for a constant number of corruptions or when computing branching programs and formulas. Our techniques are based on a generalization of Shamir’s secret sharing to non-commutative rings, which we derive from the work on Reed Solomon codes by Quintin, Barbier and Chabot (IEEE Transactions on Information Theory, 2013). When the center of the ring contains a set A = \{\alpha_0, \ldots, \alpha_n\} such that \forall i \neq j, \alpha_i - \alpha_j \in R^*, the resulting secret sharing scheme is strongly multiplicative and we can generalize existing constructions over finite fields without much trouble. Most of our work is devoted to the case where the elements of A do not commute with all of R, but they just commute with each other. For such rings, the secret sharing scheme cannot be linear on both sides" and furthermore it is not multiplicative. Nevertheless, we are still able to build MPC protocols with a concretely efficient online phase and black-box access to $R$. As an example we consider the ring $\mathcal{M}_{m\times m}(\mathbb{Z}/2^k\mathbb{Z})$, for which when $m > \log(n+1)$, we obtain protocols that require around $\lceil\log(n+1)\rceil/2$ less communication and $2\lceil\log(n+1)\rceil$ less computation than the state of the art protocol based on Circuit Amortization Friendly Encodings (Dalskov, Lee and Soria-Vazquez, ASIACRYPT 2020). In this setting with a less commutative" A, our black-box preprocessing phase has a less practical complexity of \poly(n). Due to this, we additionally provide specialized, concretely efficient preprocessing protocols for R = \mathcal{M}_{m\times m}(\mathbb{Z}/2^k\mathbb{Z}) that exploit the structure of the matrix ring.
ePrint: https://eprint.iacr.org/2021/1025
Talk: https://www.youtube.com/watch?v=Syo0aQzq3zY
Slides: https://iacr.org/submit/files/slides/2021/crypto/crypto2021/135/slides.pptx
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 .