Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/97034
Title: Graph coloring applied to secure computation in non-Abelian groups
Authors: Yao, Andrew Chi-Chih
Wang, Huaxiong
Desmedt, Yvo
Pieprzyk, Josef
Steinfeld, Ron
Sun, Xiaoming
Tartary, Christophe
Keywords: DRNTU::Science
Issue Date: 2011
Source: Desmedt, Y., Pieprzyk, J., Steinfeld, R., Sun, X., Tartary, C., Wang, H., et al. (2012). Graph Coloring Applied to Secure Computation in Non-Abelian Groups. Journal of Cryptology, 25(4), 557-600.
Series/Report no.: Journal of Cryptology
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<n/2, but it requires exponential communication complexity O((2t+1t)2⋅Ng) group elements and round complexity O((2t+1t)⋅Ng) , for a G-circuit of size N g . Nonetheless, using this coloring recursively, we obtain another protocol to t-privately compute G-circuits with communication complexity Poly(n)⋅Ng for any t∈O(n 1−ϵ ) where ϵ is any positive constant. For our third protocol, there is a probability δ (which can be made arbitrarily small) for the coloring to be flawed in term of security, in contrast to the first two techniques, where the colorings are always secure (we call this protocol probabilistic, and those earlier protocols deterministic). This third protocol achieves optimal resilience t<n/2. It has communication complexity O(n 5.056(n+log δ −1)2⋅N g ) and the number of rounds is O(n 2.528⋅(n+log δ −1)⋅N g ).
URI: https://hdl.handle.net/10356/97034
http://hdl.handle.net/10220/11624
ISSN: 0933-2790
DOI: http://dx.doi.org/10.1007/s00145-011-9104-3
Rights: © 2011 International Association for Cryptologic Research.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.