Paper 2021/1025
Efficient InformationTheoretic MultiParty Computation over NonCommutative Rings
Daniel Escudero and Eduardo SoriaVazquez
Abstract
We construct the first efficient MPC protocol that only requires blackbox access to a noncommutative 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 noncommutative 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 blackbox 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 SoriaVazquez, ASIACRYPT 2020). In this setting with a ``less commutative" $A$, our blackbox 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.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Major revision.CRYPTO '21
 Keywords
 MPCinformationtheoreticnoncommutative
 Contact author(s)

escudero @ cs au dk
eduardo soriavazquez @ tii ae  History
 20210806: received
 Short URL
 https://ia.cr/2021/1025
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1025, author = {Daniel Escudero and Eduardo SoriaVazquez}, title = {Efficient InformationTheoretic MultiParty Computation over NonCommutative Rings}, howpublished = {Cryptology ePrint Archive, Paper 2021/1025}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1025}}, url = {https://eprint.iacr.org/2021/1025} }