Cryptography Reference
In-Depth Information
in
E
invokes the public channel. Thus, we can consider the
inductive step in the cases (
α
), (
β
),and(
γ
) individually.
Case
(
α
): From the inductive hypothesis, we have
M
j−
1
R
channel if and only if
R
=
M
j−
1
R
and
M
j−
1
S
=
M
j−
1
A
.
In this case,
R
gets something new. In the execution
E
,
R
gets
X
j
Y
j
,where
X
j
is
sent by
S
and
Y
j
is a forged transmission by
A
. More specifically, we can write that
E
,
X
j
Y
j
=
f
j
(
M
j−
1
,C
S
) and
X
j
Y
j
=
f
j
(
M
j−
1
,C
A
1
). In the execution
S
gets the
S
A
same information
X
j
Y
j
.But
and
Y
j
R
gets
X
j
from
A
from
S
. Note that we can write
f
j
(
M
j−
1
A
,C
A
1
)=
f
j
(
M
j−
1
and
f
j
(
M
j−
1
S
,C
S
)=
f
j
(
M
j−
1
,C
R
)=
X
j
Y
j
,C
A
)=
S
A
X
j
Y
j
.Thus,wehave
M
j
R
=
M
j−
1
X
j
Y
j
}
=
M
j−
1
X
j
Y
j
}
=
M
j
∪{
∪{
R
,thatis,the
R
R
statement (a) holds. On the other hand, since
S
and
A
do not get anything new, we have
M
S
=
M
j−
1
=
M
j−
1
A
=
M
j
A
. That is, the statement (b) holds.
Case
(
β
): From the inductive hypothesis, we have
M
j−
1
R
S
=
M
j−
1
R
and
M
j−
1
S
=
M
j−
1
A
.
does not get anything new in the
j
-th round. This implies that
M
j−
1
R
In this case,
R
=
M
j
R
. Thus, we have
M
j
R
=
M
j
R
. That is, the statement (a) holds. On the other hand,
S
and
A
get something new in the
j
-th round. In the execution
E
,
S
gets
X
j
and
A
gets
Y
j
. Thus, we have
M
S
=
M
j−
1
and
M
j
A
=
M
j−
1
. In the execution
E
,
∪{X
j
}
∪{Y
j
}
S
A
the corrupted wires and the randomness are swapped, we have
M
j
S
=
M
j−
1
∪{
Y
j
}
and
S
M
j
A
=
M
j−
1
.Thus,wehave
M
S
=
M
j
∪{
X
j
}
A
. That is, the statement (b) holds.
A
Case
(
γ
): This case is similar to Case
(
β
). From the inductive hypothesis, we have
M
j−
1
R
=
M
j−
1
R
and
M
j−
1
S
=
M
j−
1
A
. We can show that the statement (a) holds as well
(
β
). In the execution
E
,
S
gets
P
j
X
j
A
gets
P
j
Y
j
. Thus, we have
as in Case
and
. In the execution
E
, the corrupted
wires and the randomness are swapped, we have
M
j
M
S
=
M
j−
1
and
M
j
A
=
M
j−
1
∪{
P
j
X
j
}
∪{
P
j
Y
j
}
S
A
S
=
M
j−
1
and
M
j
∪{
P
j
Y
j
}
A
=
S
M
j−
1
A
.Thus,wehave
M
S
=
M
j
A
. That is, the statement (b) holds.
In any cases, we have shown that the statements (a) and (b) during the first
j
rounds
hold. Thus, at the end of protocol, that is, after the
r
-th round, the statements (a) and (b)
hold.
In the executions
E
and
∪{
P
j
X
j
}
E
,
M
S
and
M
A
are swapped. If, in
E
,
R
outputs
M
R
=
g
(
M
r
R
,C
R
)=
M
S
,thenin
E
,
outputs
M
R
=
g
(
M
r
R
,C
R
)=
g
(
M
r
R
,C
R
)=
M
S
=
R
M
A
. Thus, if
M
A
=
M
S
and
E
∈
S
2
then
E
∈
S
2
. This completes the proof of
Lemma 4.
To complete Theorem 3, we need one more lemma.
Lemma 5
(c)
The occurrence probability of any two swapped executions
(
E, E
)
∈
W
2
is the
same, that is,
p
E
=
p
E
.
(d)
When
M
S
=
M
A
, the failure probability of
R
in recovering the secret message is
not less than the success probability of
R
, that is,
M
S
=
M
A
]
,
where the probability is taken over the randomness and messages selected by
Pr[
M
R
=
M
S
|
M
S
=
M
A
]
≤
Pr[
M
R
=
M
S
|
S
,
R
and
A
.
Search WWH ::
Custom Search