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

We construct the first efficient, unconditionally secure 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 \ne 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.