Abstract
We propose the problem of how to transmit an informationtheoretically 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. J. Fischer, M. S. Paterson and C. Rackoff, “Secret bit transmission using a random deal of cards”, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, vol.2, pp.173–181, 1991.
M. J. Fischer and R. N. Wright, “Multiparty secret key exchange using a random deal of cards”, Advances in Cryptology-CRYPTO’91, Lecture Notes in Computer Science, Springer, vol.576, pp.141–155, 1992
M. J. Fischer and R. N. Wright, “An application of game-theoretic techniques to cryptography”, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, vol.13, pp.99–118, 1993.
M. J. Fischer and R. N. Wright, “An efficient protocol for unconditional secure secret key exchange”, Proc. 4th Annual Symposium on Discrete Algorithms, pp.475–483, 1993.
M. J. Fischer and R. N. Wright, “Bounds on secret key exchange using random deal of cards”, J. Cryptology, vol.9, pp.71–99, 1996.
T. Mizuki, H. Shizuya, and T. Nishizeki, “Dealing necessary and sufficient numbers of cards for sharing a one-bit secret key”, Advances in Cryptology-EUROCRYPT’99, Lecture Notes in Computer Science, Springer, vol.1592, pp.389–401, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yoshikawa, R., Guo, S., Motegi, K., Igarashi1, Y. (2000). Secret Key Exchange Using Random Deals of Cards on Hierarchical Structures. In: Goos, G., Hartmanis, J., van Leeuwen, J., Lee, D.T., Teng, SH. (eds) Algorithms and Computation. ISAAC 2000. Lecture Notes in Computer Science, vol 1969. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-40996-3_25
Download citation
DOI: https://doi.org/10.1007/3-540-40996-3_25
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41255-7
Online ISBN: 978-3-540-40996-0
eBook Packages: Springer Book Archive