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 308

Achieveability of the Key-Capacity in a Scenario
of Key Sharing by Public Discussion
and in the Presence of Passive Eavesdropper

Valery Korzhik 1 , Viktor Yakovlev 2 , and Alexander Sinuk 2

1 Specialized Center of Programm Systems “SPECTR”
Kantemirovsaya str., 10, St. Petersburg, 197342, Russia, ph/fax [phone]
2 State University of Telecommunications St. Petersburg, Russia

Abstract. We consider a scenario of key sharing between a pair of legal users
in the presence of passive eavesdropper. In this setting it is assumed the exis-
tence of a noisy channel between legal parties and also the existence of a noisy
wire-tap channel (which is not necessary inferior to the main channel). In addi-
tion to noisy channel there is a noiseless public channel connecting legal par-
ties. This means that eavesdropper can receive without errors all messages
transmitted through this noiseless channel. Because eavesdropper is passive (by
our assumption) this illegal party is unable to change any message transmitting
by legal parties both over noisy and noiseless channel. The final goal of legal
parties is to arrange such date exchange protocol using both noisy and noiseless
channels that provides them with bit strings K K and of the same length

A

B

P of their discrepancy
is close to zero; the amount of information I about these strings leaking to
eavesdropper is close to zero. Legal parties have nothing secret date shared in
advance except the knowledge of protocol and channel parameters that are
known also for eavesdropper. The key-rate R is the ratio of the string length
l to the length of the string transmitted between legal users through noisy
channel. Key-capacity C is the maximum possible key-rate when P and
I approach both to zero. For some particular cases of noisy channels key-
capacity has been found by U. Maurer. But it was open problem how to reach
this capacity with limited computing power. The authors presented at previous
MMM-ACNS'2001 workshop the constructive methods of key sharing for the
same model. But for some channel parameters the key rates differed key-
capacity in the several orders! In the current paper we use another protocol of
key sharing and demonstrate how near to key-capacity can be provided the key-
rate depending on complexity of key-sharing protocol.

l possessing the following properties: the probability

e

Keywords: Wire-tap channel, public discussion, key capacity, Renyi entropy,
privacy amplification.