Cryptography Reference
In-Depth Information
Proof.
We prove the statement by contradiction. Suppose that there exists an (
r,
0
,r
)-
round (
ε, δ
)-SMT-PD protocol
Π
with
δ<
(1
−
1
/
|
M
|
)
/
2. We will construct an ad-
versary
who can violate the reliability of
Π
.
We will show that the
reliability
of
Π
will be violated. This is by showing that
for every successful execution there exists an unsuccessful one and so probability of
success is at most 1/2.
We describe
A
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
R
sends
X
j
Y
j
or
P
j
X
j
Y
j
,
A
blocks
Y
j
.Then
S
receives
X
j
or
P
j
X
j
,
respectively.
computes
X
j
Y
j
=
f
j
(
M
j−
1
•
When
S
sends
X
j
Y
j
,
A
,C
A
1
), then replaces
Y
j
A
with
Y
j
. Then,
receives
X
j
Y
j
.
R
outputs
M
A
=
g
(
M
r
A
,C
A
1
).
Due to the above strategy, we may assume that
C
A
2
=
⊥
-
Finally,
A
. For simplicity, we abuse the
notation
M
A
here to denote the uniformly selected message of
A
using the randomness
C
M
A
.
and
p
E
be as defined as in the proof of Theorem 2 and consider a binary relation
W
2
⊆
E
×
E
E
Let
where (
E, E
)
∈
W
2
if (1)
C
R
is the same in the two executions; (2)
C
A
0
⊕
C
A
0
=1;and(3)
C
A
1
=
C
S
,
C
S
=
C
A
1
;(4)
M
S
=
M
A
and
M
A
=
M
S
.We
denote by
S
2
the set of
successful
executions in which
R
outputs
M
R
=
M
S
under the
condition that
M
A
=
M
S
.
Lemma 4.
Let
(
E, E
)
∈
W
2
. Then the following properties hold.
(a)
The views of
in
E
and
E
are identical, that is,
M
r
R
=
M
r
R
R
.
in
E
is identical to the view of
in
E
, that is,
M
S
=
M
r
(b)
The view of
A
S
A
. Therefore,
∈
S
2
is a successful execution, then
E
if
E
∈
S
2
is a failed execution.
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
R
are the same in
E
and
E
,since
M
0
R
=
M
0
R
=
∅
are
M
S
=
M
0
A
=
{
. The views of
S
and
A
M
S
}
and
M
0
A
=
M
S
=
{
M
A
}
. 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;
(
β
)
R
S
transmissions from
to
over wires;
(
γ
)
transmissions from
R
to
S
over wires and the public channel.
initiates the
j
-th round. From the inductive hypothesis, we have
M
j−
1
R
Assume that
R
=
.Since
C
R
is the same in the two executions
E
and
E
,
M
j−
1
R
R
in
E
invokes the public
Search WWH ::
Custom Search