Cryptography Reference
In-Depth Information
Definition 1.
Aprotocol
Π
between
is an (
ε, δ
)-
secure message transmission
by public discussion
(SMT-PD) if the following two conditions are satisfied:
S
and
R
and
c
A
∈{
0
,
1
}
∗
,
Π
satisfies that
-
Privacy
: For every two messages
m
0
,m
1
∈
M
Δ
(
V
A
(
m
0
,c
A
)
,V
A
(
m
1
,c
A
))
≤
ε,
where the probability is taken over the randomness of
S
and
R
.
-
Reliability
:
R
recovers the message
M
S
with probability larger than 1
−
δ
.Inother
words, it holds that
Pr[
M
R
=
M
S
]
≤
δ,
where the probability is over the randomness of all the parties
S
,
R
and
A
,andthe
distribution of
M
S
.
Observe that the above definition is oblivious of the message distribution. In other
words, any SMT-PD protocol must be secure with the same privacy and reliability pa-
rameters regardless of the concrete distribution over
M
.
3
Known Results on the Round Complexity
In this section, we review some of known results on the round complexity for SMT-PD
protocols (when
n
≤
2
t
).
Theorem 1.
([11,18])
Suppose that
n
≤
2
t
. Then the following statements hold.
r
≥
1
, it is impossible to construct
(
r, r
)
-round
(0
,
0)
-SMT-
1. For any values
r
≥
PD protocols.
2. For any values
r
≤
1
, it is impossible to construct
(
r,
0)
-round
(
ε, δ
)
-SMT-PD protocols with
δ<
(1
−
1
/
≥
1
and
0
≤
ε
|
M
|
)
/
2
.
3. There is neither
(2
,
1
,
1)
-round nor
(2
,
2
,
0)
-round
(
ε, δ
)
-SMT-PD protocol with
ε
+
δ<
1
−
1
/
.
4. There is no
(3
,
1
,
0)
-round
(
ε, δ
)
-SMT-PD protocol with
ε
+
δ<
1
−
1
/
|
M
|
|
M
|
.
5. For any
0
≤
ε
≤
1
, there is no
(3
,
0
,
1)
-round
(
ε, δ
)
-SMT-PD protocol with
δ<
(1
−
1
/
|
M
|
)
/
2
.
In addition, we mention a technical lemma stated in [18], which we also use to derive
our results.
Lemma 2.
([18])
Let
Π
be an
(
ε, δ
)
-SMT-PD protocol and assume that
S
selects
M
S
←
M
. Then no adversary
A
can correctly guess
M
S
with probability larger than
ε
+1
/
|
M
|
. That is,
1
|
M
|
Pr[
M
A
=
M
S
]
≤
ε
+
,
where
M
A
denotes the adversary's output and the probability is taken over the random-
ness of
S
,
R
and
A
.
Search WWH ::
Custom Search