A Subexponential Construction of Graph Coloring for Multiparty Computation

Hassan Jameel Asghar; Yvo Desmedt; Josef Pieprzyk; Ron Steinfeld

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2014/066

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}$.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Multiparty Computations
Contact author(s): josef pieprzyk @ gmail com
History: 2014-01-30: received
Short URL: https://ia.cr/2014/066
License: CC BY

BibTeX

@misc{cryptoeprint:2014/066,
      author = {Hassan Jameel Asghar and Yvo Desmedt and Josef Pieprzyk and Ron Steinfeld},
      title = {A Subexponential Construction of Graph Coloring for Multiparty Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/066},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/066}},
      url = {https://eprint.iacr.org/2014/066}
}