Cryptography Reference
In-Depth Information
Proof.
(c) Note that an execution
E
is completely determined by the random-
ness and messages selected by all the parties. Then for each
E
∈
E
∈
E
,wehave
p
E
=
2
−r
S
−r
R
−r
A
/
,where
r
S
,
r
R
and
r
A
denote the length of the randomness of
C
S
,
C
R
and
C
A
respectively. Similarly, we have
p
E
=2
−r
S
−r
R
−r
A
/
|
M
|
|
M
|
.
,wehave
r
A
=
r
M
A
+
r
A
0
+
r
A
1
,where
r
M
A
,
r
A
0
,
r
A
1
denote the
length of
C
M
A
,
C
A
0
,
C
A
1
respectively. Similarly, we have
r
A
=
r
M
A
+
r
A
0
+
r
A
1
Since
C
A
2
=
⊥
.
Note that
r
A
0
=
r
A
0
=1and
r
M
A
=
r
M
A
=
log
|
M
|
. From the definition of
W
2
,wehavethat
r
R
=
r
R
,
r
S
=
r
A
1
and
r
A
1
=
r
S
. Hence we have
r
S
+
r
R
+
r
A
=
r
S
+
r
R
+
r
A
,and
p
E
=
p
E
holds.
(d) Let
S
2
=
E
\
S
2
denote the set of
failed
executions. Since
E
∈
S
2
holds for any
∈
S
2
, and the one-to-one correspondence of
E
and
E
, we get that
|
S
2
|≤|
S
2
|
E
.The
probability that
Π
fails when
M
A
=
M
S
can be computed as
Pr[
M
R
=
M
S
|
M
S
=
M
A
]
p
E
=
E∈
S
2
∈
S
2
]
≥
=Pr[
E
p
E
=Pr[
M
R
=
M
S
|
M
S
=
M
A
]
.
E∈
S
2
Let us proceed the proof of Theorem 3. From Lemma 5, we must have Pr[
M
R
=
M
S
|
=
M
S
]
≥
2
M
A
. Hence
1
2
(1
−
1
|
M
|
)
.
Pr[
M
R
=
M
S
]
≥
Pr[
M
R
=
M
S
|
M
S
=
M
A
]Pr[
M
S
=
M
A
]
≥
On the other hand, since
Π
is a
δ
-reliable protocol, we have Pr[
M
R
=
M
S
]
≤
δ
.It
follows that
δ
≥
(1
−
1
/
|
M
|
)
/
2, which contradicts the assumption on
Π
.
Theorem 2 says that any number of invocations of unidirectional public channel is not
helpful. On the other hand, Theorem 3 does not mention the privacy of SMT-PD proto-
cols. Thus, there seems to be room to be improved. In the next section, we will see that
Theorem 3 achieves almost optimal in a weak sense.
5
Upper Bound
In this section, we give an upper-bounding SMT-PD protocol where only
invokes the
public channel. Since the protocol uses universal hash functions, we give the definition
and see some property.
R
m
Definition 2.
Suppose that
m>
. A function family
H
=
{
h
:
{
0
,
1
}
→{
0
,
1
}
}
m
is called strongly universal
2
hash function family if for any distinct
a
1
,a
2
∈{
0
,
1
}
, it holds that Pr
h∈
H
[
h
(
a
1
)=
b
1
∧
h
(
a
2
)=
b
2
]
≤
2
−
2
.
and any
b
1
,b
2
∈{
0
,
1
}
m
Proposition 1.
Let
H
=
{
h
:
{
0
,
1
}
→{
0
,
1
}
}
be a strongly universal
2
hash
m
, it holds that
function family. Then, for any
(
a
1
,c
1
)
=(
a
2
,c
2
)
∈{
0
,
1
}
×{
0
,
1
}
h
(
a
2
)]
≤
2
−
.
Pr
h∈
H
[
c
1
⊕
h
(
a
1
)=
c
2
⊕
We can use “almost” strongly universal
2
hash functions instead of strongly universal
2
hash functions to reduce the communication complexity. But, in this paper, we do not
optimize the communication complexity.
Search WWH ::
Custom Search