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 d0 for which the protocol is guaranteed of success. A secret key exchange protocol is presented with d0 = 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)