Cryptography Reference
In-Depth Information
sharing protocol with unconditional security (i.e., in the information theoretic set-
ting, such as [10]) is more reliable.
It can see that there is a tradeoff between the above aspects. In this work
we focus on rational secret sharing that is coalition-resilient in the information
theoretic setting and standard communication networks, at the cost of achieving
-Nash equilibria only. But we will see that the “
” is quite small and mostly
acceptable.
1.1 Our Results and Main Ideas
We first design a 2-out-of-2 rational secret sharing protocol with unconditional
security in standard communication networks. The main idea is distributing to
player
P
1
(resp.
P
2
)alistoflength
l
1
(resp.
l
2
)where
l
2
≤
l
2
+ 1. Each cell
of the lists contains a value, and all the values jointly determine the secret. The
recovering phase consists of at most
l
1
+ 1 iterations. In each iteration, say, the
j
-th iteration,
P
1
first broadcasts the value in his
j
-th cell, then
P
2
does similarly.
Since the two cases
l
1
=
l
2
+1and
l
1
=
l
2
both are possible,
P
1
and
P
2
cannot
know which case really happens before the protocol ends. Therefore each player
still has an incentive to broadcast the value even if it comes to his last cell. This
protocol achieves an
-Nash equilibrium, where
is a negligible function in the size
of the secret and is caused by the information-theoretic MACs used inside.
Then we build a
t
-out-of-
n
rational secret sharing protocol that is (
t
l
1
≤
1)-
resilient. Since in the information theoretic setting with non-simultaneous chan-
nels, a coalition of
t
−
1 players can easily get the secret earlier than other players
and leave the protocol early, we try to insure that the innocent players (i.e. play-
ers who follow the protocol) get as much information as possible. The main idea
is to divide each cell into two parts where two values are stored respectively, and
the two values are both possible to be the secret if the secret appears in this cell.
In each iteration, players first broadcast the first part of the current cell in some
order, then the second part. The index indicating whether the current value is
the secret or not is to be revealed only after the next value has been recovered.
More precisely, suppose the secret appears in the
j
-th cell which contains
s
j
and
s
j
−
respectively in the two parts. Even the players in a (
t
−
1)-coalition at
most know that
Prob
[
s
=
s
j
]=
q
and
Prob
[
s
=
s
j
]=1
q
for some constant
q
before seeing the index
I
j
(i.e.
I
j
=0if
s
=
s
j
,and
I
j
=1if
s
=
s
j
). But
I
j
is to be revealed only after recovering
s
j
(by that time
s
j
has already been
recovered). Therefore after the coalition determines the secret
s
and leaves the
protocol, the rest players at least know
s
=
s
j
or
s
j
, which is also a pleasant
result when the secret-domain is large. On the other hand, the extra gain of the
deviating coalition is at most
,where
is exponentially small in the number of
participants in the recovering process.
−
1.2 Related Work
Table 1 displays comparisons in some aspects between our protocols in this paper
and those in some previous work.
Search WWH ::
Custom Search