数理解析研究所講究録1093 巻 1999 年 176-181

176

Secret Bit Transmission Using a Random Deal of Cards on
Hierarchical Structures
Reina Yoshikawa (吉川玲奈) and Yoshihide Igarashi (五十嵐善英)Department of Computer Science, Gunma University, Kiryu, Japan 376-8515$\mathrm{E}$-mail:igarashi@comp. .gunma-u.ac.jp$\mathrm{c}\mathrm{s}$Abstract

We propose a problem how we transmit an information-theoretically secure bit using arandom deal of cards among players in hierarchical structured groups and a computationallyunlimited eavesdropper. A player in the highest group wants to send players in lower groups
a secret bit which is secure from the eavesdropper and some other players. We formalize
this problem, and we design a protocol for constructing a secret key exchange spanning tree
on two-level hierarchical groups of players. Then for the protocol we analyze the conditions
that the secure bit transmission by the protocol is successful. We give a sufficient condition
that the protocol successfully works on the sizes of hands of players and an eavesdropper.
rmation theoretically-secure,
key words: card games, hierarchical structured groups,
key exchange graphs, secret bit transmission,$\mathrm{i}\mathrm{n}\mathrm{f}o$1

Introduction

Suppose that there are players and a passive eavesdropper, Eve, whose computational power$\ldots;G_{h}$ , where $G_{1}=$is unlimited. The players are partitioned into hierarchical groups,, $G_{h}=\{P_{h,1}, \ldots , P_{h},, \ldots, {}_{1}P_{h,k}\}h$ and $|G_{i}|\geq 1$ for each $1\leq i\leq h$ . For each).
$G_{i}\cap G_{j}=\phi,$ and$j(i\neqj),$
is the set of the players (i.e.,pair of andisis.in the suffix order. That is,
We assume that the hierarchy of the groups
in the hierarchy if $i<j$ . Using a random deal of cards we construct a spanninghigher thansatisfying the following conditions, where a node denotes a player:
tree with node set$n$$G_{1},$$n$$\{P_{1,1}, \ldots , P_{1,k_{1}}\},$$\ldots$$\bigcup_{i=1}^{h}G_{i}$$i$$G_{1},$$n= \sum_{i=1}^{h}k_{i}$$n$$\ldots,$$G_{i}$$G_{h}$$G_{j}$$\bigcup_{i=1}^{h}G_{i}$(1) A pair of nodes directly connected by an edge of the spanning tree has a secret key
exchange.
(2) For each $1\leq j\leq h$ , the subgraph of the spanning tree consisting of the nodes in.
and their incident edges is a spanning tree of the nodes of$\bigcup_{i=1}^{j}G_{i}$$\bigcup_{i=1}^{j}G_{i}$(3) If a pair of nodes are connected by an edge of the spanning tree, then both the nodes infor some between
and the other node is in
the same group, or the one node is in$G_{i}$$G_{i+1}$$i$

1 and $h-1$ .

aOnce such a spanning tree is constructed, bit secret communication is possible
pair of nodes directly connected by an edge of the spanning tree. In this paper we assume that
communication from a node a group to a node in any group higher than the group is inhibited$\mathrm{b}\mathrm{e}\mathrm{t}_{)}\mathrm{w}\mathrm{e}\mathrm{e}\mathrm{n}$$\mathrm{i}\mathrm{n}\sim$177even if the two nodes are connected by an edge of the spanning tree. The subtree rooted at a
is a subtree rooted at the node of the spanning tree consisting of nodes notnode in groupin any group higher than . A player chooses a secret bit, and using the suotree rooted at theplayer can send the secret bit to a player in the subtree in the following fashion. If playercomputesof the subtree,
along an edge
wants to send a secret bit to player$G_{i}$$G_{i}$$P_{\dot{\epsilon},j}$$r$$P_{i’,j’}$$(P_{i},, {}_{j}P_{i,j}\prime\prime)$$P_{i,j}$, where is the secret exchange key between
and sends it to
the exclusive-or. Then Pit, obtains by computing $r\oplus r’\oplus r’=r$ . Repeating this method a player
andcan send a secret bit to any node of the subtree rooted at the node of the player. This bit
transmission is information theoretically secure from not only Eve but also any node not in thethe path of the bit transmission. When the number of the hierarchical groups of the players isjust 1, this problem is the same as the secret key exchange using a random deal of cards studied
in $[1][2][3][4]$ . Constructing a secret key excllange spanning tree on the hierarchical structured
players satisfying the three conditions listed above is therefore a more general problem.
$r\oplus r^{l}$$P_{ij’},$

2

$r’$

$P_{i’,j’}$$P_{i,j}$

$r$

$j’$

Preliminary

Fischer and Wright proposed a protocol called the smallest feasible protocol (SFP for short) for
the one-bit secret key exchange [2]. Suppose that there are players and a passive eavesdropper
Eve. Let each player
hold cards and Eve hold cards. Thenis said to be feasible if$j\neqi$$\xi=$$h_{i}=1,$$h_{j}>1$
$e=0$
,
,
for
.
or
if
and
all
We
call
the signature of$ci>1$.
the deal. The SFP is as follows [2]:$n$$P_{i}$$P_{i}$$e$$c_{i}$$(c_{1}, \ldots , c_{n}; e)$(1) Let $P$ be the feasible player holding the smallest hand. (Ties are broken in favor of thelower-numbered player.)contained in her hand and a random card not in her hand andpropose $K=\{x, y\}$ as a key set by asking ”
any player hold a card in $K$ ?

(2) $P$ chooses a random card$x$$\mathrm{D}\mathrm{o}\mathrm{e}‘ \mathrm{s}$holds , she accepts $K$ by announcing that she holds a card in $K$ . The
the remaining
cards and are discarded. Whichever $P$ and holds fewer cards
cards in her hand, which are discarded, and drops out of the protocol. The remaining
players go back to step (1).

(3) If another player
$x$

$Q$

$y$

$Q$

$y$

(4) If none of the players hold , then $K$ is rejected. In this case,the players go back to step (1).
$y$$\mathrm{e}\mathrm{x}^{1}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{e}$

$x$

and

$y$

are discarded, andThe execution of the protocol continues until either there are not enough cards left to complete steps (1) and (2), or until only one player is left. The first case is the case where theprotocol fails, and the second case is the protocol is successful, i.e., a spanning tree of the play, where each edge $(x, y)$ is the result by accepting set $K=\{x, y\}$ in step (3)ers isopaqueset for Eve (i.e., it is equally likely for Eve that $P$ holds and holds or that
as an
$P$
holds and holds . Fischer and Write showed the following theorem [2].
$\mathrm{c}\mathrm{o}\mathrm{n}8\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{C}\mathrm{t}\mathrm{e}\mathrm{d}$

$x$

$y$

$Q$

$Q$

$y$

$x$

Theorem 1 [2] Let $\xi=(c_{1}, \ldots, C_{n}; e)$ be the signature of the deal. Let $ci\geq 1$ for $1\leq i\leq n$ ,and $\max\{\dot{c}_{i}|1\leq i\leq n\}+\min\{c_{i}|1\leq i\leq n\}\geq n+e$. Then the $SFP$ perfomls successfully theconstruction of a spanning tree with the nodes here each e.dge joining two nodes represents
the two nodes sharing one-bit secret key.
$n$

$..w$

$a$

The condition $\max\{C_{i}|1\leq i\leq n\}+\min\{Ci|1\leq i\leq n\}\geq n+e$ provides a sufficient condition
for the SFP to be successful on the signature. However, as shown in $[3][6]$ , it is not a necessary178

condition. For example, the signature $\xi=(3,3,2,1;1)$ has $\max\{c_{i}|1\leq i\leq n\}+\min\{c_{i}|1\leq$$i\leq n\}=4<n+e=5$ , but the SFP succeeds on the signature. A necessary and sufficientcondition for the SFP to be successful on a signature was recently given by Mizuki et al. [6].
However, the description of the necessary and sufficient condition is not simple, and the proof
for the condition is a lengthy case analysis, where the necessary and sufficient condition is givenin each of various cases [6]Protocols for Constructing Key Exchange Spanning bees

3

In the case where the number of the hierarchical groups of the players is 1, a secret one-bit key
exchange spanning tree with the nodes of the players can be constructed by the SFP. In thissection we give a protocol called 2-level protocol for constructing a key exchange spanning treesatisfying the conditions given in Section 1 in the case where the number of the hierarchicalandgroups is 2 (i.e., the case where the players are divided into two hierarchical groups. The 2-level protocol partly uses a modified SFP. Let $\{P_{1,1j}\ldots, P_{1,k_{1}}\}$ be the set of the’. The current size ofbe the set of the players in
andplayers infor each pair of and $j(1\leq i\leq 2,1\leq j\leq k_{i})$ , and the current size
hand is denoted by
has a tag, $T(i,j)$ . For each pair of andof Eve’s hand is denoted by . Each playerifis said to be$(1\leq i\leq 2,1\leq j\leq k_{i}),$ $T(i, j)$ is initially set to be $(i,j)$ . A player, and$e=0$ , for every other player $P_{1,t}(j\neq t)$ in(1) ci,. or (2) $i=1,$
in$e=0$
playerevery,
for$T(2, t)=(1,1)$ , or (3) $i=2,$
in
for every player.
$T(1, t)=(1,1)$ , and for every other player $P_{2,t}(j\neq t)$ in
We use the lexicographical order of the indices of the players. That is, if $i<i’$ , or $i=i’$ and$i’<j’$ , then $(i,j)<(i’,j’)$ . The signature of the deal of the two hierarchical groups is denoted.
by$G_{1}$$n$$G_{2})$$G_{1}$$G_{2}$$\{P_{2,1}, \ldots , P_{2,k_{2}}\}$$P_{i,j^{\mathrm{S}}}$$i$$c_{i_{\dot{\theta}}}$$fea\mathit{8}ible$$P_{i,j}$$G_{1},$$c_{1,j}=1_{\backslash },$$j>1\text{ノ}$$c_{1,t}\neq 1$$P_{1,t}$$c_{2,\mathrm{j}}=1,$$G_{2},$$P_{2,t}$

$j$

$i$

$P_{i,j}$$e$$G_{2},$$G_{1},$$c_{2,t}\neq 1$$\xi=(_{C_{1,1}}, \ldots, c_{1},k_{1} ; c2,1, \ldots, C_{2},k_{2}arrow ; e)$2-level protocol:
withorand there is a player in(1) If there is no player with a non-empty hand in$T(1,i)=(1,1)$
$(1,
1)$
all
for
If
fails.
stops
protocoland, then theits tag value not equal to$1\leq i\leq k_{1}$ then go to step (5). Let
be the feasible player holding the smallest hand in. (Ties are broken in favor of the lower ordered player.) If no player in is feasible,, is chosen.
then the lowest ordered player holding an non-empty hand, say$G_{2}$$G_{1}$$G_{1_{i}}$$P_{1,i}$$G_{1}$$G_{1}$$P_{1,i}$chooses a random card contained in her hand and a randomchosen in (1),card not in her hand and proposes $K=\{x, y\}$ as a key set by asking, ”Does any player
with its tag value different from $T(1, i)$ hold a card in $K$ ? (If there are no cards not in$P_{1,i,y}$ can be a dummy card.)(2) For$x$$P_{1,i}$$P_{1,i}$$y$, with its tag value different from $T(1, i)$ holds then, sayaccepts $K$ by announcing that she holds a card in $K$ . The cards, and are discarded,
such that $T(1, t)=T(1\text{ノ}.i)$ or $T(1, t)=T(1,j),$ $T(1,t)$ is set to be
and for every$T(1, \min\{i,j\})$ . A player holding fewer cards exposes the remaining cards in her hand (i.e.,hereafter the player holds the empty hand). (Ties are broken by exposing the remaining,say, holds
cards in the hand of the player with the larger index.) If a player inthen the cards and are
accepts $K$ by announcing that she holds a card in
then
$(1,
1)$
exposesthe remaining cards$T(2,j)$,and thenis set to be
and thenholds the empty hand). All the players go back to step (1)in her hand (i.e., hereafterwith the updated deal.

(3) If another player in$G_{1}$$P_{1,j}$$P_{1,j}$$y,\cdot$

$x$

$y$

$P_{1,t}$$G_{2j}$$K_{i}$$P_{2,j}$$P_{2,j}$$\mathrm{d}\mathrm{i}_{\mathrm{S}\mathrm{C}\mathrm{a}\mathrm{r}}\mathrm{d}\mathrm{e}\mathrm{d}_{i}$$P_{2,j}$$P_{2,j}.$

$x$

$y$

$y$

179

(4) If none of the players accept $K=\{x,y\}$ , then andplayers go back to step (1) with the updated deal.
$x$

$y$

are discarded, and then all the(5) If for all $1\leq i\leq k_{2j}T(2, i)=(1,1)$ , then the protocol successfully stops. If there isa player with its tag value not equal to $(1, 1)$ in
holding the empty hand, then the
protocol stops and fails. If there are no feasible players in
but there is a player inhand, then let
holding a
be such a player and go to step step (9). Let
be the feasible player holding the smallest hand in. (Ties are broken in favor of the$G_{2}$$G_{2}$$G_{1}$$P_{1,i}$$\mathrm{n}\mathrm{o}\mathrm{n}- \mathrm{e}\mathrm{m}\mathrm{P}^{\mathrm{t}}\mathrm{y}$$P_{2,i}$$G_{2}$

lower ordered player.)chosen in (5),choose8 a random card contained in her hand and a random
card not in her hand and proposes $K=\{x,y\}$ as a key set by asking, ”Does any player
hold a card in $K$ ?

(6) For$P_{2,i}$$x$$P_{2,i}$$y$(7) If a player inholds , then the player accepts $K$ by announcing that she holds a
card in K., then the cards and arethen for every playersuch that$G_{1}$

$y$

$x$

$y$

$P_{2,t}$$\mathrm{d}\mathrm{i}_{\mathrm{S}\mathrm{C}\mathrm{a}\mathrm{r}}\mathrm{d}\mathrm{e}\mathrm{d}_{j}$$T(2,t)=T(2, i),$ $T(2,t)$ is set to be $(1, 1)$ , and thenexpose the remaining cards in her(i.e.,
hand
hereafterholds the empty hand). If another player, say
, in
holds
$P_{2,i}$$P_{2,i}$$P_{2,j}$$G_{2}$

accepts that she holds a card in $K$ , then the cards and are, thenthen for every
such that $T(2,t)=T(2, i)$ or $T(2,t)=T(2,j),$ $T(2, t)$ is set to be$\min\{T(2, i), T(2,j)\}$ , and then a player holding a smaller hand among the two players
exposes the remaining cards (i.e., hereafter the player holds the empty hand.) (Ties arebroken by exposing the remaining cards in the hand of the player with the larger index.)
All the players go back to (5) with the updated deal.
$P_{2,j}$

$y$

$x$

$y$

$\mathrm{d}\mathrm{i}_{\mathrm{S}\mathrm{C}\mathrm{a}\mathrm{r}}\mathrm{d}\mathrm{e}\mathrm{d}_{j}$$P_{2,t}$(8) If none of the players accept $K=\{x, y\}$ , then andplayers go back to step (5) with the updated deal.
$x$

$y$

are discarded, and then all the(9) Letbe the player defined in step (5) (i.e., the player inholding a non-empty hand).
(Note that in this case every player other thanholds the empty hand.)chooses a$G_{1}$$P_{1,i}$$P_{1,i}$in her hand and a random card not in her hand and propose
as a key set by asking, ”Does any player hold a card in $K$ ?

random card
$K=\{x, y\}$$P_{1,i}$$x\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{e}^{\backslash }\mathrm{d}$$y$accepts that she holds a card in $K$ ,holds , then
then the cards and are discarded, then for every
such that $T(2, t)=T(2,j),$ $\tau(2, t)$
is set to be $(1, 1)$ , and then go back to step (5) with updated deal.

(10) If another player,$x$$\mathrm{i}\mathrm{n}G^{\mathrm{v}_{2}}\overline{\sim}\sim$$8\mathrm{a}\mathrm{y}P_{2,j},$$y$$P_{2_{\dot{d}}}$$P_{2,t}$$y$(11) If none of the players accept $K=\{x, y\}$ , then andplayers go back to step (5) with the updated deal.
$x$

$y$

are discarded, and then all the

Example 1 Let $\xi=(4,5,6;7,8;5)$ be theof a deal. We apply the 2-level protocol to$(a)$. The size of each hand is indicated by
the deal. The initial signature shown in Figure 1
a number beside the $corre\mathit{8}ponding$ node in Figure 1. Goupconsists of three player8. Theirinitial tag value8 are $(1, 1)$ , $(1, 2)$ and $(1, 3)$ . Groupof two players. Their initial tag
$(2,
1)$
$(2,
2)$
. The process of constructing a secret key exchange spanning tree by
andvalues are
key exchange spanningthe 2-level protocol is shown in Figure 1. The construction of a$(b),$$(h)$$(a),$,
tree proceeds as shown inof Figure 1. Players with their tag value $(1, 1)$ areAt
playerby
black
circles.
eachawith the double circle propose8 a key
indicatedofcards. A player who announces a $ca7d$ in the key set is indicated by an incoming arrow. $At$
are (1.1). The proces8
the end of proces8 shown in $(c)$ , the tag values of all the players in$(d)$ in Figure 1.
protocolstep
2-level
shown
At
the
is
each proposal by the
from
of
from
$\mathit{8}ignature$$i\mathit{8}$$G_{1}$$G_{2}consi\mathit{8}tS$$\mathit{8}ecret$$\ldots$$\mathit{8}et$$\mathit{8}tage$$G_{1}$$(\dot{\mathit{5}})$

180,
in $(e)$ , Eve has a card in the key
player indicated by the double circle during theplayer inand eventually the stage shown in $(f)$ reache8. At the stage shown in $(f)$ , the. Thisby the player indicated by the double circle ina card in the key set
tree. Thiskey exchange
in $(g)$ , and eventually we obtain asituation istree satisfies the three condition8 listed in Section 1.
$\mathit{8}et$$proce\mathit{8}S$$\mathit{8}econd$$G_{2}$$propo\mathit{8}ed$$G_{1}ha\mathit{8}$$\mathit{8}panning$$\mathit{8}ecret$$\mathit{8}hown$$\mathit{8}panning$

G2

$06$

$05$

$\mathrm{G}1\bullet 4$$\mathrm{O}$$\mathrm{O}$87$\mathrm{G}1\bullet r_{0}^{5\backslash 5}3\mathrm{O}$G2$\mathrm{O}$$\mathrm{O}$

7

8

Eve:

Eve:5

Eve:

$0$

8
Eve: 5
$(d)$

Eve:

$0$

$0$

$(h)$

$(g)$

$(f)$

$(e)$

$\mathrm{O}$

7

$(c)$

$(b)$

$(a)$

$\mathrm{O}$

Eve: 5

Eve: 5

Eve: 5

G2

Figure 1: A process by the 2-level protocol on $\xi=(4,5,6;7,8;5)$

Theorem 2 Let $\xi=(c_{1,1}, \ldots, c_{1,k_{1}} ; c_{2,1}, \ldots, c_{2,k_{2}} ; e)$ be the signature of a deal on hierarchicalarpd $c2$ . If the following two inequalitie8 hold, then the 2-level protocol perform8 sucgroups,
the three condition8
cessfully to construct a secret one-bit key exchange spanning tree
in Section 1.
$G_{1}$$\mathit{8}ati_{S}fying$$li\mathit{8}ted$(1) $\max\{c_{1,i}|1\leq i\leq k_{1}\}+\min\{c_{1,i}|1\leq i\leq k_{1}\}\geq k_{1}+k_{2}+e$(2) $\min\{c_{2,i},|1\leq i\leq k_{2}\}\geq e+k_{2}$propose sets of
For the process before step (5) of the 2-level protoc.ol, players incards. For each proposed set $K=\{x, y\}$ before step (5), one of the following three cases occurs.
, the second case is that one of
The first case is that both and are hold by players in, and the third case is that one of the cards is hold by Eve.
the card8 is hold by a player in
Besides discarding the two cards in $K$ at each proposal, in the first case, exactly one player in
exposes the remaining cards and becomes a player with the empty hand, in the second casethe remaining cards and becomes a player with the empty hand, andthe player inin the third case, the remaining cards are not exposed. We might assume that the behavior of
during the process before step (4) likes Eve if the set of the discarded cards
each player in
at each proposal before step (5) is considered just one
and the exposed cards by a player incard. Therefore, as proved about SFP in [2], if the condition (1) in the theorem is satisfied thenbefore steP
are connected by key exchange edges of a spanning tree inall the players in(5).
has already connected with a player in
When the protocol enters step (5), a player inor no players have not yet connected with any player in . In the latter case, at least one

Proof.

$G_{1}$$x$$G_{1}$$y$$G_{2}$$G_{1}$$G_{2}\mathrm{e}\mathrm{x}\mathrm{p}\mathrm{o}8\mathrm{e}\mathrm{s}$$G_{2}$$G_{2}$$G_{1}$$G_{1}$$G_{2}$$G$$G_{1}$

181

player inshould be connected with a player inin a step after leaving step (4). For eachloop starting step (5), the number of different tag values of players in
is reduced by at least
one, or a player inis directly connected with a player in, or the size of Eve’s hand isreduced by one. Even if there are no chances such a player inis connected with a player inin step (7), there is such a chance in step (10). Note that step (9) and step (10) are prepared
for this purpose. From this observation we can say that if the second condition holds then the
all the players’ tag values eventually become $T(1,1)$ and a desired key exchange spanning treewith the set of players on the hierarchical structure is constructed.
$G_{2}$$G_{1}$$G_{2}$$G_{2}$$G_{1}$$G_{2}$$G_{1}$$\square$4

Concluding Remarks

The condition given in Theorem 2 is a sufficient condition but the converse does not hold inthe signature $\xi=(3,3,2,1;1;\mathrm{o})$ does not satisfies (1) in Theorem
general. For
but the 2-level protocol works successfully on $\xi=(3,3,2,1:1;\mathrm{o})$ in any case. If we could use
the necessary and sufficient condition given in [6] on the sizes of the hands of the players and
Eve that the SFP works successfully, we might obtain a necessary and sufficient condition or asufficient condition stronger than the condition given in Theorem 2. However, the necessary andsufficient condition given in [6] is complicated. We are asked to prepare an elegant necessary andsufficient condition on a signature in the case where the 2-level protocol works successfully. We
are also interested in designing an efficient protocol for constructing good shaped spanning tresssatisfying the conditions given in Section 1 on a general hierarchical structures of the players.
These problems would be worthy of further investigation.
$\mathrm{e}\mathrm{x}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}_{i}$$2_{i}$

References[1] M.J.Fischer, M.S.Paterson and C.Rackoff, “Secret bit transmission using a random deal ofcards”, DIMACS Series in Discrete Ma thematics and Theoretical Computer Science., AMS,

vo1.2,
1991.
[2] M.J.Fischer and R.N.Write, “Multiparty secret key exchange using a random deal of cards”,
Proc. Crypto’91, Lecture Notes in Computer Science, Springer-Verlag, vol.
pp.141-155,
1992.
[3] M.J.Fischer and R.N.Wright, “An application of game-theoretic techniques to cryptography”, DIMACS Series in Discrete Mathematics and Theoretical Compu ter Science, AMS,
vol. 3, pp.99-118, 1993.
[4] M.J.Fischer and R.N.Write, “An efficient protocol for unconditional secure secret key exchange”, Proc. 4th Annual Symposium on Discrete Algorithms, pp.475-483, 1993.
’‘Bounds on secret key exchange using random deal of cards”,[5] M.J.Fischer and
J. Cryptology, vol.9, pp.71-99, 1996.
[6] T.Mizuki, H.Shizuya and T.Nishizeki, “On dealing necessary and sufficient numbers of card8
to share a one-bit key” . Technical Report of Information Processing Society of Japan, 98AL-62, pp.73-80, 1998.
$\mathrm{P}\mathrm{P}^{173-18}.1J^{\cdot}$$576_{J}\backslash$$\dot{1}$$\mathrm{R}.\mathrm{N}.\mathrm{w}_{\mathrm{r}}\mathrm{i}\mathrm{t}\mathrm{e},$$t$