Cryptography Reference
In-Depth Information
(d) The short list holder is not contained in
C
.
can only know
l
∗
≤
Then the coalition
C
l
−
1 in advance. By the analysis
similar to that of (a),
C
has no incentive to deviate in the
j
-th iteration for
1
≤
j<l
−
1. In the (
l
−
1)-th iteration, similar to the analysis of the fourth
can only increase the utility by at most
λ
k−c
(
a
situation in (c),
C
−
b
)ifthey
deviates from the protocol.
From the analysis (a)-(d) above, we can get the following theorem.
Theorem 2.
Let the parameters
p
,q
and the utility values satisfy the in-
equalities (3)-(5), then the protocol
Π
for
t
-out-of-
n
rational secret sharing
induces a
(
t
1)
-resilient
-Nash equilibrium with
<λ
k−t
+1
(
a
−
−
b
)
,where
λ
=
max
{
q,
1
−
q
}
and
k
is the number of participants in the recovering process.
Remark 3.
Note that the inequality (4) and (5) may not simultaneously hold for
some values of
a, b, c, d
. This can be solved by making some additional assump-
tions on the utility values. For example, assume that
a
−
b<b
−
c
, then the
a−b
a−c
<q<
b−c
inequality (4) and (5) are satisfied for
a−c
. Actually, the assumption
a
=2,
i.e. each player still has an incentive to participate in the protocol for recovering
even if the secret is just one bit.
−
b<b
−
c
is implied from the natural requirement of
U
random
<b
for
|
S
|
Remark 4.
It can see that the
is exponentially small in the number of partici-
pants. When a large number of players participate in the recovering process or
the utility values
a
and
b
are very close, a coalition of (
t
1) players cannot
gain much by deviation form
Π
. Actually, as pointed out in [10] a gain by a
(
t
−
1)-coalition is inevitable in the information theoretic setting. We leave it as
an open problem to determine the lower bound of
at achieving (
t
−
−
1)-resilience
in standard communication networks.
On the other side, although some players quit from the protocol after they
get the secret, leaving the other players (who honestly follow the protocol so far,
thus we call them “innocent players”) cannot determine what the secret is, the
innocent player can at least be sure that the secret must be one of the two values
he has already recovered. Thus in innocent players' view the Shannon entropy
of the secret reduces to less than 1. When
is very large, every rational player
has great incentive to participate in the protocol
Π
even if he might encounter
a coalition of
t
|
S
|
−
1players.
5 Conclusions
In the information theoretic setting of rational secret sharing, only approximate
Nash equilibrium can be achieved in standard communication networks. We re-
alize
-Nash both for the 2-out-of-2 case and the
t
-out-of-
n
case. The 2-out-of-2
protocol is more ecient than previous ones and the
is a negligible function in
the size of the secret. This negligible function is due to the information-theoretic
Search WWH ::
Custom Search