Cryptography Reference
In-Depth Information
Now, we give an upper-bounding SMT-PD protocol
Π
1
as follows. The following
protocol is an adaptation of (3,2)-round SMT-PD protocol proposed in [18].
and
R
i
∈{
0
,
1
}
m
1.
(
S→R
):For
i
=1
,...,n
,
S
randomly selects
r
i
∈{
0
,
1
}
and sends the pair (
r
i
,R
i
) to
R
along wire
i
.
correctly receives a pair (
r
i
,R
i
) along wire
i
2.
(
S←R
):For
i
=1
,...,n
,if
R
(i.e.,
r
i
∈{
0
,
1
}
and
R
i
∈{
0
,
1
}
m
),
and computes
T
i
=
r
i
⊕
R
selects
h
i
←
H
h
i
(
R
i
); otherwise, wire
i
is assumed
corrupted
.
R
then constructs an indicator bit
string
B
=
b
1
b
2
···
b
n
where
b
i
=1if the wire
i
is corrupted and
b
i
=0otherwise.
Finally,
sends (
B,
(
H
1
,...,H
n
)) over the public channel, where
H
i
=(
h
i
,T
i
)
if
b
i
=0;and
H
i
R
is empty, otherwise.
3.
(
S→R
):
S
ignores the wires with
b
i
=1.For
i
=1
,...,n
,if
b
i
=0,
S
computes
h
i
(
R
i
) and checks
T
i
=
T
i
;if
T
i
=
T
i
,wire
i
is assumed
consistent
;
otherwise, wire
i
is corrupted.
T
i
=
r
i
⊕
S
constructs an indicator bit string
V
=
v
1
v
2
···
v
n
,
where
v
i
=1if wire
i
is considered consistent; otherwise
v
i
=0.
S
sends the pair
(
V, C
=
M
S
⊕{
v
i
=1
R
i
}
) along every consistent wire
j
.
R
receives (
V
j
,C
j
)
(
V
,C
)
∈
V
along wire
j
and set
V
=
{
(
V
j
,C
j
)
}
.
R
chooses some pair
as
follows.
-
All the elements in
can be enumerated as (
U
1
,D
1
)
,...,
(
U
d
,D
d
) according
to some order, where
d
=
|
V
|
V
.
-
Let
d
i
be the number of indices
j
such that (
V
j
,C
j
)=(
U
i
,D
i
).
-
If
d
i
<n
−
t
then reset
d
i
=0.
-
Choose (
V
,C
)=(
U
k
,D
k
) with probability
d
k
/
(
i
d
i
).
Finally,
recovers
M
R
=
C
⊕{
v
i
=1
R
R
i
}
and outputs it, where
V
=
v
1
···
v
n
.
Theorem 4.
The protocol
Π
1
is a
(3
,
0
,
1)
-round
(0
,δ
)
-SMT-PD protocol, where
t
n
+
n
−
t
· t ·
2
−
.
δ ≤
n
Proof.
Let
B
=
{
i
: wire
i
is corrupted
}
and
G
=
{
i
: wire
i
is consistent
}
.
First, we upper-bound the reliability parameter. If
can detect all corrupted wires with
(
r
i
,R
i
)
=(
r
i
,R
i
) and (
V, C
)=(
V
,C
), then the protocol is perfectly reliable.
The probability of the event when
S
(
V, C
)=(
V
,C
)
t
)
/n
.We
consider that the reliability is always violated when (
V, C
)
=(
V
,C
). Hence in the
following we assume that (
V, C
)=(
V
,C
).
In the second round the wires with
b
i
=1are detected as corrupted and are ignored
in the third round. Hence in the following we only consider wires with
b
i
=0.Forwire
i
, the wire is called
bad
if (
r
i
,R
i
)
=(
r
i
,R
i
) but
r
i
⊕
is at least
(
n
−
h
i
(
R
i
)=
r
i
⊕
h
(
R
i
).Badwires
. Using Proposition 1 and noting that
r
i
,R
i
,r
i
,R
i
are fixed
before the second round and then
h
i
is selected with uniform distribution, we have
are always included in
G
h
i
(
R
i
)=
r
i
⊕
h
(
R
i
)
∧
(
r
i
,R
i
)
=(
r
i
,R
i
)]
Pr[wire
i
is bad]=Pr[
r
i
⊕
h
i
(
R
i
)=
r
i
⊕
h
(
R
i
)
|
(
r
i
,R
i
)
=(
r
i
,R
i
)]
≤
2
−
,
≤
Pr[
r
i
⊕
Search WWH ::
Custom Search