Construction of Secret Key Exchange Spanning Trees by Random Deals of Cards on Hierarchical Structures

Reina YOSHIKAWA  Shimin GUO  Kazuhiro MOTEGI  Yoshihide IGARASHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E84-A   No.5   pp.1110-1119
Publication Date: 2001/05/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
card games,  hierarchical groups,  information-theoretically secure,  key exchange graphs,  secret bit transmission,  

Full Text: PDF>>
Buy this Article

We propose the problem of how to transmit an information-theoretically secure bit using random deals of cards among players in hierarchical groups and a computationally unlimited eavesdropper. A player in the highest group wants to send players in lower groups a secret bit which is secure from the eavesdropper and some other players. We formalize this problem and design protocols for constructing secret key exchange spanning trees on hierarchical groups. For each protocol we give sufficient conditions to successfully construct a secret key exchange spanning tree for the hand sizes of the players and the eavesdropper.