×

Absolutely secure message transmission using a key sharing graph. (English) Zbl 1257.68065

Summary: Assume that there are players and an eavesdropper Eve of unlimited computational power and that several pairs of players have shared secret keys beforehand. In a key sharing graph, each vertex corresponds to a player, and each edge corresponds to a secret key shared by the two players corresponding to the ends of the edge. Given a key sharing graph, a player wishes to send a message to another player so that the eavesdropper Eve and any other player can get no information on the message.
In this paper, we first give a necessary and sufficient condition on a key sharing graph for the existence of such a unicast protocol. We then extend the condition to the case where a multiple number of players other than the sender and receiver passively collude. We finally give a sufficient condition for the existence of a secure multicast protocol.

MSC:

68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68P25 Data encryption (aspects in computer science)
68R10 Graph theory (including graph drawing) in computer science
05C40 Connectivity
05C38 Paths and cycles
94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1007/BF00206326 · Zbl 0654.94012 · doi:10.1007/BF00206326
[2] Diestel R., Graph Theory (2000)
[3] DOI: 10.1145/138027.138036 · Zbl 0774.68017 · doi:10.1145/138027.138036
[4] DOI: 10.1007/s001459910002 · Zbl 0957.68042 · doi:10.1007/s001459910002
[5] DOI: 10.1137/S0895480198335215 · Zbl 1080.94019 · doi:10.1137/S0895480198335215
[6] DOI: 10.1142/S0129054111008659 · Zbl 1222.68037 · doi:10.1142/S0129054111008659
[7] DOI: 10.1016/j.ipl.2009.04.004 · Zbl 1209.68232 · doi:10.1016/j.ipl.2009.04.004
[8] DOI: 10.1002/j.1538-7305.1949.tb00928.x · Zbl 1200.94005 · doi:10.1002/j.1538-7305.1949.tb00928.x
[9] Suzuki H., IEICE Trans. A J 71 pp 1906– (1988)
[10] DOI: 10.1007/s00145-001-0002-y · Zbl 1027.94012 · doi:10.1007/s00145-001-0002-y
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.