Abstract
Using a random deal of cards to players and a computationally unlimited eavesdropper, all players wish to share a one-bit secret key which is information-theoretically secure from the eavesdropper. This can be done by a protocol to make several pairs of players share one-bit secret keys so that all these pairs form a spanning tree over players. In this paper we obtain a necessary and sufficient condition on the number of cards for the existence of such a protocol. Our condition immediately yields an efficient linear-time algorithm to determine whether there exists a protocol to achieve such a secret key sharing.
Chapter PDF
References
T. Asano, “An O(n log log n) time algorithm for constructing a graph of maximum connectivity with prescribed degrees,” J. Comput. and Syst. Sci., 51, pp. 503–510, 1995.
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, 2, pp. 173–181, 1991.
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, 13, pp. 99–118, 1993.
M. J. Fischer and R. N. Wright, “An efficient protocol for unconditionally secure secret key exchange,” Proceedings of the 4th Annual Symposium on Discrete Algorithms, pp. 475–483, 1993.
M. J. Fischer and R. N. Wright, “Bounds on secret key exchange using a random deal of cards,” J. Cryptology, 9, pp. 71–99, 1996.
M. J. Fischer and R. N. Wright, “Multiparty secret key exchange using a random deal of cards,” Proc. Crypto’ 91, Lecture Notes in Computer Science, Springer-Verlag, 576, pp. 141–155, 1992.
S. L. Hakimi, “On realizability of a set of integers as degrees of the vertices of a linear graph. I,” J. SIAM Appl. Math., 10,3, pp. 496–506, 1962.
F. Harary, “Graph Theory,” Addison-Wesley, Reading, Mass., 1969.
T. Mizuki, H. Shizuya and T. Nishizeki, “Eulerian secret key exchange,” Proc. COCOON’ 98, Lecture Notes in Computer Science, Springer, 1449, pp. 349–360, 1998.
E. F. Schmeichel and S. L. Hakimi, “On planar graphical degree sequences,” SIAM J. Appl. Math., 32, 3, pp. 598–609, 1977.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mizuki, T., Shizuya, H., Nishizeki, T. (1999). Dealing Necessary and Sufficient Numbers of Cards for Sharing a One-Bit Secret Key (Extended Abstract). In: Stern, J. (eds) Advances in Cryptology — EUROCRYPT ’99. EUROCRYPT 1999. Lecture Notes in Computer Science, vol 1592. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48910-X_27
Download citation
DOI: https://doi.org/10.1007/3-540-48910-X_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65889-4
Online ISBN: 978-3-540-48910-8
eBook Packages: Springer Book Archive