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