Cryptography Reference
In-Depth Information
M
j−
1
S
=
M
j
S
. Thus, we have
M
S
=
M
j
S
. That is, the statement (a) holds. On the other
hand,
R
and
A
get something new in the
j
-th round. In the execution
E
,
R
gets
X
j
and
gets
Y
j
. Thus, we have
M
j
R
=
M
j−
1
and
M
j
A
=
M
j−
1
A
∪{
X
j
}
∪{
Y
j
}
. In the execution
R
A
E
, the corrupted wires and the randomness are swapped, we have
M
j
R
=
M
j−
1
∪{
Y
j
}
R
and
M
j
A
=
M
j−
1
.Thus,wehave
M
j
R
=
M
j
A
. That is, the statement (b) holds.
Case
(
β
): From the inductive hypothesis, we have
M
j−
1
S
∪{
X
j
}
A
=
M
j−
1
S
and
M
j−
1
R
=
M
j−
1
A
.
gets
X
j
Y
j
,
In this case,
S
gets new information in the
j
-th round. In the execution
E
,
S
and
Y
j
where
X
j
is sent by
R
is transmission altered by
A
. More specifically, we
can write that
X
j
Y
j
=
f
j
(
M
j−
1
,C
R
) and
X
j
Y
j
=
f
j
(
M
j−
1
,C
A
2
). In the execution
R
A
E
,
gets the same information
X
j
Y
j
.But
and
Y
j
S
S
gets
X
j
from
A
from
R
.Note
that we can write
f
j
(
M
j−
1
A
,C
A
2
)=
f
j
(
M
j−
1
and
f
j
(
M
j−
1
R
,C
R
)=
X
j
Y
j
,C
R
)=
R
f
j
(
M
j−
1
A
,C
A
)=
X
j
Y
j
. Thus, we have
M
S
=
M
j
S
, that is, the statement (a) holds. On
do not get anything new. Thus, we have
M
j
R
=
M
j
the other hand,
R
and
A
.Thatis,
A
the statement (b) holds.
Case
(
γ
): This case is similar to Case
(
α
). From the inductive hypothesis, we have
M
j−
1
S
=
M
j−
1
S
and
M
j−
1
R
=
M
j−
1
A
. We can show that the statement (a) holds as well
as in Case
(
α
). In the execution
E
,
R
gets
P
j
X
j
and
A
gets
P
j
Y
j
. Thus, we have
M
j
R
=
M
j−
1
. In the execution
E
, the corrupted
wires and the randomness are swapped, we have
M
j
and
M
j
A
=
M
j−
1
∪{
P
j
X
j
}
∪{
P
j
Y
j
}
R
A
R
=
M
j−
1
and
M
j
∪{
P
j
Y
j
}
A
=
R
M
j−
1
A
. Thus, we have
M
j
R
=
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. Furthermore, we have
M
R
=
g
(
M
r
R
,C
R
)=
g
(
M
r
∪{
P
j
X
j
}
A
,C
A
2
)=
M
A
. This completes
the proof of Lemma 3.
Let us proceed the proof of Theorem 2. Let
S
1
∈
E
be the set of all successful ex-
ecutions in which
outputs
M
R
=
M
S
,and
p
E
denotes the probability of execu-
tion
E
determined by the randomness of all the parties. Define
p
E
R
similarly. Then
Pr[
M
R
=
M
S
]=
E∈
S
1
p
E
. By Lemma 3, if
E
∈
S
1
,
A
will output
M
S
in the
swapped execution of
E
; therefore Pr[
M
A
=
M
S
]
≥
E∈
S
1
p
E
.
Additionally, by the definition of
W
1
and the observation that
C
M
A
=
C
A
1
=
⊥
,
we have
1
|
M
|
2
−r
S
−r
R
−r
A
2
−
1
=
p
E
,
p
E
=
where
r
S
,
r
R
,
r
A
2
denote the length of the randomness of
C
S
C
R
,
C
A
2
used by
S
,
R
and
respectively.
From the above equation and Lemma 2, it follows that
A
1
|
M
|
1
−
δ
≤
Pr[
M
R
=
M
S
]
≤
Pr[
M
A
=
M
S
]
≤
+
ε.
Therefore, we have 1
−
1
/
|
M
|≤
ε
+
δ
, contradicting the assumption on
Π
.
r
≥
1
and
0
≤
Theorem 3.
Suppose that
n
≤
2
t
. For any
r
≥
ε
≤
1
, there is no
(
r,
0
,r
)
-round
(
ε, δ
)
-SMT-PD protocol with
δ<
(1
−
1
/
|
M
|
)
/
2
.
Search WWH ::
Custom Search