**A Subexponential Construction of Graph Coloring for Multiparty Computation**

*Hassan Jameel Asghar, Yvo Desmedt, Josef Pieprzyk, and Ron Steinfeld*

**Abstract: **We show the first deterministic construction of an unconditionally secure multiparty computation (MPC) protocol in the passive adversarial model over black-box non-Abelian groups which is both optimal and has subexponential complexity of construction. More specifically, following the result of Desmedt et al. (2012) that the problem of MPC over non-Abelian groups can be reduced to finding a $t$-reliable $n$-coloring of planar graphs, we show the construction of such a graph which allows a path from the input nodes to the output nodes when any $t$-party subset is in the possession of the adversary. Unlike the (deterministic) constructions from Desmedt et al. (2012) our construction is subexponential and optimal at the same time, i.e., it is secure for any $t < \frac{n}{2}$.

**Category / Keywords: **cryptographic protocols / Multiparty Computations

**Date: **received 29 Jan 2014

**Contact author: **josef pieprzyk at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20140130:115952 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]