Indo, Yoshihiro; Mizuki, Takaaki; Nishizeki, Takao Absolutely secure message transmission using a key sharing graph. (English) Zbl 1257.68065 Discrete Math. Algorithms Appl. 4, No. 4, Paper No. 1250053, 15 p. (2012). 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 Keywords:message transmission; key sharing graph; eavesdropper; absolutely secure; 2-connected graph; internally disjoint paths; tree; unicast; multicast; collusion PDFBibTeX XMLCite \textit{Y. Indo} et al., Discrete Math. Algorithms Appl. 4, No. 4, Paper No. 1250053, 15 p. (2012; Zbl 1257.68065) 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.