Cryptography Reference
In-Depth Information
Garay and Ostrovsky [12] studies a model called Secure Message Transmission
by
Public Discussion
(SMT-PD) as an important building block for achieving secure multi-
party computation [3,6] on sparse networks. (A similar setting was studied earlier by
Franklin and Wright [11]). In this model, in addition to the wires in the standard SMT,
S
R
can access to a
public
channel which the adversary cannot alter but eavesdrop.
Generally speaking, the public channel is more expensive to implement than wires.
Since there are several ways to implement the public channel even on the sparse net-
works [8,21,4,5], the costs are still expensive. Thus, it is desirable to minimize the use
of this expensive resource. One of the typical efficiency measures of SMT-PD protocols
is the number of
rounds
where each round is one message flow between
and
.Shi,
Jiang, Safavi-Naini and Tuhin [18] (and Garay, Givens and Ostrovsky [13] also) gave
an SMT-PD protocol with 3 rounds, 2 of which invoke the public channel. We say that
an SMT-PD protocol is of (
r, r
)-round if the SMT-PD protocol satisfies that
r
is the
total number of rounds and
r
S
and
R
r
) is the number of rounds in which the public chan-
nel is invoked. Through this paper, we assume that
t
+1
≤
(
≤
≤
2
t
, since an efficient
(i.e., polynomial-time) “2-round” PSMT protocol is provided by Kurosawa and Suzuki
[14] when
n
n
≥
2
t
+1.Shiet al. also showed that (3
,
2)-round is optimal for SMT-PD
protocols (in case of
n
≥
t
+1) by showing the impossibility of useful (3
,
1)-round
SMT-PD protocols.
In this paper, we revisit the lower-bounds on the round complexity for SMT-PD
protocols. As mentioned, known round-optimal SMT-PD protocols invoke the public
channel twice: once is for the public transmission from
S
to
R
and the other time
is for that from
. This means that two types of implementation for the public
channel are necessary. If the message flows over public channel are one-way in SMT-
PD protocols, it is sufficient that we implement only one type of the public channel,
which is more desirable. We first discuss the limitation of SMT with the “unidirectional”
public channel, where either the sender or the receiver can invoke the public channel,
and show that the “bidirectional” public channel is necessary for SMT.
To discuss the directions of the message flows over the public channel, we consider
separately the number of rounds where the message flows are from
R
to
S
S
R
to
over the pub-
lic channel and the number of rounds where the message flows are from
.Wesay
that an SMT-PD protocol is of (
r, r
1
,r
2
)-round if the SMT-PD protocol is of
r
rounds
and satisfies that
r
1
(resp.,
r
2
) is the number of rounds in which the message flows are
from
R
to
S
). We review some previous results by using our ter-
minology. Known round-optimal SMT-PD protocols [18,13] are of (3
,
1
,
1)-round. Shi
et al. [18] showed that (
r,
1
,
0)-round protocol must satisfy that
ε
+
δ
S
to
R
(resp., from
R
to
S
≥
1
−
1
/
|
M
|
;
and (
r,
0
,
1)-round protocol must satisfy that
δ
≥
(1
−
1
/
|
M
|
)
/
2,where
r
≥
3 and
denotes the message space. We generalize their results and prove that (
i
) (
r, r
,
0)-
round protocol must satisfy that
ε
+
δ
M
;and(
ii
) (
r,
0
,r
)-round protocol
≥
1
−
1
/
|
M
|
≥
3 and
r
≤
must satisfy that
δ
r
. The statement (
i
)
says that any (
r, r
,
0)-round protocol is not useful at all. The statement (
ii
) does not
say anything about the privacy. Actually, we provide an upper-bounding (0
,δ
)-SMT-
PD protocol (
δ
≥
(1
−
1
/
|
M
|
)
/
2,where
r
≈
1
/
2 when
n
=2
t
), which says that the bound in (
ii
)isalmost
tight.
Search WWH ::
Custom Search