Cryptography Reference
In-Depth Information
-
Each player always prefers to learn the secret than to not learn it;
-
Secondarily, each player prefers that the fewer of the other players who get
it, the better.
In particular, we define four utility values for each player
P
i
:
(1)
u
i
=
a
if
P
i
gets the secret while
P
j
does not for any
j
=
i
;
(2)
u
i
=
b
if
P
i
gets the secret and so does
P
j
=
i
;
(3)
u
i
=
c
if
P
i
does not get the secret and neither does
P
j
for some
j
for any
j
=
i
;
(4)
u
i
=
d
if
P
i
does not get the secret while
P
j
does for some
j
=
i
.
From the common assumptions on utilities, it obviously holds that
a>b>c>d
.
Let
S
denote the secret-domain and
be the cardinality of
S
. Then by guessing
the secret uniformly from
S
, a player at most gets the utility
|
S
|
1
1
U
random
=
a
+(1
−
)
c.
|
S
|
|
S
|
To make every player has the incentive to participate in a protocol for secret
recovering, it requires
b>U
random
.
Concerning about coalitions, for simplicity we additionally assume that
-
Once a player joins a coalition, he will never leave the coalition before the
protocol ends;
-
Players in the same coalition always share all information they jointly have.
Given an execution of a protocol, let
C
(
i
) denote the coalition that
P
i
joined
in. Thus all players in
(
i
) have the same utility as
P
i
.Asanextension,we
similarly define the four utility values
a, b, c, d
for each player
P
i
as in (1)-(4)
just replacing “
j
C
(
i
)”.
When no coalition is formed, namely,
=
i
”with“
j
∈C
,the
problem is much easier [10]. In this work we deal with the most general coalitions
in
t
-out-of
n
secret sharing, i.e. 1
C
(
i
)=
{
i
}
for any
i
∈{
1
, ..., n
}
≤|C
(
i
)
|≤
t
−
1.
2.2 Notions of Equilibria
In the recovering process of a secret sharing scheme, view the interaction between
players as a game among the
n
players. Let
σ
=(
σ
1
, ..., σ
n
) denote a strategy
profile of players, where
σ
i
is
P
i
's strategy for 1
≤
i
≤
n
. Usually, we let
σ
−i
denote the strategy profile of all players except
P
i
and
σ
C
denote the strategy
profile constricted to the coalition
. Given a strategy profile
σ
,
it induces the utility
u
i
(
σ
) for each player
P
i
. Referring to the definitions in
[1,5,10,11], we give some notions of equilibria as follows:
C⊆{
1
, ..., n
}
Definition 1.
Astrategy
σ
induces an
-Nash equilibrium
if for any player
P
i
and any strategy
σ
i
of
P
i
, it holds that
u
i
(
σ
i
,σ
−i
)
≤ u
i
(
σ
i
,σ
−i
)+
.
Search WWH ::
Custom Search