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 (secure against an adversary who possesses any t < n 2 $t < \frac{n}{2}$ inputs) and has subexponential complexity of construction based on coloring of planar graphs. 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 has subexponential complexity and is optimal at the same time, i.e., it is secure for any t < n 2 $t < \frac{n}{2}$ .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 (secure against an adversary who possesses any t < n 2 $t < \frac{n}{2}$ inputs) and has subexponential complexity of construction based on coloring of planar graphs. 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 has subexponential complexity and is optimal at the same time, i.e., it is secure for any t < n 2 $t < \frac{n}{2}$ .

Journal of Mathematical CryptologyJul 23, 20140 citations

Quantum algorithms for Abelian groups

Alexei Kitaev, Alexander Khanievich Shen', M. Vyalyi

Graduate studies in mathematicsMay 31, 20020 citations

Quantum Circuit Compilation for the Graph Coloring Problem

Angelo Oddi, Riccardo Rasconi, Marco Baioletti +2 more

Lecture notes in computer scienceJan 1, 20233 citations

t < \frac{n}{2}

inputs) and has subexponential complexity of construction based on coloring of planar graphs. 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 has subexponential complexity and is optimal at the same time, i.e., it is secure for any t < n 2

t < \frac{n}{2}