An application of st-numbering to secret key agreement

Takaaki Mizuki, Satoru Nakayama, Hideaki Sone

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Assume that there are players and an eavesdropper Eve, where several pairs of players have shared secret keys beforehand. We regard each player as a vertex of a graph and regard each pair of players sharing a key as an edge. Consider the case where Eve knows some of the keys according to a certain probability distribution. In this paper, applying the technique of st-numbering, we propose a protocol which allows any two designated players to agree on a secret key through such a partially leaked key exchange graph. Our protocol is optimal in the sense that Eve's knowledge about the secret key agreed on by the two players is as small as possible.

Original languageEnglish
Pages (from-to)1211-1227
Number of pages17
JournalInternational Journal of Foundations of Computer Science
Issue number5
Publication statusPublished - 2011 Aug


  • Graph algorithm
  • Information-theoretic secrecy
  • Key agreement protocol
  • Key sharing graph
  • st-numbering


Dive into the research topics of 'An application of st-numbering to secret key agreement'. Together they form a unique fingerprint.

Cite this