## 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} ∈ 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(_{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(nt^{2}) group elements. Furthermore, we believe that our results can be improved by further study of the associated combinatorial problems.

Original language | English |
---|---|

Title of host publication | Advances in Cryptology - CRYPTO 2007 - 27th Annual International Cryptology Conference, Proceedings |

Editors | Alfred Menezes |

Place of Publication | Berlin |

Publisher | Springer, Springer Nature |

Pages | 591-612 |

Number of pages | 22 |

Volume | 4622 LNCS |

ISBN (Print) | 9783540741428 |

Publication status | Published - 2007 |

Event | 27th Annual International Cryptology Conference, CRYPTO 2007 - Santa Barbara, CA, United States Duration: 19 Aug 2007 → 23 Aug 2007 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4622 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Other

Other | 27th Annual International Cryptology Conference, CRYPTO 2007 |
---|---|

Country/Territory | United States |

City | Santa Barbara, CA |

Period | 19/08/07 → 23/08/07 |