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.
|Number of pages
|International Journal of Foundations of Computer Science
|Published - 2011 Aug
- Graph algorithm
- Information-theoretic secrecy
- Key agreement protocol
- Key sharing graph