Information Technology Reference
In-Depth Information
is not the case for binomial distribution that we have in BSC. Thus we need to use (9)
substituting it into (7).
The results of the calculations for the achievable values of the key-rate
R
as
functions of the string length
k
for different error probabilities in the legal channel
)
−
5
(
p
(
p
)
P
≤
5
⋅
10
and in the illegal channel
, for the probability of risk
and
m
w
10
−
30
I
≤
are presented in Fig. 1. The key-capacities are shown there by dotted
0
lines.
3
Discussion of the Results and Some Open Problems
We presented the paper towards an achievability of the key-capacity in a scenario of
public discussion by showing a technique of real key-rate calculation depending on
the states of legal and illegal channel and the length of the string transmitted through
noisy channel.
To produce the final key-strings we gave
KSA
that constitutes of the following ge-
neric procedures:
•
random bit string generation;
•
hashing the bit string to shorter bit string;
•
check bit string generation corresponding to a “good” error correcting code;
•
error correcting based on chosen code.
The most complex operations from the list above are hashing and error correcting
procedures. With the preceding notation a complexity of hashing is equivalent to a
complexity of multiplication the row vector of the length
k
by the matrix
k
×
(l+r)
. It
k
(
l
+
r
)
requires about
operations. As for a complexity of error correcting proce-
dure it depends on the type of code and error correcting algorithm but roughly
speaking we can let
2
Bkt
as an estimate of the number of elementary operations
where
t
is the number of correcting errors and
B
is some factor that does not depend
on the parameters
k
and
t
. We can see eventually that error correcting is the most time
(or space) consuming procedure in
KSA
. Fig. 1 shows (this is typically in general)
that for each channel state (
p
m
,
p
w
) there exists some string length
k
0
that provides the
key-rate close enough to the key-capacity. These values
k
0
are presented in Table 1.
This table shows that if the channel states are either
p
m
= 0.01,
p
w
= 0.1 or
p
m
=
p
w
=
0.1 the string lengths are still acceptable with point of view
KSA
complexity. But for
the channel state
p
m
=
p
w
= 0.01 and first of all for the channel state
p
m
= 0.1,
p
w
= 0.01
when illegal channel is superior to legal one the
KSA
is intractable with point of view
its complexity. Then we need to pay off complexity to the key-rate. So if we select
k
16000, then we obtain
k
/
= 307 and this is significant degradation of
KSA
efficiency. This situation disagrees to the situation with error correcting procedure on
ordinary BSC when the block length of error correcting codes can be chosen no more
k
