Paper 2021/1025

Efficient Information-Theoretic Multi-Party Computation over Non-Commutative Rings

Daniel Escudero and 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.CRYPTO '21
Keywords
MPCinformation-theoreticnon-commutative
Contact author(s)
escudero @ cs au dk
eduardo soria-vazquez @ tii ae
History
2021-08-06: received
Short URL
https://ia.cr/2021/1025
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1025,
      author = {Daniel Escudero and Eduardo Soria-Vazquez},
      title = {Efficient Information-Theoretic Multi-Party Computation over Non-Commutative 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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.