TY - GEN
T1 - On secure multi-party computation in black-box groups
AU - Desmedt, Yvo
AU - Pieprzyk, Josef
AU - Steinfeld, Ron
AU - Wang, Huaxiong
PY - 2007
Y1 - 2007
N2 - We study the natural problem of secure n-party computation (in the passive, computationally unbounded attack model) of the n-product function f G(x1,...,xn) = x1 · x 2 ⋯ xn in an arbitrary finite group (G, ·), where the input of party Pi is xi ∈ G for i = 1,...,n. For flexibility, we are interested in protocols for fG which require only 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 results are as follows. First, on the negative side, we show that if (G, ·) is non-abelian and n ≥ 4, then no [n/2]-private protocol for computing fG exists. Second, on the positive side, we initiate an approach for construction of black-box protocols for fG based on k-of-k threshold secret sharing schemes, which are efficiently implementable over any black-box group G. We reduce the problem of constructing such protocols to a combinatorial colouring problem in planar graphs. We then give two constructions for such graph colourings. Our first colouring construction gives a protocol with optimal collusion resistance t < n/2, but has exponential communication complexity O(n(t 2t+1)2) group elements (this construction easily extends to general adversary structures). Our second probabilistic colouring construction gives a protocol with (close to optimal) collusion resistance t t < n/μ for a graph-related constant μ ≤ 2.948, and has efficient communication complexity O(nt2) group elements. Furthermore, we believe that our results can be improved by further study of the associated combinatorial problems.
AB - We study the natural problem of secure n-party computation (in the passive, computationally unbounded attack model) of the n-product function f G(x1,...,xn) = x1 · x 2 ⋯ xn in an arbitrary finite group (G, ·), where the input of party Pi is xi ∈ G for i = 1,...,n. For flexibility, we are interested in protocols for fG which require only 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 results are as follows. First, on the negative side, we show that if (G, ·) is non-abelian and n ≥ 4, then no [n/2]-private protocol for computing fG exists. Second, on the positive side, we initiate an approach for construction of black-box protocols for fG based on k-of-k threshold secret sharing schemes, which are efficiently implementable over any black-box group G. We reduce the problem of constructing such protocols to a combinatorial colouring problem in planar graphs. We then give two constructions for such graph colourings. Our first colouring construction gives a protocol with optimal collusion resistance t < n/2, but has exponential communication complexity O(n(t 2t+1)2) group elements (this construction easily extends to general adversary structures). Our second probabilistic colouring construction gives a protocol with (close to optimal) collusion resistance t t < n/μ for a graph-related constant μ ≤ 2.948, and has efficient communication complexity O(nt2) group elements. Furthermore, we believe that our results can be improved by further study of the associated combinatorial problems.
UR - http://www.scopus.com/inward/record.url?scp=38049173951&partnerID=8YFLogxK
M3 - Conference proceeding contribution
AN - SCOPUS:38049173951
SN - 9783540741428
VL - 4622 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 591
EP - 612
BT - Advances in Cryptology - CRYPTO 2007 - 27th Annual International Cryptology Conference, Proceedings
A2 - Menezes, Alfred
PB - Springer, Springer Nature
CY - Berlin
T2 - 27th Annual International Cryptology Conference, CRYPTO 2007
Y2 - 19 August 2007 through 23 August 2007
ER -