Cryptography Reference
In-Depth Information
a
1
,
Mac
α
1
(
a
1
)
a
2
,
Mac
α
2
(
a
2
),
β
1
··· ··· a
l
1
,
Mac
α
l
1
(
a
l
1
),
β
l
1
−
1
L
1
:
(
b
2
,
Mac
(
b
2
))
(
b
l
2
,
Mac
(
b
l
2
))
end
(
a
1
,
Mac
(
a
1
))
(
b
1
,
Mac
(
b
1
))
(
a
2
,
Mac
(
a
2
))
(
a
l
1
,
Mac
(
a
l
1
))
b
1
,
Mac
β
1
(
b
1
),
α
1
b
2
,
Mac
β
2
(
b
2
),
α
2
··· ···
b
l
2
,
Mac
β
l
2
(
b
l
2
),
α
l
2
L
2
:
Fig. 1.
The recovering process when
l
1
=
l
2
(a)
P
1
has no incentive to deviate in the first iteration.
Since
l
1
+
l
2
=
l
+1
>
1, it must have
l
2
≥
1. Namely,
P
2
at least holds a value
that contributes to determining
s
.
P
1
cannot get this value if his message
broadcast in the first iteration does not pass verification of the MAC. So by
deviating,
P
1
can get utility at most
μ
(
m
)
a
+(1
μ
(
m
))
U
random
,where
μ
(
m
)
is the probability of successfully forging an MAC as defined in Definition 3
and
U
random
=
−
1
|S|
1
|S|
)
c
is an upperbound of the utility that a player
can get by guessing the secret uniformly from
S
. By requiring
a
+(1
−
μ
(
m
)
a
+(1
−
μ
(
m
))
U
random
<b
(1)
P
1
has no incentive to deviate in this iteration.
(b) For 2
l
1
,
P
1
has no incentive to deviate in the
j
-th iteration.
Similarly to the analysis in (a),
P
1
has no incentive to deviate through iter-
ation 2 to
l
1
−
≤
j
≤
1. Achieving the
l
1
-th iteration, with probability
p
it holds
that
l
2
=
l
1
−
1, i.e.
P
2
's list has run out. In this situation,
P
1
can get utility
at most
a
by deviation. But if
l
2
=
l
1
which happens with probability 1
−
p
,
P
1
getatmost
μ
(
m
)
a
+(1
−
μ
(
m
))
U
random
. Therefore
P
1
will not deviate
by requiring
pa
+(1
−
p
)(
μ
(
m
)
a
+(1
−
μ
(
m
))
U
random
)
<b.
(2)
Note that inequality (2) implies inequality (1).
(c) For 1
l
2
,
P
2
has no incentive to deviate in the
j
-th iteration.
The analysis is similar to that of (b).
(d)
P
1
(resp.
P
2
) cannot increase his utility more than
by deviating in the
(
l
1
+ 1)-th (resp. the (
l
2
+ 1)-th) iteration.
In the (
l
1
+ 1)-th iteration and after verifying the MAC,
P
1
already knows
that
l
2
=
l
1
and he can determine
s
=(
⊕
≤
j
≤
l
i
=1
b
i
). But
P
2
still
does not know whether
P
1
's list is longer than his or not.
P
1
can deceive
P
2
by continuing to send a fake value in the (
l
1
+ 1)-th iteration which passes
verification of the MAC under the secret key
α
l
1
+1
=
α
l
2
+1
, and the success
probability is at most
μ
(
m
) due to security of the MAC. Thus
P
1
can get
utility at most
μ
(
m
)
a
+(1
l
i
=1
a
i
)
⊕
(
⊕
−
μ
(
m
))
b
. Therefore,
(
m
)=
μ
(
m
)
a
+(1
−
μ
(
m
))
b
−
b
=
μ
(
m
)(
a
−
b
)
.
The analysis of
P
2
's (
l
2
+ 1)-th iteration is similar.
Search WWH ::
Custom Search