Cryptography Reference
In-Depth Information
When
= 0 it is the well-known Nash equilibrium [16]. In some cases, a Nash
equilibrium in the strict sense is hard to compute [3], while computing the
-
approximate Nash equilibrium is much easier [4]. Therefore, the
-Nash equilib-
rium is also an appealing notion for a small
.
Definition 2.
Astrategy
σ
induces an
k-resilient -Nash equilibrium
if for any
coalition
k
) and for any strategy profile
σ
C
C
of at most
k
players (i.e.
|C| ≤
of
the coalition
C
, it holds that
u
i
(
σ
C
,σ
)
≤
u
i
(
σ
C
,σ
)+
for any
i
∈C
,
C
C
where
C
denotes the complement of
C
.
When
k
= 1 it is the
-Nash equilibrium just defined. In this work, we realize
the resilience for
k
=
t
1ina
t
-out-of-
n
secret sharing scheme. Obviously, this
is the optimal coalition resilience in the
t
-out-of-
n
case.
−
2.3
Information-Theoretic MACs
We refer to [6] for the description of information theoretically secure message
authentication codes (MACs). A message authentication code consists of three
polynomial-time algorithms (
Gen
,
Mac
,
Vrfy
). The key-generation algorithm
Gen
takes as input the security parameter 1
m
and outputs a key
k
. The message au-
thentication algorithm
Mac
takes as input a key
k
and a message
M
}
≤m
,
and outputs a tag
t
; we write this as
t
=
Mac
k
(
M
). The verification algorithm
Vrfy
takes as input a key
k
, a message
M
and a tag
t
, and outputs a bit
b
; i.e.,
b
=
Vrfy
k
(
M, t
). We regard
b
= 1 as acceptance and
b
= 0 as rejection, and
require that for all
m
,all
k
output by
Gen
(1
m
), all
M
∈{
0
,
1
}
≤m
, it holds that
∈{
0
,
1
Vrfy
k
(
M,
Mac
k
(
M
)) = 1.
Definition 3.
(
Gen
,
Mac
,
Vrfy
) is an information-theoretic MAC if for any
M
∈
}
≤m
,
k
=
Gen
(1
m
)
,
t
=
Mac
k
(
M
)
, and for any (computationally unbounded)
adversary
{
0
,
1
, the following probability is negligible in
m
:
μ
(
m
)=
Prob
[(
M
,t
)
←A
(
M, t
):
Vrfy
k
(
M
,t
)=1
M
A
=
M
]
.
For example, an information-theoretic MAC can be built as follows [17,19]: Let
F
be a finite field, the key is (
α, β
)
∈
F
2
. For a message
M ∈
F
,thetagis
generated as
t
=
β
−
αM
∈
F
.
3 Rational Secret Sharing: The 2-Out-of-2 Case
In this section we give a 2-out-of-2 rational secret sharing protocol in standard
communication networks (i.e. point-to-point and non-simultaneous channel) and
with unconditional security. Denote the protocol by
Π
, we describe
Π
in terms
of Dealer's protocol and players' protocol separately. Actually, Dealer's protocol
Search WWH ::
Custom Search