CryptoDB
Graph Coloring Applied to Secure Computation in Non-Abelian Groups
| Authors: | |
|---|---|
| Download: | |
| Abstract: | We study the natural problem of secure n-party computation (in the computationally unbounded attack model) of circuits over an arbitrary finite non-Abelian group (G,⋅), which we call G-circuits. Besides its intrinsic interest, this problem is also motivating by a completeness result of Barrington, stating that such protocols can be applied for general secure computation of arbitrary functions. For flexibility, we are interested in protocols which only require black-box access to the group G (i.e. the only computations performed by players in the protocol are a group operation, a group inverse, or sampling a uniformly random group element). Our investigations focus on the passive adversarial model, where up to t of the n participating parties are corrupted.Our results are as follows. We initiate a novel approach for the construction of black-box protocols for G-circuits based on k-of-k threshold secret-sharing schemes, which are efficiently implementable over any black-box (non-Abelian) group G. We reduce the problem of constructing such protocols to a combinatorial coloring problem in planar graphs. We then give three constructions for such colorings. Our first approach leads to a protocol with optimal resilience t |
BibTeX
@article{jofc-2012-29486,
title={Graph Coloring Applied to Secure Computation in Non-Abelian Groups},
journal={Journal of Cryptology},
publisher={Springer},
volume={25},
pages={557-600},
doi={10.1007/s00145-011-9104-3},
author={Yvo Desmedt and Josef Pieprzyk and Ron Steinfeld and Xiaoming Sun and Christophe Tartary and Huaxiong Wang and Andrew Chi-Chih Yao},
year=2012
}