On the average length of secret key exchange Eulerian circuits

Takaaki Mizuki, Zhi Bo Sui, Hiroki Shizuya, Takao Nishizeki

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Designing a protocol to exchange a secret key is one of the most fundamental subjects in cryptography. Using a random deal of cards, pairs of card players (agents) can share secret keys that are information-theoretically secure against an eavesdropper. A key set protocol, which uses a random deal of cards, can perform an Eulerian secret key exchange, in which the pairs of players sharing secret keys form an Eulerian circuit passing through all players. Along the Eulerian circuit any designated player can send a message to the rest of players and the message can be finally sent back to the sender. Checking the returned message with the original one, the sender can know whether the message circulation has not been influenced by a possible single transmission error or false alteration. It has been known that any Eulerian circuit formed by the protocol has length at most 3/2 k, where k is the number of players. Note that the length corresponds to the time required to send the message to all players and acknowledge the secure receipt. In this paper, we show that the average length of Eulerian circuits is approximately k + In k.

Original languageEnglish
Pages (from-to)662-670
Number of pages9
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number4
Publication statusPublished - 2000


  • Card game
  • Eulerian graph
  • Information-theoretically secure
  • Key set protocol
  • Secret key exchange


Dive into the research topics of 'On the average length of secret key exchange Eulerian circuits'. Together they form a unique fingerprint.

Cite this