Achieveability of the Key-Capacity in a Scenario of Key Sharing by Public Discussion and in the Presence of Passive Eavesdropper - Computer Network Security - page 311

k

1 /( 1 + ρ ) 1 /( 1 + ρ )

E ( ρ ) = ρ − ( + ρ ) log( p + ( − p ) ), R = .

0 m m

k + r

In the next Section 2 we apply these results in order to show how can be achieved
the key-capacity in asymptotic case for the special key-sharing protocol and how can
we approach to this key-capacity in non-asymptotic case depending on the string
length k and channel parameters p , p . In Section 3 we discuss these results in
the framework of implementation complexity and present some open problems.

2 The Proof of the Lower Bound for the Key-Rate

Let us consider the following key-sharing algorithm (KSA):
1. Bob generates truly random binary string of the length k and sends it to Alice

through BSCm.
2. Alice generates truly random binary string x , computes

′ ′

⊕ x

, where is a

⊕

noisy version received by Alice in the step 1 of KSA , - is modulo 2 addition

and sends it to Bob, through noiseless public channel.
3. Bob computers

′ ′

x = ⊕ x ⊕ .

y x 4. Alice sends to Bob the check string to the string

, where P is the matrix of the reduced echelon form
representing of the generator matrix of some linear

y = zH = xAH = xP

2 2

( k , k + r )

code. This code
(properly the matrix P ) can be chosen by legal parties to be good (with point of
view error correcting capability and the existence for it a constructive algorithm of
error correction).
5. Bob corrects errors in the noisy version x ′ of the Alice's string x . Denote by ~

′

this string after correction of errors.
6. Both Alice and Bob compute the key strings

K ,

A K

applying a multiplication by

B

to the strings x and ~

′

H 1 A

, respectively.
Let us prove the following asymptotic statement
Theorem 1. The KSA presented above allows to achieve asymtotically (as

matrix

k )
the key-capacity given by (1) if the legal channel is BSCm and the wire-tap channel is
BSCw for any

→ ∞

< w p .
Proof. By definition of the key-capacity it is such maximum possible key-rate
k

0 ≤ p < 1 / 2 0 ≤ 1 / 2 ,

m

k . We can see from KSA that after a per-
formance of its steps 1-3 there exists a virtual BSC between Alice and Bob with the
same error probability

R k = l /

I , P

→ 0 → ∞ that as

p as in the original legal BSCm. Hence we can use (4) in

m

k . Since Eve receives the sequence
sent by Bob to Alice in the step 1 of KSA through BSCw and

P

→ 0 → ∞

order to provide the condition as

′ ⊕ x sent by