Cryptography Reference
In-Depth Information
where the probability is over the randomness of all the parties. Then, the probability of
unreliable message transmission is
⎡
⎣
j∈
G
⎤
=
j∈
G
⎦
≤
Pr[
∃
R
j
=
R
j
]
Pr[
M
R
=
M
S
]=Pr
R
j
j
∈
G
s.t.
R
j
≤
Pr[
∃
at least one bad wire]
·
2
−
,
≤
Pr[wire
j
is bad]
≤
t
j∈
B
where the probability is over the random coins of all the parties.
Thus, putting altogether, we can say that the reliability
δ
satisfies
t
n
+
n − t
n
·
2
−
.
δ
≤
·
t
Next, we estimate the privacy parameter. The adversary can obtain transmissions related
to
M
S
only from the corrupted wires in the third round. Thus, the situation is completely
the same as (3,2)-round SMT-PD protocol by Shi et al.[18]. Thus, the proof of the
perfect privacy for their protocol also works in our case.
Let us consider the case where
n
=2
t
. Then, if
is large enough, then the reliability
parameter in Theorem 4 comes close to 1
/
2. In this sense, the gap between the lower
bound in Theorem 3 and the upper bound in Theorem 4 is slight.
6
Concluding Remarks
We have considered the secure message transmission with unidirectional public chan-
nel. We have shown that any (
r, r
,
0)-round protocol must satisfy that
ε
+
δ
≥
1
−
1
/
. It says that there is no useful (
r, r
,
0)-round SMT-PD protocol. We have also
shown that any (
r,
0
,r
)-round protocol must satisfy that
δ
|
M
|
|
M
|
)
/
2.Itsays
that there may exist an (
r,
0
,r
)-round (0
,
1
/
2)-SMT-PD protocol. Actually, if
n
=2
t
then the protocol in Theorem 4 satisfies that
δ
≥
(1
−
1
/
≈
1
/
2. However, there is still a gap in
general. In other words, either the lower bound in Theorem 3 or the upper bound in
Theorem 4 may be further improved.
Anyway, we may say that SMT-PD protocols require the bidirectional public
channel.
References
1. Araki, T.: Almost secure 1-round message transmission scheme with polynomial-time mes-
sage decryption. In: Safavi-Naini, R. (ed.) ICITS 2008. LNCS, vol. 5155, pp. 2-13. Springer,
Heidelberg (2008)
2. Agarwal, S., Cramer, R., de Haan, R.: Asymptotically optimal two-round perfectly secure
message transmission. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 394-408.
Springer, Heidelberg (2006)
Search WWH ::
Custom Search