## Abstract

The multiparty secret key exchange problem is to find a k-player protocol for generating an n-bit random key. At the end of the protocol, the key should be known to each player but remain completely secret from a computationally unlimited eavesdropper, Eve, who overhears all communication among the players. The players are initially dealt hands of cards of prespecified sizes from a deck of distinct cards; any remaining cards are given to Eve. Considered here is the case in which each player receives the same fraction β of the cards in the deck, for β in the interval (0, 1/k]. The efficiency of a secret key exchange protocol is measured by the smallest deck size d_{0} for which the protocol is guaranteed of success. A secret key exchange protocol is presented with d_{0} = O(n(1/β)^{2.71}). The best previous bound, by Fischer, Paterson, and Rackoff (1991), was super-polynomial in 1/β and only handled the special case of k = 2 and n = 1.

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

Pages | 475-483 |

Number of pages | 9 |

State | Published - 1993 |

Externally published | Yes |

Event | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA Duration: Jan 25 1993 → Jan 27 1993 |

### Other

Other | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

City | Austin, TX, USA |

Period | 1/25/93 → 1/27/93 |

## ASJC Scopus subject areas

- Engineering(all)