Desmedt, Y;
Pieprzyk, J;
Steinfeld, R;
Wang, HX;
(2007)
On secure multi-party computation in black-box groups.
In: Menezes, A, (ed.)
**ADVANCES IN CRYPTOLOGY - CRYPTO 2007, PROCEEDINGS.**
(pp. 591 - 612).
SPRINGER-VERLAG BERLIN

## Abstract

We study the natural problem of secure n-party computation (in the passive, computationally unbounded attack model) of the n-product function f(G)(x(1), . . . , x(n)) = x(1) . x(2) . . . x(n) in an arbitrary finite group (G, .), where the input of party P-i is x(i) is an element of G for i = 1, . . . , n. For flexibility, we are interested in protocols for f(G) 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 f(G) exists. Second, on the positive side, we initiate an approach for construction of black-box protocols for f(G) 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 (2t+1 t)(2)) group elements t (this construction easily extends to general adversary structures). Our second probabilistic colouring construction gives a protocol with (close to optimal) collusion resistance t < n/mu for a graph-related constant mu <= 2.948, and has efficient communication complexity O(nt(2)) group elements. Furthermore, we believe that our results can be improved by further study of the associated combinatorial problems.

Type: | Proceedings paper |
---|---|

Title: | On secure multi-party computation in black-box groups |

Event: | 27th Annual International Cryptology Conference |

Location: | Santa Barbara, CA |

Dates: | 2007-08-19 - 2007-08-23 |

ISBN-13: | 978-3-540-74142-8 |

Keywords: | multi-party computation, non-abelian group, black-box, planar graph, graph colouring, PUBLIC-KEY CRYPTOSYSTEMS, DISCRETE LOGARITHMS |

UCL classification: | UCL > School of BEAMS > Faculty of Engineering Science UCL > School of BEAMS > Faculty of Engineering Science > Computer Science |

URI: | http://discovery.ucl.ac.uk/id/eprint/139141 |

### Archive Staff Only

View Item |