Cryptography Reference
In-Depth Information
to generate the forged communication to replace the communication sent by
R
with.
C
M
A
is used to select uniformly a message from
M
to impersonate
S
.
By using these notations, we can describe
A
's behavior as follows. Without loss of
generality, we assume that
C
A
0
=1.
-
In the
j
-th round with 1
≤
j
≤
r
,
•
When
S
sends
X
j
Y
j
or
P
j
X
j
Y
j
,
A
blocks
Y
j
.Then
R
receives
X
j
or
P
j
X
j
,
respectively.
computes
X
j
Y
j
=
f
j
(
M
j−
1
•
R
sends
X
j
Y
j
,
A
,C
A
2
), then replaces
Y
j
When
A
with
Y
j
.(Here
M
j−
1
denotes the messages eavesdropped by
A
during the first
A
receives
X
j
Y
j
.
j
−
1 rounds.) Then,
S
outputs
M
A
=
g
(
M
r
A
,C
A
2
).
Due to the above strategy, we may assume that
C
M
A
=
⊥
-
Finally,
A
and
C
A
1
=
⊥
.
be the set of executions of
Π
, where each execution is determined by the
message
M
S
and the randomness
C
S
,
C
R
and
C
A
used for
Let
E
S
,
R
and
A
, respectively. We
to specify a pair (
E, E
) of executions as follows:
(
E, E
)
∈
W
1
if (1) (
M
S
,C
S
) are the same for both executions, (2)
C
A
0
⊕ C
A
0
=1,
and (3)
C
A
2
=
C
R
define a binary relation
W
1
⊆
E
×
E
and
C
R
=
C
A
2
.
Lemma 3.
Let
(
E, E
)
∈
W
1
. Then the following properties hold.
in
E
is identical to her view in
E
, that is,
M
S
=
M
r
(a)
The view of
S
S
.
in
E
is identical to the view of
in
E
, that is,
M
r
R
=
M
r
(b)
The view of
A
R
A
. Thus the
E
. That is,
M
R
=
M
A
holds.
output of
R
in
E
is the same as the output of
A
in
Proof.
We show the statements by induction with respect to the rounds. At the begin-
ning of the protocol, i.e., in the 0-th round, the views of
are
M
S
=
M
S
=
S
,
R
,and
A
,
M
0
R
=
M
0
R
=
∅
,and
M
0
A
=
M
0
A
=
∅
{
M
S
}
, respectively. These imply that the
statements (a) and (b) hold in the base case
j
=0.
Next, we show the inductive step. That is, we assume that the statements (a) and (b)
hold during the first (
j
−
1) rounds and prove that they hold during the first
j
rounds.
First, we observe that the protocol is a combination of the following three transmis-
sions:
(
α
)
transmissions from
S
to
R
over wires;
(
β
)
transmissions from
R
to
S
over wires;
(
γ
)
transmissions from
S
to
R
over wires and the public channel.
initiates the
j
-th round. From the inductive hypothesis, we have
M
j−
1
S
Assume that
S
=
is the same in the two executions
E
and
E
,
M
j−
1
S
.Since
C
S
S
in
E
invokes the public
in
E
invokes the public channel. Thus, we can consider the
inductive step in the cases (
α
), (
β
),and(
γ
) individually.
channel if and only if
S
Case
(
α
): From the inductive hypothesis, we have
M
j−
1
S
=
M
j−
1
S
and
M
j−
1
R
=
M
j−
1
A
.
does not get any new information. This implies that
M
j−
1
S
=
M
S
In this case,
S
and
Search WWH ::
Custom Search