On the average length of secret key exchange Eulerian circuits

Designing a protocol to exchange a secret key is one of the most fundamenta l subjects in cryptography. Using a random deal of cards, pairs of card pla yers (agents) can share secret keys that are information-theoretically secu re 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 pl ayers. 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 send er. Checking the returned message with the original one, the sender can kno w whether the message circulation has not been influenced by a possible sin gle transmission error or false alteration. It has been known that any Eule rian circuit formed by the protocol has length at most 3/2 k, where k is th e 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 t his paper, we show that the average length of Eulerian circuits is approxim ately k + in k.