Cryptography Reference
In-Depth Information
s
=
s
l
∗
−
1
. Since Dealer set
s
=
s
l
∗
with probability
q
,
C
guesses wrong
with probability 1
−
q
. Therefore by deviating players in
C
get utility at
most
qa
+(1
−
q
)
c
. Requiring
qa
+(1
−
q
)
c<b,
(4)
then
C
has no incentive to deviate.
When recovering
I
l
∗
,since
I
l
∗
only indicates whether
s
l
∗
−
1
is the secret
•
or not which
C
has already known. Besides, at this time players outside
C
already get
s
l
∗
which means they also have opportunity to get the right
secret even if
C
deviates. Based on the inequality (4),
C
has no incentive
to deviate.
deviates in recovering
s
l
∗
, then players in
set
s
=
s
l
∗
•
If
C
C
with proba-
bility
q
and set
s
=
s
l
∗
q
. By the protocol
Π
,after
detecting someone cheats in recovering
s
l
∗
, each of the players outside
with probability 1
−
C
sets
s
=
s
l
∗
and quits. If Dealer set
σ
= 0 (which happens with proba-
bility
q
), then with probability
q
all players get the right secret and with
probability 1
guess wrong while others guess right. If
Dealer set
σ
= 1 (which happens with probability 1
−
q
players in
C
−
q
), then players
outside
C
get the wrong secret, while
C
guesses right with probability
1
q
.
Thus deviation in recovering
s
l
∗
−
makes players in
C
get utility at most
q
)
2
a
+
q
2
b
+
q
(1
q
(
qb
+(1
−
q
)
d
)+(1
−
q
)(
qc
+(1
−
q
)
a
)=(1
−
−
q
)(
c
+
d
)
.
By requiring
q
)
2
a
+
q
2
b
+
q
(1
(1
−
−
q
)(
c
+
d
)
<b,
(5)
C
has no incentive to deviate.
•
If
can increase
the utility by at most
=
O
(
λ
k
)where
k
is the number of participants
in the recovering process and
λ<
1 is a constant determined by
q
.
After deviation players in
C
deviates in recovering
I
l
∗
, we will show that players in
C
C
can determine the secret, while each player
sets
s
=
s
l
∗
with probability
q
and
s
=
s
l
∗
outside
C
with probability
1
−
q
. Suppose
|C|
=
c
, then there are
k
−
c
players outside
C
.IfDealer
set
σ
= 0, then the probability that none of the
k
−
c
players outputs the
q
)
k−c
, while if
σ
= 1, this probability is
q
k−c
.Thus
by deviation players in
right secret is (1
−
C
get utility at most
q
)
k−c
a
+(1
q
)
k−c
)
b
)+(1
q
)(
q
k−c
a
+(1
q
k−c
)
b
)
U
D
=
q
((1
−
−
(1
−
−
−
q
)
k−c
+(1
q
)
q
k−c
)
a
+(1
q
)
k−c
q
)
q
k−c
)
b.
=(
q
(1
−
−
−
q
(1
−
−
(1
−
q
)
k−c
+(1
q
)
q
k−c
)(
a
Therefore
=
U
D
−
b
=(
q
(1
−
−
−
b
). Denote
λ
k−c
(
a
b
)=
O
(
λ
k
).
λ
=
max
{
q,
1
−
q
}
,then
≤
−
•
Neglecting the negligible probability of successfully forging a MAC,
C
has no incentive to deviate after recovering
I
l
∗
, because
C
has already
known the secret and players outside
C
can also output the right secret.
Search WWH ::
Custom Search